Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A prime number whose binary representation looks like a giraffe

reddit.com

Post reply on HN
Print view View original

21–30 of 82 posts

Re: A prime number whose binary representation looks like a giraffe

#21

Post by krisives »

szemet wrote: post #8
theaeolist wrote: post #4

The last line of the picture contains some 'noise': 0000000000000000000000000000000000000000000000000001000101101001 So the idea is that you produce any 63x64 binary image then you find a number up to 2^64 so that added to the number represented by the first image gives a prime. It's not exactly amazing, but clever enough.

Or you can move the image on canvases of different size until you find a position/size where it is prime. Several other methods can work... Primes are not rare at all - average prime gaps are fairly small in that domain...

Isn't the largest gap for any prime sqrt(n) ?

Re: A prime number whose binary representation looks like a giraffe

#23

Post by phkahler »

krisives wrote: post #21
szemet wrote: post #8

Earlier quoted context omitted.

Or you can move the image on canvases of different size until you find a position/size where it is prime. Several other methods can work... Primes are not rare at all - average prime gaps are fairly small in that domain...

Isn't the largest gap for any prime sqrt(n) ?

not even close. the average gap is closer to log(n).

Re: A prime number whose binary representation looks like a giraffe

#24

Post by tromp »

phkahler wrote: post #23
krisives wrote: post #21

Earlier quoted context omitted.

Isn't the largest gap for any prime sqrt(n) ?

not even close. the average gap is closer to log(n).

where log(n) is the natural logarithm of n

https://en.wikipedia.org/wiki/Prime_number_theorem

Re: A prime number whose binary representation looks like a giraffe

#25

Post by phkahler »

Smaug123 wrote: post #16
mkl wrote: post #15

Earlier quoted context omitted.

I had the same sort of idea, and just implemented it in Python using gmpy2 for the primality check. Here's a prime smiley face: 111010101111001000110101111111001001000010000 000000000000000000000000000000000000000000001 000000000000000001110111111100000000000000001 100000000000011110000000000011010000000000001 000000000011100000000000000000011100000000000 100000000100000000000000000000000011000000001 1000000110000000…

It is provably prime; I got Mathematica to generate a certificate for it in about five minutes using `PrimeQCertificate`.

Sometimes its a good idea to use a faster probable prime test when searching, and then use a slower test to verify the result. As has been done here.

Re: A prime number whose binary representation looks like a giraffe

#26

Post by tgb »

theaeolist wrote: post #4

The last line of the picture contains some 'noise': 0000000000000000000000000000000000000000000000000001000101101001 So the idea is that you produce any 63x64 binary image then you find a number up to 2^64 so that added to the number represented by the first image gives a prime. It's not exactly amazing, but clever enough.

I'm just disappointed that the noise isn't hidden in the pattern on the giraffe.

Re: A prime number whose binary representation looks like a giraffe

#27

Post by tischler »

tgb wrote: post #26
theaeolist wrote: post #4

The last line of the picture contains some 'noise': 0000000000000000000000000000000000000000000000000001000101101001 So the idea is that you produce any 63x64 binary image then you find a number up to 2^64 so that added to the number represented by the first image gives a prime. It's not exactly amazing, but clever enough.

I'm just disappointed that the noise isn't hidden in the pattern on the giraffe.

Then the background cannot be zeros.

Re: A prime number whose binary representation looks like a giraffe

#28

Post by jules »

szemet wrote: post #8
theaeolist wrote: post #4

The last line of the picture contains some 'noise': 0000000000000000000000000000000000000000000000000001000101101001 So the idea is that you produce any 63x64 binary image then you find a number up to 2^64 so that added to the number represented by the first image gives a prime. It's not exactly amazing, but clever enough.

Or you can move the image on canvases of different size until you find a position/size where it is prime. Several other methods can work... Primes are not rare at all - average prime gaps are fairly small in that domain...

I don't see why that would work. If the last digit is 0 then the number is not prime. Even if you make the bottom right corner a 1, it is not clear to me that any image will give a prime for sufficiently large canvas. The reason the original method works is that the density of primes around n is roughly 1/log n, so there are lots of primes around. If your image has k pixels the density is approx 1/k, so you'd only have to change the last log k pixels on average.

Re: A prime number whose binary representation looks like a giraffe

#29

Post by goldenkey »

tromp wrote: post #24
phkahler wrote: post #23

Earlier quoted context omitted.

not even close. the average gap is closer to log(n).

where log(n) is the natural logarithm of n https://en.wikipedia.org/wiki/Prime_number_theorem

Any log base is just a multiple of the natural log. When you talk about asymptotic growth, those factors are irrelevant.

Re: A prime number whose binary representation looks like a giraffe

#30

Post by tgb »

tischler wrote: post #27
tgb wrote: post #26

Earlier quoted context omitted.

I'm just disappointed that the noise isn't hidden in the pattern on the giraffe.

Then the background cannot be zeros.

Sorry, I mean the spots of the giraffe. You'd need a 'higher resolution prime' for that, but still.
Post reply on HN