9 ms·

A prime number whose binary representation looks like a giraffe

264 points by svenfaw 9y ago

tzahola 9y ago
Neat. Reminds me of illegal primes: https://en.m.wikipedia.org/wiki/Illegal_prime https://en.m.wikipedia.org/wiki/Illegal_prime
- sigotirandolas 9y ago
  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 9y 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.
    - tzahola 9y ago
      That's not exactly true. E.g. -1 is also a "factor" of 3: -3 * -1 = 3 In number theory we define primes as a subset of the natural numbers, which excludes negative integers. But when you move on to abstract algebra, the definition of a prime element in a commutative ring is an element p, such that p|ab implies p|a or p|b. Using this definition, we can conclude that the prime elements in the ring of integers are both the positive and negative primes.
    - mkl 9y ago
      -1 is not a prime, so that doesn't work. The actual reason is a little more boring - negative numbers are not prime by the definition of a prime number: "a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers" (Wikipedia).
      - posterboy 9y ago
        There's another definition, that doesn't have to exclude the one explicitly. I think it's a natural number not divisible by any natural number smaller than itself.
        tzahola 9y ago
        *other than one
        posterboy 9y ago
        damn what was it though ... can't remember where I read it.
    - deleted 9y ago
      [deleted]
    - tialaramex 9y ago
      Yes, the primes become more sparse, but because there are countably infinitely many of them, and the natural numbers (of which they are a subset) are merely countably infinite, this counts as "common". Our intuitions about this stuff are not very helpful in mathematics. For example, _most_ numbers are normal in any base (if you wrote them out as a decimal fraction they'd have an evenly distributed amount of all the different digits, forever) and we can prove this is true of the set of real numbers - but even though we know it's true, we don't have any definite examples of such numbers, the closest are we think Pi might be normal but we can't prove it, and we know Chaitin's constants are normal for sure, but by definition there's no way to write one of those down...
xaedes 9y 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/walk_made_with_the_first_million_digits_in_prime/ https://www.reddit.com/r/dataisbeautiful/comments/79hads/wal...
theaeolist 9y 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 9y 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 9y ago
    Isn't the largest gap for any prime sqrt(n) ?
    - phkahler 9y ago
      not even close. the average gap is closer to log(n).
      - tromp 9y ago
        where log(n) is the natural logarithm of n https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem
        goldenkey 9y ago
        Any log base is just a multiple of the natural log. When you talk about asymptotic growth, those factors are irrelevant.
        dvanduzer 9y ago
        It wasn't clear to me that the problem as framed was about asymptotic growth. I was curious if/when the factors might become relevant, so I started sketching this out... The 63x64 binary canvas is made of integers on the order of 2^4032. (Please forgive my approximation notation.) ln(2^4032) ~= 2795 log_10(2^4032) ~= 1214 So, the difference between natural log (for this canvas size) and log base 10 is only one binary digit (min 11, max 12). The "noise" you need to introduce to the image will definitely keep to the bottom right corner. So, I'm curious how tall the phone-width image needs to be before the required noise exceeds 64 bits (aka a single row). And the answer is... Too tall to be calculated quickly with my brute force method of "try bigger numbers until you get too impatient to wait for your desktop to calculate the natural log". I'm sure if I spent enough time drawing the parameters out, I'd eventually agree that there's no representation of this problem where those factors ever become relevant. BUT. If the problem we were calculating involved log base 1.0001 instead of the natural log, those factors would become relevant at much smaller canvas sizes. I would love to hear an intuitive explanation of logarithms that would convince me to not bother making calculations like this in the future!
krylon 9y 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.
- mkl 9y 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.
  - krylon 9y 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 9y ago
Cool but old. It can be done in any number base, e.g. in decimal: https://www.youtube.com/watch?v=fQQ8IiTWHhg https://www.youtube.com/watch?v=fQQ8IiTWHhg
js8 9y 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.
- deleted 9y ago
  [deleted]
reificator 9y 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-7697ece4918e0a73861de0eb37d08968.ssl.cf1.rackcdn.com/873_200w.jpg https://6d4be195623157e28848-7697ece4918e0a73861de0eb37d0896... (Sorry for unreadable CDN link)
- mkl 9y 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 https://gitlab.com/snippets/1694391
jamessb 9y 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 https://news.ycombinator.com/item?id=15208317 [2]: https://www.youtube.com/watch?v=fQQ8IiTWHhg https://www.youtube.com/watch?v=fQQ8IiTWHhg [3]: http://archive.bridgesmathart.org/2016/bridges2016-359.pdf http://archive.bridgesmathart.org/2016/bridges2016-359.pdf
- iClaudiusX 9y 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.html http://mathworld.wolfram.com/TuppersSelf-ReferentialFormula.... [1]: https://www.youtube.com/watch?v=_s5RFgd59ao https://www.youtube.com/watch?v=_s5RFgd59ao
ggambetta 9y ago
Mods, please add ["Contact" (the novel, not the movie) spoiler alert] to the title.
raverbashing 9y 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 9y 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.
- rtkwe 9y 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 9y ago
    How is that only 45 bits?
    - rtkwe 9y ago
      Cause that's how the math works. log_2(22,459,157,718,361) ~= 44.35. Powers of two get big really really fast after all. https://www.wolframalpha.com/input/?i=22,459,157,718,361+to+binary https://www.wolframalpha.com/input/?i=22,459,157,718,361+to+...
      - plafl 9y ago
        Shouldn't it be log_2(10^22,459,157,718,361)?
        daveFNbuck 9y ago
        That answers the question of how many bits of pi we know. If you want to be able to take an arbitrary n-bit string and find its position in a set of n-bit strings, you need to have something like 2^n strings in your set. So to find the number of bits you can support for an algorithm like this, taking the log of the number of digits of pi we know gives you a rough estimate.
        9y ago
userbinator 9y 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...
- qualitytime 9y ago
  "write a short program that checks if a file is a prime number." What do you mean? I tried googling but failed.
  - qualitytime 9y ago
    Was that a downvote? For asking a question? Jeez.
  - colejohnson66 9y ago
    Hint: Interpret the file’s bits as a single number
    - qualitytime 9y ago
      Thanks for the clarification.
DoreenMichele 9y ago
In my mind, math + giraffes = https://news.ycombinator.com/user?id=RiderOfGiraffes 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 9y 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.

264 points by svenfaw 9y ago

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

sigotirandolas 9y ago
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 9y 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.
  - tzahola 9y ago
    That's not exactly true. E.g. -1 is also a "factor" of 3: -3 * -1 = 3 In number theory we define primes as a subset of the natural numbers, which excludes negative integers. But when you move on to abstract algebra, the definition of a prime element in a commutative ring is an element p, such that p|ab implies p|a or p|b. Using this definition, we can conclude that the prime elements in the ring of integers are both the positive and negative primes.
  - mkl 9y ago
    -1 is not a prime, so that doesn't work. The actual reason is a little more boring - negative numbers are not prime by the definition of a prime number: "a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers" (Wikipedia).
    - posterboy 9y ago
      There's another definition, that doesn't have to exclude the one explicitly. I think it's a natural number not divisible by any natural number smaller than itself.
      - tzahola 9y ago
        *other than one
        posterboy 9y ago
        damn what was it though ... can't remember where I read it.
  - deleted 9y ago
    [deleted]
  - tialaramex 9y ago
    Yes, the primes become more sparse, but because there are countably infinitely many of them, and the natural numbers (of which they are a subset) are merely countably infinite, this counts as "common". Our intuitions about this stuff are not very helpful in mathematics. For example, _most_ numbers are normal in any base (if you wrote them out as a decimal fraction they'd have an evenly distributed amount of all the different digits, forever) and we can prove this is true of the set of real numbers - but even though we know it's true, we don't have any definite examples of such numbers, the closest are we think Pi might be normal but we can't prove it, and we know Chaitin's constants are normal for sure, but by definition there's no way to write one of those down...

xaedes 9y 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/walk_made_with_the_first_million_digits_in_prime/ https://www.reddit.com/r/dataisbeautiful/comments/79hads/wal...

theaeolist 9y 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 9y 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 9y ago
  Isn't the largest gap for any prime sqrt(n) ?
  - phkahler 9y ago
    not even close. the average gap is closer to log(n).
    - tromp 9y ago
      where log(n) is the natural logarithm of n https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem
      - goldenkey 9y ago
        Any log base is just a multiple of the natural log. When you talk about asymptotic growth, those factors are irrelevant.
        dvanduzer 9y ago
        It wasn't clear to me that the problem as framed was about asymptotic growth. I was curious if/when the factors might become relevant, so I started sketching this out... The 63x64 binary canvas is made of integers on the order of 2^4032. (Please forgive my approximation notation.) ln(2^4032) ~= 2795 log_10(2^4032) ~= 1214 So, the difference between natural log (for this canvas size) and log base 10 is only one binary digit (min 11, max 12). The "noise" you need to introduce to the image will definitely keep to the bottom right corner. So, I'm curious how tall the phone-width image needs to be before the required noise exceeds 64 bits (aka a single row). And the answer is... Too tall to be calculated quickly with my brute force method of "try bigger numbers until you get too impatient to wait for your desktop to calculate the natural log". I'm sure if I spent enough time drawing the parameters out, I'd eventually agree that there's no representation of this problem where those factors ever become relevant. BUT. If the problem we were calculating involved log base 1.0001 instead of the natural log, those factors would become relevant at much smaller canvas sizes. I would love to hear an intuitive explanation of logarithms that would convince me to not bother making calculations like this in the future!

krylon 9y 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.

mkl 9y 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.
- krylon 9y 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 9y ago

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

js8 9y 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.

deleted 9y ago
[deleted]

reificator 9y 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-7697ece4918e0a73861de0eb37d08968.ssl.cf1.rackcdn.com/873_200w.jpg https://6d4be195623157e28848-7697ece4918e0a73861de0eb37d0896... (Sorry for unreadable CDN link)

mkl 9y 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 https://gitlab.com/snippets/1694391

jamessb 9y 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 https://news.ycombinator.com/item?id=15208317 [2]: https://www.youtube.com/watch?v=fQQ8IiTWHhg https://www.youtube.com/watch?v=fQQ8IiTWHhg [3]: http://archive.bridgesmathart.org/2016/bridges2016-359.pdf http://archive.bridgesmathart.org/2016/bridges2016-359.pdf

iClaudiusX 9y 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.html http://mathworld.wolfram.com/TuppersSelf-ReferentialFormula.... [1]: https://www.youtube.com/watch?v=_s5RFgd59ao https://www.youtube.com/watch?v=_s5RFgd59ao

ggambetta 9y ago

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

raverbashing 9y 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 9y 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.

rtkwe 9y 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 9y ago
  How is that only 45 bits?
  - rtkwe 9y ago
    Cause that's how the math works. log_2(22,459,157,718,361) ~= 44.35. Powers of two get big really really fast after all. https://www.wolframalpha.com/input/?i=22,459,157,718,361+to+binary https://www.wolframalpha.com/input/?i=22,459,157,718,361+to+...
    - plafl 9y ago
      Shouldn't it be log_2(10^22,459,157,718,361)?
      - daveFNbuck 9y ago
        That answers the question of how many bits of pi we know. If you want to be able to take an arbitrary n-bit string and find its position in a set of n-bit strings, you need to have something like 2^n strings in your set. So to find the number of bits you can support for an algorithm like this, taking the log of the number of digits of pi we know gives you a rough estimate.
      - 9y ago

userbinator 9y 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...

qualitytime 9y ago
"write a short program that checks if a file is a prime number." What do you mean? I tried googling but failed.
- qualitytime 9y ago
  Was that a downvote? For asking a question? Jeez.
- colejohnson66 9y ago
  Hint: Interpret the file’s bits as a single number
  - qualitytime 9y ago
    Thanks for the clarification.

DoreenMichele 9y ago

In my mind, math + giraffes = https://news.ycombinator.com/user?id=RiderOfGiraffes 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 9y 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.