A prime number whose binary representation looks like a giraffe

https://www.reddit.com/r/math/comments/7qpfls/does_there_exist_a_prime_number_whose/

by svenfaw • 9 years ago

264 76 9 years ago

tzahola3• 9 years ago

Neat. Reminds me of illegal primes: https://en.m.wikipedia.org/wiki/Illegal_prime

It’s pretty much the same thing - take some arbitrary data, and add some bits so that the result is prime. Not surprising from a mathematical point of view since primes are very common, but it’s a fun thing to see.

bringtheaction• 9 years ago

primes are very common

Isn't it thought that they get more and more rare the further you go away from zero in the positive direction?

By the way I just realized why no negative numbers are prime and that's because -1 is a factor in all of them. Quite obvious but I just never thought about it before.

xaedes• 9 years ago

Found the link in the comments to the "Walk made with the first million digits in prime numbers" very interesting!

https://www.reddit.com/r/dataisbeautiful/comments/79hads/wal...

theaeolist• 9 years ago

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.

szemet• 9 years ago

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...

krisives• 9 years ago

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

jules• 9 years ago

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.

tgb2• 9 years ago

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

tischler• 9 years ago

Then the background cannot be zeros.

dahart2• 9 years ago

The last line of the picture contains some 'noise'

Note that if the picture is prime, then the last line must always contain noise... the last digit must be a 1!

I also feel like it's slightly cheating that the first line doesn't contain noise, or a leading 1 digit... the number doesn't naturally fit into 64x64 bits because of all the leading zeroes.

ThrustVectoring• 9 years ago

If you "draw" with zeros instead of ones, then you don't have the last-digit-in-foreground problem.

llamaz2• 9 years ago

That may have been how the author came up with a prime number, but any extremely large odd number is probably prime, since the primes get further and further apart as you go further along the number line. So it may have been a lucky guess.

Jeff_Brown• 9 years ago

This logic is backward. If you want empirical evidence you can ask WolframAlpha:

There are 25 primes in [1, 100]. There are 16 in [1001, 1100]. There are 6 in [1000001, 1000100].

krylon2• 9 years ago

Did somebody stumble upon this by accident, or did they deliberately look for a prime number and play with the layout until they saw a picture?

Either way, this is really cool.

mkl3• 9 years ago

They made/got the picture, converted it to a number (by interpreting it as binary), then incremented the number until they found the next prime. The incrementing is what made the "noise" in the bottom right.

krylon2• 9 years ago

Thanks for explanation. It does take away the magic, though.

It's still way cool, but how much cooler woulc it have been if a mathematician had stumbled upon this by accident...

msuvakov• 9 years ago

Cool but old. It can be done in any number base, e.g. in decimal: https://www.youtube.com/watch?v=fQQ8IiTWHhg

js8• 9 years ago

I think it would look much better had he put a frame around it with binary ones. It would not only hint about how to decode it, but it would also make it more likely to be prime (ending with huge number of 1s) and hide the ugly noise.

I would also like to conjecture that there is infinitely many primes that look like a giraffe in binary, so it's nothing that unusual.

reificator• 9 years ago

I think the more interesting way to do this would be to create a border that's roughly circular to frame the giraffe, and fill that border with noise. Then do the incrementing thing, and your 12 or so bits of noise at the end will blend in better, making it harder for the average person to reverse engineer.

I'm imaging something like this, but with a giraffe instead: https://6d4be195623157e28848-7697ece4918e0a73861de0eb37d0896...

(Sorry for unreadable CDN link)

mkl3• 9 years ago

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
  100000011000000000000000000000000000100000001
  100000110000000001000000001000000000011000001
  100000100000000001000000001000000000001100000
  000001000000000001000000001000000000000100001
  100010000000000001000000001000000000000010000
  000010000000000001000000001000000000000010001
  000010000000000001000000001000000000000010000
  000010000000000000000000000000000000000010000
  100010000001100000000000000000001100000010001
  000001000000110000000000000000011000000100000
  000000100000011000000000000000110000001100001
  100000110000001111000000000111100000011000000
  000000011000000001111111111100000000100000000
  100000000100000000000000000000000011000000001
  000000000011100000000000000000011100000000000
  100000000000011110000000000011010000000000000
  100000000000000001110111111100000000000000000
  100000000000000000000000000000000000000000001
  111011110010001011101100010110111111110011001

As a number, it's

  418286130038247526051590581692998429049634527936177232676862400134230223310124567196900044669909574838414882468188159808593146618824409867113710174334769625185535031892647808338085451521099179358299885075661065903947563499117521951858387121272237585876050870984471996640946451287415573046990997289875221396633775785411121263373993999302553.

This took 487 random border attempts to find, which seems pretty small!

Note that efficient primality tests are probabilistic, so there's a small chance this isn't actually prime. I expect it's the same with the giraffe one in the link.

Edit: Here's the code (improved a bit over what made the picture above): https://gitlab.com/snippets/1694391

Smaug123• 9 years ago

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

jdnier2• 9 years ago

Playing with the wrap width (in this case 94), you'll see a small herd of giraffes instead. (This is the prime from the reddit article, rather than your smiley face. Easier to see white on black.)

    100000000000000000000000000000000000000000000000000000000000000110000000000000000000000000000000
    000000000000000000000000000000111000000000000000000000000000000000000000000000000000000000000111
    110000000000000000000000000000000000000000000000000000000000111111000000000000000000000000000000
    000000000000000000000000000011111110000000000000000000000000000000000000000000000000000000011111
    111000000000000000000000000000000000000000000000000000000001000011110000000000000000000000000000
    000000000000000000000000000000000111000000000000000000000000000000000000000000000000000000000000
    011110000000000000000000000000000000000000000000000000000000000000111100000000000000000000000000
    000000000000000000000000000000000011110000000000000000000000000000000000000000000000000000000000
    000111100000000000000000000000000000000000000000000000000000000000011111000000000000000000000000
    000000000000000000000000000000000000111110000000000000000000000000000000000000000000000000000000
    000011111100000000000000000000000000000000000000000000000000000000000111111100000000000000000000
    000000000000000000000000000000000000011111111100000000000000000000000000000000000000000000000000
    000000111111111100000000000000000000000000000000000000000000000000000011111111111000000000000000
    000000000000000000000000000000000000000111111111111000000000000000000000000000000000000000000000
    000000001111111111111100000000000000000000000000000000000000000000000000111111111111111100000000
    000000000000000000000000000000000000000011111111111111111000000000000000000000000000000000000000
    000000001111111111111111110000000000000000000000000000000000000000000000111111111111111111000000
    000000000000000000000000000000000000000011111111111111111110000000000000000000000000000000000000
    000000001111111111111111111000000000000000000000000000000000000000000000011111111111111111100000
    000000000000000000000000000000000000000001111111111111111110000000000000000000000000000000000000
    000000000111100001111111110000000000000000000000000000000000000000000000011110000011111111000000
    000000000000000000000000000000000000000001111000000111111100000000000000000000000000000000000000
    000000001111100000011111110000000000000000000000000000000000000000000000110110000000110111000000
    000000000000000000000000000000000000000011011000000011101110000000000000000000000000000000000000
    000000011001100000001110111000000000000000000000000000000000000000000001100110000000111001110000
    000000000000000000000000000000000000000110011000000011100110000000000000000000000000000000000000
    000000011001100000001100011000000000000000000000000000000000000000000000110010000000100001100000
    000000000000000000000000000000000000000001001000000110000110000000000000000000000000000000000000
    000000000011100000010000011000000000000000000000000000000000000000000000001110000011000001100000
    000000000000000000000000000000000000000000011000011000000110000000000000000000000000000000000000
    000000000001100001100000011000000000000000000000000000000000000000000000000111001100000001100000
    000000000000000000000000000000000000000000011100110000000110000000000000000000000000000000000000
    000000000001010011000000010000000000000000000000000000000000000000000000001100000000000011000000
    000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    000000000000000000000000000000000000000000000000000000000000001000101101001

YomiK2• 9 years ago

Pari/GP's APR-CL took 4 seconds to prove it. Perl's ntheory module took 2.6 seconds to prove with ECPP (including generating and verifying a certificate). That's over 1000x slower than BPSW but still not bad.

jamessb• 9 years ago

Previously on HN, someone posted the The Corpus Christi Prime blog post [1], which was inspired by the Numerphile Trinity Hall Prime video [2].

See also Zachary Abel's Prime Portraits article [3].

[1] https://news.ycombinator.com/item?id=15208317

[2] https://www.youtube.com/watch?v=fQQ8IiTWHhg

[3] http://archive.bridgesmathart.org/2016/bridges2016-359.pdf

iClaudiusX• 9 years ago

See also Tupper's Self-Referential Formula [0] and the Numberphile explanation [1] for generating bitmap plots of itself.

[0] http://mathworld.wolfram.com/TuppersSelf-ReferentialFormula....

[1] https://www.youtube.com/watch?v=_s5RFgd59ao

ggambetta• 9 years ago

Mods, please add ["Contact" (the novel, not the movie) spoiler alert] to the title.

raverbashing• 9 years ago

Seems like an idea for a (lighter) proof of work, find a prime number in a certain format (and the harder it is, the least noise it should have)

amelius• 9 years ago

Here's another challenge: find a number whose binary representation looks like Mickey mouse, and find the index where it occurs in the binary representation of pi. Bonus: that index should have a binary representation that looks like a copyright symbol.

rtkwe3• 9 years ago

We don't have the digits of pi for the second part. We only have 22,459,157,718,361 digits of pi which is only ~45 bits not enough to create the image with bits left over for moving it around in pi.

selestify• 9 years ago

How is that only 45 bits?

userbinator• 9 years ago

Great, another great demonstration of the fundamental principles of digital computing - representation and interpretation of data. It's been my experience teaching CS courses that many students, despite being taught bits and bytes and binary and ASCII and so forth, don't really "get it" until they see things like this.

This particular one only looks like a giraffe when it's interpreted as a 1bpp big-endian bitmap, but you could probably do the same with a colour (24bpp, in whatever order you wish) photo.

Here's another fun idea: write a short program that checks if a file is a prime number. Now you can get into the principles of CRCs, RS, and other error-correction codes...

qualitytime3• 9 years ago

"write a short program that checks if a file is a prime number."

What do you mean? I tried googling but failed.

qualitytime3• 9 years ago

Was that a downvote? For asking a question? Jeez.

colejohnson66• 9 years ago

Hint: Interpret the file’s bits as a single number

DoreenMichele• 9 years ago

In my mind, math + giraffes =

https://news.ycombinator.com/user?id=RiderOfGiraffes

There shouldn't be two answers for that equation. That is just too weird of a coincidence.

RiderOfGiraffes• 9 years ago

I guess I should comment here, but I don't have much to add. Most of the questions that arise naturally about how this was done, and about primes in general, have already been asked and answered.

Still, given my username I should add something ...

So if the size was prime x prime then the fact that the number of bits is a semi-prime tells you the size of the image, even if all you have is a stream of digits. Then the "noise" at the end will tell you what the least significant bits are, and hence you get an image without very much ambiguity.

Just thought I'd mention that.

A prime number whose binary representation looks like a giraffe

Related Stories