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, ..."
Surely the engineer would round it to the nearest power of ten and thus discount all of the numbers?
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?
Every possible message is already there. 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.
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).
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.
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.
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.
I mean, it's not that many if your expecting a message from God (I say half-jokingly).
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.)
Sure, it can run alongside SETI-in-the-burn-marks-on-toast and SETI-the-flour-spilled-on-the-table projects.
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.
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.
> as Sagan puts it in the story itself, the surprise is not that it appears that it appears "so early" in the sequence.
[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)
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 most religious practice is abusive or anything. But it can be.)
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?
You’re welcome to devote time to trying to discover them...
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.
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?
If pi is normal (as it is conjectured to be), then yeah it has to.
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?
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.
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.
Don't get carried away with pi mysticism - all this stuff is also true of the concatenation of all integers in order (0123456789101112131415...).
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
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.
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.
Basically: DeCSS source code (illegal) → compress → pad → add constant to make it prime.
I can, for instance, encode a picture of you doing something embarrassing as a very large prime 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.
 The primality is of course totally irrelevant, but it makes it seem more "mathy"
Most of the digits were fixed while the rest could be brute-forced using some useful properties.
> 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 1/n of all n-bit pieces of data (including bimaps) are prime.
 A reddit commenter also found a "minimalist giraffe": 7.
Here's a prime smiley face (with code) I generated at the time: https://news.ycombinator.com/item?id=16192922
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"
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.
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.
So basically, what is the longest sequence of primes you could find following that pattern?
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:
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
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:
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:
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)....
What does this mean?
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.
perl -lne '(1x$_) =~ /^1?$|^(11+?)\1+$/ || print "$_ is prime"'