Images Created from Prime Numbers(futilitycloset.com)
futilitycloset.com
Images Created from Prime Numbers
https://www.futilitycloset.com/2020/01/12/more-prime-images/
130 comments
The way I would describe it is that the primality of a number is almost completely unrelated to these images. The image is chosen beforehand, then a set of integers is chosen that each looks recognizably close to that image, then that set is searched for one that is prime (which is not unusual). Primality is the chosen attribute simply because it’s widely known and considered to be interesting in popular mathematics. People would be less impressed by images constructed with the binary representation of numbers divisible by 1,000,000, even though that may be a rarer property than primality for the magnitude of numbers considered.
Your argument is true; though constructing images with numbers divisible by 1000000 is far easier. Take any image you want, and replace the last figures by zeroes. You'll just get a small artefact in the bottom right corner!
Not in binary, right?
This is why I love the idea of the "Library of Babel". The basic idea is that it's a vast "library" of every permutation of letters and punctuation in a book. Almost every book would be complete gibberish, but there much also be every book ever written, already created and waiting to be discovered.
Is any idea truly created, or simply discovered first? Or is the simple fact of having too many possibilities man that there's no possible way you can "discover" anything at all, and anything much be invented first to be looked for?
Is any idea truly created, or simply discovered first? Or is the simple fact of having too many possibilities man that there's no possible way you can "discover" anything at all, and anything much be invented first to be looked for?
well, among other things that library contains an infinite number of proofs that P=NP. Also an infinite number of proofs of the opposite. Also an infinite number of base64-encoded FLACs of the original cast recording of a rock opera based on each of those proofs, performed by David Bowie and Justin Bieber. Obviously, an infinite number of them contain logical flaws. An infinite number of them are surprisingly listenable.
You’re welcome to devote time to trying to discover them...
You’re welcome to devote time to trying to discover them...
> well, among other things that library contains an infinite number of proofs that P=NP. Also an infinite number of proofs of the opposite.
Of course, given our current understanding of math and logic, although there would be an infinite number of proofs both for and against P=NP, only ones on one side of the argument could ever be correct, and all the others must contain logical errors, however subtle.
Assuming that the proof of P=NP isn't somehow outside of human comprehension, it means that, over an infinite period of time, a human could go over all those infinite proofs and still pick out the correct answer.
Of course, given our current understanding of math and logic, although there would be an infinite number of proofs both for and against P=NP, only ones on one side of the argument could ever be correct, and all the others must contain logical errors, however subtle.
Assuming that the proof of P=NP isn't somehow outside of human comprehension, it means that, over an infinite period of time, a human could go over all those infinite proofs and still pick out the correct answer.
> with an infinite numbers of primes available to us, nothing is hidden
Just because there's an infinite number of primes, it doesn't necessarily mean that everything is in there, does it? For example, would you expect to find Romeo and Juliet in pi? It might be there, but I don't think it has to be there, does it?
Just because there's an infinite number of primes, it doesn't necessarily mean that everything is in there, does it? For example, would you expect to find Romeo and Juliet in pi? It might be there, but I don't think it has to be there, does it?
> A sequence is normal if and only if every block of equal length appears with equal frequency. (A block of length k is a substring of length k appearing at a position in the sequence that is a multiple of k: e.g. the first length-k block in S is S[1..k], the second length-k block is S[k+1..2k], etc.) This was implicit in the work of Ziv and Lempel (1978) and made explicit in the work of Bourke, Hitchcock, and Vinodchandran (2005). [1]
If pi is normal (as it is conjectured to be), then yeah it has to.
[1] https://en.wikipedia.org/wiki/Normal_number#Properties
If pi is normal (as it is conjectured to be), then yeah it has to.
[1] https://en.wikipedia.org/wiki/Normal_number#Properties
This is amazing!
So somewhere pi is a computer program that when run would set up a server with an entry for every person that has ever lived or ever will live with complete information on that person. You could theoretically see a real-time movie of anybody from life until death. Crazy!
Do you know if k has to be finite?
So somewhere pi is a computer program that when run would set up a server with an entry for every person that has ever lived or ever will live with complete information on that person. You could theoretically see a real-time movie of anybody from life until death. Crazy!
Do you know if k has to be finite?
K would have to be finite, yes, or there could never be another string after it. But k can be arbitrarily large.
Yes, Normal Numbers are awesome to think about when you first learn them. Ever tiny detail of everything that has ever happened in the history of the world, written in incredibly beautiful prose that would bring the entire planet to its knees on reading it, is somewhere in the digits of pi.
Of course, so are a lot of lies -- every possible variant of lie. And lots and lots and lots of junk. Indeed, you can make a program to search pi for any string of letters, and if your program is powerful enough you may find a 10 or 11 digit sequence of your choosing, but no more than that. And of course, searching for the string you pre-chose seems a lot more underwhelming than stumbling across the story of your life.
https://www.angio.net/pi/
Yes, Normal Numbers are awesome to think about when you first learn them. Ever tiny detail of everything that has ever happened in the history of the world, written in incredibly beautiful prose that would bring the entire planet to its knees on reading it, is somewhere in the digits of pi.
Of course, so are a lot of lies -- every possible variant of lie. And lots and lots and lots of junk. Indeed, you can make a program to search pi for any string of letters, and if your program is powerful enough you may find a 10 or 11 digit sequence of your choosing, but no more than that. And of course, searching for the string you pre-chose seems a lot more underwhelming than stumbling across the story of your life.
https://www.angio.net/pi/
That's really fascinating.
So if you could find things in pi (or any normal number) quickly enough, then any arbitrary chunk of data could be compressed to just an offset and a length into that number. That's kind of crazy to think about.
So if you could find things in pi (or any normal number) quickly enough, then any arbitrary chunk of data could be compressed to just an offset and a length into that number. That's kind of crazy to think about.
No, not compressed - the offset would always be (much) larger than the arbitrary chunk of data. It's flawed intuition to think of the information as "in" pi - it's "in" the offset, and pi is essentially a small decryption algorithm.
Don't get carried away with pi mysticism - all this stuff is also true of the concatenation of all integers in order (0123456789101112131415...).
Don't get carried away with pi mysticism - all this stuff is also true of the concatenation of all integers in order (0123456789101112131415...).
It's an idea as old as time. Or 8 years, at the very least: https://github.com/philipl/pifs
In expectation, a k-digit sequence will require a k-digit number to encode its offset, so there's no compression there.
Then again, there's this gem 762 decimal places in: http://mathworld.wolfram.com/FeynmanPoint.html
In expectation, a k-digit sequence will require a k-digit number to encode its offset, so there's no compression there.
Then again, there's this gem 762 decimal places in: http://mathworld.wolfram.com/FeynmanPoint.html
> https://github.com/philipl/pifs
That's brilliant. I also like that you don't need to store the offsets anywhere else, because that metadata is also just data that can itself be found in pi.
Actually, that sounds like one of the sects in Library of Babel, who tried to find the one true catalogue (or whatever it was) by looking for the book that told where it was, and the book that told where that book was, etc. There must be an infinite number of books that lead the way to the catalogue.
That's brilliant. I also like that you don't need to store the offsets anywhere else, because that metadata is also just data that can itself be found in pi.
Actually, that sounds like one of the sects in Library of Babel, who tried to find the one true catalogue (or whatever it was) by looking for the book that told where it was, and the book that told where that book was, etc. There must be an infinite number of books that lead the way to the catalogue.
Conjectured, but still not proved to be normal. Or did I miss something this big?
Note also that the line breaks are chosen by a human, and if you look at the bottom right corner of some of the images you can see random-looking digits that don't contribute to the image, but do contribute to the "primeness". There's the actual size of the search space, the rest of it is just picked to look that way. It's still a huge space and doesn't discount the effort of finding candidates and checking them, but it does demystify the image a bit.
Not quite true.
Sagan's version was better than that analysis suggests: http://kasmana.people.cofc.edu/MATHFICT/mf55-spoiler.html
> as Sagan puts it in the story itself, the surprise is not that it appears that it appears "so early" in the sequence.
> as Sagan puts it in the story itself, the surprise is not that it appears that it appears "so early" in the sequence.
It seems there was a large (unconscious?) religious dimension to SETI. Michael Shermer:
[David Swift in his 1990 book SETI Pioneers] asked each of the SETI pioneers about their parents’ religiosity... most were raised in a religious household but that not one believes in anything like the traditional Judeo-Christian God... Astronomer Frank Drake, ostensively the SETI pioneer if there was one (and creator of the infamous “Drake equation” for computing the probability of ETIs), who was raised “Very strong Baptist. Sunday school every Sunday,” made this observation: “A strong influence on me, and I think on a lot of SETI people, was the extensive exposure to fundamentalist religion. You find when you talk to people who have been active in SETI that there seems to be that thread. They were either exposed or bombarded with fundamentalist religion. So to some extent it is a reaction to firm religious upbringing”. Similarly, John Kraus recalled: “We were very strong churchgoers, members of the Methodist church. I was brought up in a very religious atmosphere…there was never any thought of conflict between science and religion in my thinking or in my upbringing. Science and religion were simply both seeking ultimate truth but using different ways of going at it”. ...
... One might speculate that SETI, as a highbrow, elitist revolution, contains within it quasi-religious and spiritual overtones, in the sense that these scientists, while not believing in God, do believe in ETIs, uniformly portrayed as higher intelligences who, having survived what might be a tendency in species toward self-destruction once advanced technologies are created, must also be morally superior. To the extent that religion involves belief in and hope for transcendence or transcendent beings, SETI is a high-cultural form of religion, and UFOs a low-cultural form of religion.
The Measure Of A Life: Carl Sagan and the Science of Biography http://www.theeway.com/skepticc/newsworthy06.html
P.S. I was very much a child of Sagan and SETI! I was 15 when Cosmos aired, and read every Sagan book I could get my hands on, got a large telescope, became obsessed with astronomy for years... Reading about this religious dimension years later surprised me, it had never occurred to me. (My family was atheist)
[David Swift in his 1990 book SETI Pioneers] asked each of the SETI pioneers about their parents’ religiosity... most were raised in a religious household but that not one believes in anything like the traditional Judeo-Christian God... Astronomer Frank Drake, ostensively the SETI pioneer if there was one (and creator of the infamous “Drake equation” for computing the probability of ETIs), who was raised “Very strong Baptist. Sunday school every Sunday,” made this observation: “A strong influence on me, and I think on a lot of SETI people, was the extensive exposure to fundamentalist religion. You find when you talk to people who have been active in SETI that there seems to be that thread. They were either exposed or bombarded with fundamentalist religion. So to some extent it is a reaction to firm religious upbringing”. Similarly, John Kraus recalled: “We were very strong churchgoers, members of the Methodist church. I was brought up in a very religious atmosphere…there was never any thought of conflict between science and religion in my thinking or in my upbringing. Science and religion were simply both seeking ultimate truth but using different ways of going at it”. ...
... One might speculate that SETI, as a highbrow, elitist revolution, contains within it quasi-religious and spiritual overtones, in the sense that these scientists, while not believing in God, do believe in ETIs, uniformly portrayed as higher intelligences who, having survived what might be a tendency in species toward self-destruction once advanced technologies are created, must also be morally superior. To the extent that religion involves belief in and hope for transcendence or transcendent beings, SETI is a high-cultural form of religion, and UFOs a low-cultural form of religion.
The Measure Of A Life: Carl Sagan and the Science of Biography http://www.theeway.com/skepticc/newsworthy06.html
P.S. I was very much a child of Sagan and SETI! I was 15 when Cosmos aired, and read every Sagan book I could get my hands on, got a large telescope, became obsessed with astronomy for years... Reading about this religious dimension years later surprised me, it had never occurred to me. (My family was atheist)
I have been raised extremely religious and I completely understand obsession by the search for alien life. In some way it would "ground" at once my entire struggle to get out of this (human) religion. Sure, you can imagine an adapted religion cross the universe with multiple Jesuses etc., but it's much less convincing than the original.
Actually, the reason I'm so interested in artificial general intelligence is, I think, driven by the same reasons. If we can create fellow human beings, it somehow is like creating your own aliens on earth. That, and the idea that we need them to solve the tough problem we nowadays face as mankind.
Actually, the reason I'm so interested in artificial general intelligence is, I think, driven by the same reasons. If we can create fellow human beings, it somehow is like creating your own aliens on earth. That, and the idea that we need them to solve the tough problem we nowadays face as mankind.
Not saying you are from that background, but I think any upbringing that beats you over the head with something akin to "who are you going to believe, your deceiving eyes or me?" will prime you for SETI or similar "religion" later in life. That beating over the head could be an abusive parent, boarding school or whatever.
(Not saying most religious practice is abusive or anything. But it can be.)
(Not saying most religious practice is abusive or anything. But it can be.)
Also, if you loved (Sagan's) Cosmos - Dimitri Martin did a spoof version, Our Fascinating Planet, which is absolutely hilarious.
https://www.youtube.com/watch?v=fYo-OdQ-5ic&list=PLRcB4n4CGc...
https://www.youtube.com/watch?v=fYo-OdQ-5ic&list=PLRcB4n4CGc...
I’ve always assumed that was also the inspiration for one of the earliest xkcd’s: https://xkcd.com/10/
I'd never read that analysis of the ending of Contact. Thanks for sharing!
There's a corollary here about the very human nature of seeking to find order in chaos. I'm not sure how to voice it exactly but it cuts to the philosophy of mathematics, especially probability and statistics.
We are beings that seek to attach order and patterns to randomness and noise even when there might be none. And when it is a pattern or recognizable slice of information within something than contains very few, if any of those slices we are astounded and ponder the greater nature of whatever we observe.
We are beings that seek to attach order and patterns to randomness and noise even when there might be none. And when it is a pattern or recognizable slice of information within something than contains very few, if any of those slices we are astounded and ponder the greater nature of whatever we observe.
> it’s basically an expected outcome given what we think we know about pi.
There is a massive gulf between searching deep into random digits to find something, down to completely unimaginable depths, entire universe-fulls of digits discarded...
and having it be right there, near the surface, in one of the most common numbers that exists. The book talks about the latter.
What this page is about is a third option. It's not searching through primes or other math-derived numbers. It's constructing a number that already has a pattern, which is trivial, and then it's searching nearby numbers until it hits a prime.
There is a massive gulf between searching deep into random digits to find something, down to completely unimaginable depths, entire universe-fulls of digits discarded...
and having it be right there, near the surface, in one of the most common numbers that exists. The book talks about the latter.
What this page is about is a third option. It's not searching through primes or other math-derived numbers. It's constructing a number that already has a pattern, which is trivial, and then it's searching nearby numbers until it hits a prime.
Reminds me of this classic number: https://en.wikipedia.org/wiki/Illegal_prime
Basically: DeCSS source code (illegal) → compress → pad → add constant to make it prime.
Basically: DeCSS source code (illegal) → compress → pad → add constant to make it prime.
If I ever get a tattoo, I think it's going to be of that.
That article talks about specious attempt to hack the legal system, by claiming information can never be legally restricted because it can encode numbers, but doesn't say the result of the attempt.
Copyright does make numbers illegal. I think it is less about "hacking" the legal system, and more about demonstrating how nonsensical it is.
Which it doesn't actually do. Whatever you think of copyright law, the nonsense lies in our contradictory intuition that information is "special" and numbers, even large ones, aren't. But beyond about, oh say, 128 bits[1], numbers take on all the properties we expect of "special" information.
I can, for instance, encode a picture of you doing something embarrassing as a very large prime[2] number. Yet my protest of "it's just a prime number, bro!" isn't likely to calm you when I start passing it around to all your friends. Information is information. It's not unreasonable to have rules about the flow of information, however cleverly you've encoded it.
[1] https://qntm.org/number [2] The primality is of course totally irrelevant, but it makes it seem more "mathy"
I can, for instance, encode a picture of you doing something embarrassing as a very large prime[2] number. Yet my protest of "it's just a prime number, bro!" isn't likely to calm you when I start passing it around to all your friends. Information is information. It's not unreasonable to have rules about the flow of information, however cleverly you've encoded it.
[1] https://qntm.org/number [2] The primality is of course totally irrelevant, but it makes it seem more "mathy"
[deleted]
Half a year ago I made the same idea but with colour: http://www.pinchofintelligence.com/painting-by-prime-number/. It's interesting that we both took the Mona Lisa to visualise the concept :)
I was sure that the original inspiration for this would be this [0] comic and reddit post from 2015, about a 4096-bit prime number that looks like a giraffe [1].
[0] https://www.reddit.com/r/math/comments/7qpfls/does_there_exi...
[1] A reddit commenter also found a "minimalist giraffe": 7.
[0] https://www.reddit.com/r/math/comments/7qpfls/does_there_exi...
[1] A reddit commenter also found a "minimalist giraffe": 7.
That comic was oddly apropros. I just messaged my father explaining what a perfect number is (He'd asked me because of a question on a game show). That comic made for a great footnote.
Usecase: In future when computers become intelligent and we(humans) want to communicate without computers understand, we can use this means :)
This would make a great conspiracy theory - that Mona Lisa was a prime number painted by Leonardo.
what if instead we have an approximate representation of an image through a highly composed number? we end up with a number theoretic compression technique.
How on earth did they verify a 30k long number is prime?!?
Perl's regex engine is really fast, so presumably:
perl -lne '(1x$_) =~ /^1?$|^(11+?)\1+$/ || print "$_ is prime"'What are the image errors?
Explanation from an article referenced by the linked article[1]:
Most of the digits were fixed while the rest could be brute-forced using some useful properties.
[1] https://www.futilitycloset.com/2017/09/10/trinity-hall-prime...
Most of the digits were fixed while the rest could be brute-forced using some useful properties.
[1] https://www.futilitycloset.com/2017/09/10/trinity-hall-prime...
From the link:
> approximately one in every 6200 2688-digit numbers is prime.
So if you're lucky, you only need to brute force the last 4 digits! Maybe 5 if you're unlucky. In either case, that's a lot less work than I imagined. And of course you can skip all the even numbers.
> approximately one in every 6200 2688-digit numbers is prime.
So if you're lucky, you only need to brute force the last 4 digits! Maybe 5 if you're unlucky. In either case, that's a lot less work than I imagined. And of course you can skip all the even numbers.
Kinda more 'primes from images' (w/a tiny area that can't be used) than 'images from primes'. Still cool though!
How did you get 4 digits? Wouldn't that mean 1 in every 2^4 = 16 is prime? For 1 in every 6200 shouldn't it be 12 digits?
You can generate these from any image here:
https://geonnave.github.io/primg/
Pretty cool although it struggled with certain very basic 2d images.
[deleted]
Wow. I feel like the fact that you can encoding arbitrary information in long numbers is such a far reaching concept in math/computer science, it's really satisfying to see it demonstrated in such an intuitive way.
Dimensions can always be compressed and uncompressed.
Naturals: https://en.wikipedia.org/wiki/Pairing_function
Reals: https://en.wikipedia.org/wiki/Space-filling_curve
The caveat is that a function, like the evolution of the universe, General Relativity, differential equations, would be possibly unwieldy and unaesthetic when written on lower dimensions, and locality might also be lost.
Some techniques try to preserve locality:
https://en.wikipedia.org/wiki/Z-order_curve
The takeaway is that any object, nomatter how complex, can be represented as a single number. That is the basis of Godel Numbering: https://en.m.wikipedia.org/wiki/G%C3%B6del_numbering
Naturals: https://en.wikipedia.org/wiki/Pairing_function
Reals: https://en.wikipedia.org/wiki/Space-filling_curve
The caveat is that a function, like the evolution of the universe, General Relativity, differential equations, would be possibly unwieldy and unaesthetic when written on lower dimensions, and locality might also be lost.
Some techniques try to preserve locality:
https://en.wikipedia.org/wiki/Z-order_curve
The takeaway is that any object, nomatter how complex, can be represented as a single number. That is the basis of Godel Numbering: https://en.m.wikipedia.org/wiki/G%C3%B6del_numbering
Replying to the dead comment by saschag:
Respectfully, your argument just boils down to whether the real numbers actually "exist." And I airquote exist because even that term is loaded.
This HN delved into it: https://news.ycombinator.com/item?id=14080024
It really just boils down to the nature of incompressible infinities.
You may enjoy this video that explores some of the issues with unresolvable infinities:
https://youtu.be/Szd6RBsWntg
Respectfully, your argument just boils down to whether the real numbers actually "exist." And I airquote exist because even that term is loaded.
This HN delved into it: https://news.ycombinator.com/item?id=14080024
It really just boils down to the nature of incompressible infinities.
You may enjoy this video that explores some of the issues with unresolvable infinities:
https://youtu.be/Szd6RBsWntg
[deleted]
The entire Library of Babel is encoded in Pi.
https://en.wikipedia.org/wiki/The_Library_of_Babel
https://en.wikipedia.org/wiki/The_Library_of_Babel
This assumes that pi is a normal number [0], a fact that is widely believed but has not been proven.
[0]: https://en.wikipedia.org/wiki/Normal_number
[0]: https://en.wikipedia.org/wiki/Normal_number
So cool, you can find anything you search for: https://libraryofbabel.info/bookmark.cgi?concernedcoder0001 about 1/2 way down the page you can find: "concerned coder is a programmer living in the
sourthern usa, playing a game called eve online while reading hacker news on a
sunday night in january"
Hmm. Other sources suggest that Concerned Coder is a programmer living in the northern USA, playing a game called Eve Online while reading Hacker News on a Sunday night in January:
https://libraryofbabel.info/bookmark.cgi?concernedcoder00001...
https://libraryofbabel.info/bookmark.cgi?concernedcoder00001...
[deleted]
you can encode any arbitrary information into a one dimensional value....
eg: a large enough number can encode the whole universe....
But decoding any meaningful information has to be at least in two dimensions....
In two dimensions, you can describe everything.... the other dimensions are not needed (and perhaps just emerging, according to the holographic principle)....
But decoding any meaningful information has to be at least in two dimensions....
In two dimensions, you can describe everything.... the other dimensions are not needed (and perhaps just emerging, according to the holographic principle)....
> But decoding any meaningful information has to be at least in two dimensions....
What does this mean?
What does this mean?
It's the uncertainty principle and principle of orthogonal observables. Energy vs time for example. You need two dimensions for a comparison. One dimension is static.
1GB of storage is a single number with 2^8billion binary digits.
Everything we do in computers is encoding information in long numbers. Every character is a single number, every file is, every disk image is, every state of RAM, every database, every cache, every piece of source code.
Everything we do in computers is encoding information in long numbers. Every character is a single number, every file is, every disk image is, every state of RAM, every database, every cache, every piece of source code.
Not encoded as, but can
be interpreted as.
Any precisely specified object can be interpreted as a number.
[deleted]
Reminds me of a thought I had a while back that given sufficient computational power you could describe any dataset using only two place values in an irrational number and an interpretation rule. For example, the complete data for an h265 copy of Avengers Endgame exists somewhere in the digital expression of the value of Pi. It might be googleplexes of digits deep, but it's there somewhere.
The problem is that the index itself becomes so large, even you use a dataset-optimised number instead of pi, that it's much worse than just storing the original data.
Oh certainly. I was just thinking of it as a way to get around intellectual property laws.
Only if that irrational number is also normal (https://en.wikipedia.org/wiki/Normal_number), which pi has not been proven to be.
In addition, even if a normal number was used, it's far simpler to describe the data by just using a single number alone. For example, a binary encoding of the data (perhaps using a prefix-free code). Using a normal number and two "positions" is just more complicated.
Nonetheless, it's freaky that our deepest secrets are encoded into pi. If pi is normal.
Also, there will be multiple copies of data, some uncompressed, some compressed in different formats like gzip, lzo, etc.
And each copy will occur infinitely often.
And man there is a hell of a lot of fake news in there.
This is yet another case where "prime" is bolted onto something for no particular reason to make it superficially more interesting. IMO this confused mathematical understanding.
Approximately 1/n of all n-bit pieces of data (including bimaps) are prime.
Approximately 1/n of all n-bit pieces of data (including bimaps) are prime.
It's like a magic trick. Amazing at first, then you sort of realize how they did it.
If you take a binary image, of length n bits, then the probability of some single bit flip producing a prime, is approximately 1 - (1 - 1/ln(2^n))^n ~ 0.76. Allowing 2 bit flips makes finding a prime as good as certain.
If you take any binary image, of length n bits, then the probability of some single bit flip producing a prime, is approximately 1 - (1 - 1/ln(2^n))^n ~ 1 - e^{-1 / ln(2)} ~ 0.76.
Semi-related, but reading this article and thinking about it made me wonder if there is any study at all of "gray code" primes, for lack of a better word.
Basically, prime numbers that differ by exactly one binary digit in their representation.
Probably nothing about that relationship that would be interesting enough to look into beyond just "I ran some calculations and found these numbers that fit the pattern"
Basically, prime numbers that differ by exactly one binary digit in their representation.
Probably nothing about that relationship that would be interesting enough to look into beyond just "I ran some calculations and found these numbers that fit the pattern"
This is just a weaker version of the twin prime conjecture. You’re asking for primes that differ by 2^k instead of 2. Last I heard the best result was from Polymath 8a.
http://michaelnielsen.org/polymath1/index.php?title=Bounded_...
Edit: Actually I was wrong, differing by a binary digit is much stronger than a difference of 2^k. But that’s a starting point.
http://michaelnielsen.org/polymath1/index.php?title=Bounded_...
Edit: Actually I was wrong, differing by a binary digit is much stronger than a difference of 2^k. But that’s a starting point.
Neat. Thanks for tying it in to something real. Makes sense now that you phrase it that way. Not something I've ever looked into much.
Actually I replied without thinking too much, sorry... Your question is (probably a fair bit) stronger than the one I related to. Edited.
Big side note, but what you just exhibited is one of my favorite things about this community: admitting being wrong.
It wasn’t really until the workplace where I encountered level-headed people that would just shrug their shoulders and say “You are right. I was wrong” and then move on.
It’s so simple, but is amazingly powerful.
It wasn’t really until the workplace where I encountered level-headed people that would just shrug their shoulders and say “You are right. I was wrong” and then move on.
It’s so simple, but is amazingly powerful.
To take it a little further, what I was even more specifically interested in was a sequence of primes following the principle of a gray code [1] where each subsequent prime would differ from the previous prime by precisely one bit.
So basically, what is the longest sequence of primes you could find following that pattern?
[1] https://en.wikipedia.org/wiki/Gray_code
So basically, what is the longest sequence of primes you could find following that pattern?
[1] https://en.wikipedia.org/wiki/Gray_code
We discussed a similar thing a couple of years ago: https://news.ycombinator.com/item?id=16192608
Here's a prime smiley face (with code) I generated at the time: https://news.ycombinator.com/item?id=16192922
Here's a prime smiley face (with code) I generated at the time: https://news.ycombinator.com/item?id=16192922
Mostly unrelated but this made me check to see if the Prime Number Shitting Bear is still online. It is! https://alpha61.com/primenumbershittingbear/
The classic prime joke (saw it originally in Sci Am back in the ... 70's? 80's?). Found an approximation when I googled it:
A mathematician, physicist, and engineer are taking a math test. One question asks "Are all odd numbers prime?"
The mathematician thinks, "3 is prime, 5 is prime, 7 is prime, 9 is not prime -- nope, not all odd numbers are prime."
The physicist thinks, "3 is prime, 5 is prime, 7 is prime, 9 ... experimental error, 11 is prime, 13 is prime, yes, they're all prime."
The engineer thinks, "3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is prime, ..."
A mathematician, physicist, and engineer are taking a math test. One question asks "Are all odd numbers prime?"
The mathematician thinks, "3 is prime, 5 is prime, 7 is prime, 9 is not prime -- nope, not all odd numbers are prime."
The physicist thinks, "3 is prime, 5 is prime, 7 is prime, 9 ... experimental error, 11 is prime, 13 is prime, yes, they're all prime."
The engineer thinks, "3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is prime, ..."
Yes, and the programmer thinks: "3 is prime, 5 is prime, 7 is prime, 9 is not prime, 9 is not prime, 9 is not prime, …"
> The engineer thinks, "3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is prime, ..."
Surely the engineer would round it to the nearest power of ten and thus discount all of the numbers?
Surely the engineer would round it to the nearest power of ten and thus discount all of the numbers?
[deleted]
Help with the joke? I understood the mathematician and the physicist, but not the engineer. What stereotype is being invoked?
The version I remember has the mathematician thinking: "3 is prime, 5 is prime, 7 is prime, so by mathematical induction, all odd numbers are prime".
It just occurred to me how strange it is that you can get to some numbers by addition that you cannot get to by multiplying any subset of the earlier sequence. Emotionally, it feels like addition and multiplication are arguing over who's better, and multiplication is like "I'm so fast", and addition is like, "I'm slow but, I can go places you can't".
It'd be cool, if there was a Maker, that they make it so that some very large prime number is a message to all intelligent life capable of computing and deciphering it. This kind of message would penetrate even nested, simulated universes, and could only come from World 0, assuming the properties of numbers are independent of physical constants. Why not have a SETI-in-the-primes project, after all?
It'd be cool, if there was a Maker, that they make it so that some very large prime number is a message to all intelligent life capable of computing and deciphering it. This kind of message would penetrate even nested, simulated universes, and could only come from World 0, assuming the properties of numbers are independent of physical constants. Why not have a SETI-in-the-primes project, after all?
> It'd be cool, if there was a Maker, that they make it so that some very large prime number is a message to all intelligent life capable of computing and deciphering it
Every possible message is already there. Just like how Borges’ Library of Babel contains every possible book (within its limits of size and format)
Every possible message is already there. Just like how Borges’ Library of Babel contains every possible book (within its limits of size and format)
> Just like how Borges’ Library of Babel contains every possible book (within its limits of size and format)
You're welcome to look around for messages here: https://libraryofbabel.info/
I don't know if anyone has ever found one, though.
You're welcome to look around for messages here: https://libraryofbabel.info/
I don't know if anyone has ever found one, though.
That cannot be true. It does not contain the message '4'. (Or any of the non-primes.)
In fact it seems like there must be many more non-primes than primes over any finite interval (for the simple reason that multiplication gets a lot of whacks at the piñata, e.g. producing a product landing in that finite interval.)
So to answer your implied question ("why bother commucating with primes anwyay?") I guess the value of limiting your message to "a really big prime number" is to make discovery hard, but still tenable. It should be pretty big, like big enough for a good bible sized book, say 1 gigabyte, and start with something really obviously artificial, or unexpected looking, like starting as a 1 with 20,000 zeroes, or maybe better, 20k perfect 010101 and then after a few thousand, 00110011, and from there establish a language protocol, and write the book. But you'd have to expect people to check only primes for these simple patterns, because it's really easy to produce meaningful sequences with addition, and really hard with multiplication (AFAIK).
In fact it seems like there must be many more non-primes than primes over any finite interval (for the simple reason that multiplication gets a lot of whacks at the piñata, e.g. producing a product landing in that finite interval.)
So to answer your implied question ("why bother commucating with primes anwyay?") I guess the value of limiting your message to "a really big prime number" is to make discovery hard, but still tenable. It should be pretty big, like big enough for a good bible sized book, say 1 gigabyte, and start with something really obviously artificial, or unexpected looking, like starting as a 1 with 20,000 zeroes, or maybe better, 20k perfect 010101 and then after a few thousand, 00110011, and from there establish a language protocol, and write the book. But you'd have to expect people to check only primes for these simple patterns, because it's really easy to produce meaningful sequences with addition, and really hard with multiplication (AFAIK).
> That cannot be true. It does not contain the message '4'. (Or any of the non-primes.)
Any finite message (containing a finite number of symbols drawn from a finite alphabet) can be represented as a positive integer.
Any positive integer n can be encoded in a prime, even a composite integer.
Use the following encoding system: write 1 n times, followed by a zero, followed by an arbitrary bit string.
For example, for 4: 11110xxxxxxxxxxxxx...
Using that encoding system, there will be an infinite number of primes that encode 4 - all the primes which start with 11110 in binary.
Thus, the set of all primes contains an infinite number of copies of every possible finite message.
Any finite message (containing a finite number of symbols drawn from a finite alphabet) can be represented as a positive integer.
Any positive integer n can be encoded in a prime, even a composite integer.
Use the following encoding system: write 1 n times, followed by a zero, followed by an arbitrary bit string.
For example, for 4: 11110xxxxxxxxxxxxx...
Using that encoding system, there will be an infinite number of primes that encode 4 - all the primes which start with 11110 in binary.
Thus, the set of all primes contains an infinite number of copies of every possible finite message.
I meant that the entire message is "4", not just part of the message. Obviously we can pick a subset of digits of any large prime and find anything we want. However, the odds of a very large prime (like a gigabyte) looking intentionally ordered over its entire length seems vanishingly small.
The only reason to limit ourselves to primes is because its trivial to produce a meaningful composite, and very difficult to produce a meaningful prime. Take this message; if I was to associate it with a number (say by joining its characters as 7-bit ASCII), my money is that it's composite. (Not sure what the odds are, but I'd take 100:1 odds).
EDIT: period is `01110`, which is even, so I win.
The only reason to limit ourselves to primes is because its trivial to produce a meaningful composite, and very difficult to produce a meaningful prime. Take this message; if I was to associate it with a number (say by joining its characters as 7-bit ASCII), my money is that it's composite. (Not sure what the odds are, but I'd take 100:1 odds).
EDIT: period is `01110`, which is even, so I win.
> However, the odds of a very large prime (like a gigabyte) looking intentionally ordered over its entire length seems vanishingly small.
Can we estimate how many gigabyte sized primes exist? I think one can do that using the prime number theorem. Let’s call that N. What is the probability one of those N messages is meaningful? I think it is a lot higher than you think it is. I think N is a very big number, even though it is very small compared to the number of composite gigabyte-sized numbers, it is still unimaginably large in absolute terms.
Can we estimate how many gigabyte sized primes exist? I think one can do that using the prime number theorem. Let’s call that N. What is the probability one of those N messages is meaningful? I think it is a lot higher than you think it is. I think N is a very big number, even though it is very small compared to the number of composite gigabyte-sized numbers, it is still unimaginably large in absolute terms.
PNT, interesting! If I'm reading it correctly you can estimate the number of N digit primes as 10^N/N. That's basically 10^N, and for N=9 (a billion), that means there's (very very roughly) a billion primes with a billion digits.
I mean, it's not that many if your expecting a message from God (I say half-jokingly).
I mean, it's not that many if your expecting a message from God (I say half-jokingly).
Suppose somewhere out there, there is an ISO of Bible software, and it just so happens that when expressed as an integer it turns out to be prime – proof that the Bible is God's word, or freak coincidence? I think most people would go with the second option. And, the same would be just as true if it was an ISO of some other religious scripture, such as the Quran or the Vedas.
Well it would be an impressive feat, regardless. But of course there are a lot of degrees-of-freedom if you were to attempt this. Tiny formatting and encoding decisions would all greatly influence the resulting integer. Because it's so sensitive to chosen input, I would say even if you managed to produce a prime, it's not very satisfying as a sort of Godly checksum and signature.
Much more interesting is to discover a new communication, a message encoded in a very large number that is distinguished by being prime. (What message would you send? It would be interesting if it ultimately described some sort of recursive, reactive automata, the source code for a kind of learning, communicating intelligence. A gift, then. An awesome, terrible gift.)
Much more interesting is to discover a new communication, a message encoded in a very large number that is distinguished by being prime. (What message would you send? It would be interesting if it ultimately described some sort of recursive, reactive automata, the source code for a kind of learning, communicating intelligence. A gift, then. An awesome, terrible gift.)
> Why not have a SETI-in-the-primes project, after all?
Sure, it can run alongside SETI-in-the-burn-marks-on-toast and SETI-the-flour-spilled-on-the-table projects.
Sure, it can run alongside SETI-in-the-burn-marks-on-toast and SETI-the-flour-spilled-on-the-table projects.
that's not mathematical induction though. it's what philosophers call "induction", i.e. building theories out of empirical observations (as opposed to deduction; mathematical induction is weirdly named because it's actually purely deductive)
You heard that in your engineering course.....
Surely the mathematician would think “if all odd numbers were prime then the Riemann hypothesis would be trivially false, so obviously they cannot be”.
That's a mouse.
[deleted]
But in fact, it’s basically an expected outcome given what we think we know about pi.
At first glance these images were startling to me; that such recognizable images could be “hidden” in the primes... in the very structure of mathematics! But then I realized that with an infinite numbers of primes available to us, nothing is hidden. It’s more like the primes are simply building blocks for us to use in constructing images of whatever we want.