Slashdot Mirror
Mathematicians Discover Prime Conspiracy (quantamagazine.org)
An anonymous reader writes with an intriguing story at Quanta Magazine, which begins: Two mathematicians have uncovered a simple, previously unnoticed property of prime numbers — those numbers that are divisible only by 1 and themselves. Prime numbers, it seems, have decided preferences about the final digits of the primes that immediately follow them. Among the first billion prime numbers, for instance, a prime ending in 9 is almost 65 percent more likely to be followed by a prime ending in 1 than another prime ending in 9. In a paper posted online today, Kannan Soundararajan and Robert Lemke Oliver of Stanford University present both numerical and theoretical evidence that prime numbers repel other would-be primes that end in the same digit, and have varied predilections for being followed by primes ending in the other possible final digits. "We've been studying primes for a long time, and no one spotted this before," said Andrew Granville, a number theorist at the University of Montreal and University College London. "It's crazy."
https://www.quantamagazine.org...
7 did it.
It's the same 300 digit number to his luggage!
Stop anthropomorphizing prime numbers. They hate that!
Only 65%? Pft. In base 2, every prime number is 100% likely to be followed by a prime ending in 1.
"We've been studying primes for a long time, and no one spotted this before," said Andrew Granville, a number theorist at the University of Montreal and University College London. "It's crazy."
I can tell you that it's not crazy, the information has simply been occulted ("occult" means to hide). Why do you think RSA selects two consecutive prime numbers? The answer is known to the NSA, and now you do too.
I bet you think that we actually thought there would be WMDs in Iraq, that we couldn't have stopped 9/11, and that we didn't know it was strategically folly to deploy such a fleet in close quarters in Perl Harbor, meanwhile embargoing Japan...
Besides, "it's crazy" to think otherwise, eh?
>Two mathematicians have uncovered a simple, previously unnoticed property of prime numbers — those numbers that are divisible only by 1 and themselves.
Did anyone else LOL when they read the first sentence. My first thought was who wouldn't notice primes are only divisible by 1 and themselves it's the definition, duh.
I wonder if this has anything to do with Twin primes. If a prime ends in 9, then its twin will end in 1, and so we should expect primes ending in 9 to more often be followed by primes ending in 1. The number of twin primes is believed to be infinite, but they get more sparse as you go towards infinity (proportional to 1/(ln(n)^2)), even faster than primes (proportional to 1/ln(n)), so if they are responsible for the bias, then the bias should diminish as you go up.
I'll do one better than that.
I'm working on a formula to predict various pieces of prime numbers and have spotted a pattern I cannot yet identify which allows me to quickly discern by human eye whether the number is prime or not...
I think we should move off of prime numbers as cryptographic trap doors.
As a later time-stamped proof of my work, I'd like to provide a hash of a number sequence which proves I understand this concept in case anyone else beats me to publishing.
1,256
1,2,4,256
1,4,8,256
(....Skip 40 iterations)
1,4,8,16,32,64,128,256
1,8,512
And a hash of the code that generates this sequence....
2e61492abdc45b37811fb2ce64c2c41d5a60522cdf8f357419f37a2cdabfb94d
I'll see you all in the future.
The Kennedys? Or Jimmy Hoffa?
“He’s not deformed, he’s just drunk!”
Take other, random sequences of integers with the same density within the integers. I wouldn't be surprised if you find similar anomalies.
Get off my lawn! says prime number to its siblings.
present both numerical and theoretical evidence that prime numbers repel other would-be primes that end in the same digit, and have varied predilections for being followed by primes ending in the other possible final digits.
Everything I write is lies, read between the lines.
Hi all, your input please on this paragraph in the linked article:
"Soundararajan was drawn to study consecutive primes after hearing a lecture at Stanford by the mathematician Tadashi Tokieda, of the University of Cambridge, in which he mentioned a counterintuitive property of coin-tossing: If Alice tosses a coin until she sees a head followed by a tail, and Bob tosses a coin until he sees two heads in a row, then on average, Alice will require four tosses while Bob will require six tosses (try this at home!), even though head-tail and head-head have an equal chance of appearing after two coin tosses."
This seems wrong to me. Both Alice and Bob have equal chance of rolling a head, hence on average they will need the same number of tries to arrive at a head toss; and since coins dont have memory, the next toss has equal chance of being head or tail. So I do expect the chances of head head and head tail to be the same.
This is how I see it, the statement above came from a mathematician so I am probably making a mistake in my reasoning but I don't see where.
Any input?
After a prime ending in 2 or 5, there has to be at least a billion primes before another one can end in 2 or 5.
Shachar
By the general nature of extremely basic things in mathematics, shouldn't "almost 65%" actually be a number equal to some sort of constant or famous sequence? Or there's a pattern with the 2nd to last digit then 3rd to last digit etc that assembles some sort of other known constant. Since prime numbers are sort of like a constant and there's a lot of constant crossover between equations and each other, you would think something like the Fibonacci sequence or other common constant would show up in a situation like this. That or another prime number.
... or base 16, or base 7, or base 64, for that matter?
Will they still exhibit the 'twin prime' / 'prime number conspiracy' phenomena?
This seems wrong to me. Both Alice and Bob have equal chance of rolling a head, hence on average they will need the same number of tries to arrive at a head toss; and since coins dont have memory, the next toss has equal chance of being head or tail. So I do expect the chances of head head and head tail to be the same.
Yes, it's called a veridical paradox. That's something that seems impossible but is nonetheless true. You can verify it by flipping a coin, or running a computer simulation using a good random number generator.
If I can be modded down for being a troll, can I be modded up for being an orc, or a balrog?
What's this base 1010 drama? Everyone knows in binary ALL primes end in "1".
Jokes aside, the fact that there's plenty of bases to choose from means that what they are really talking about is the modulo remainders of primes having a pattern- and modulo division and primes have had a pretty flirty relationship. Unquestionably interesting. The thing with the prime number set is that it's immutable- a set of fixed numeric stars shining the same light since before time began, and yet even with that constancy, many functions involving the prime number web have proven frustrating to calculate for large values- there's hardly any shortcuts compared to the integer math you run into on a daily basis.
But we should be able to calculate this instead of trying it. So I understand where my error is.
Everyone with at least a passing interest in cryptography and computer security does. Primes is basically what we rely on in these fields.
Quite seriously, every time someone comes up with a claim that something can be done "more easily", "more efficiently" or generally "faster" in a field that remotely touches on prime numbers, you can see the ripples in the fabric of spacetime from cryptographers shaking in their boots.
We used to have a Bill of Rights. Now, with the rights gone, all we have left is the bill.
If Alice and Bob both fail after getting their first head, (Alice gets a head, and Bob gets a tail) then Alice can still succeed on her next flip by getting a tail, but Bob has to get a head again before he has another chance. So Bob's failure costs him more.
Of course. Thanks !
Last time I looked at primes in binary I noticed a 100% chance that the next one ended in 1. No I am not trolling you I'm just making a point, go look at the primes in different bases and see what you notice.
Intuitively it makes sense. Assume the first H has been tossed. For Alice, she fails by tossing another H. However, this second H can be the first H of a successful HT sequence, so in failure there is a silver lining - she's halfway to success and can stop after tossing a single T. Full sequence: HHT.
For Bob, after tossing the first H, tossing a T means he has to start over. He needs to toss another H first, followed by yet another H to succeed. His task is harder. Full sequence: HTHH.
yes, I get it completely now. thanks.
And can we establish a university department to run courses challenging it? I get to be the overpaid professor in charge as I thought of the idea, but I'm sure that there will be plenty of teaching posts focusing on the need to avoid such an elementary form of discrimination...
Of course a prime ending in 9 will most often be followed by a prime ending in 1.
Primes are more-or-less "random": you can't easily predict the next prime. In every number-range primes have a certain density, and that density drops as numbers get larger. So "around 1000", the prime-density is higher than "around 10000".
So assuming the prime density is P and we have a prime p ending in nine, there is a P chance of p+2 (ending in 1) being prime. Then there (1-P)P chance of the next candidate being prime. This is a smaller number. The next number CANNOT be prime because it is divisible by five. Anyway, the chance of the next prime being p+10 is on the order of (1-P)^4.P.
Because the prime density is not all that low, even for numbers around a million, the fourth power of 1-P becomes small quickly.
Note that I'm using an adjusted prime density here. If there are x primes per stretch of 100 numbers on the number line, you have a prime density of x/100. The P I'm dealing with is only considering the 4-mod 10 options for primes. So P = 10/4. x/100 .
I wonder how many already stumbled upon this and just assumed that it must be already mentioned somewhere.
For instance if I noticed that the probability of a prime ending in a 9 went up and down in a sign wave over the first billion primes, I would again just assume that this was a well known fact and move on.
So I wonder how many of these previously ignored discoveries are going to be dusted off now that people have been reminded that there are fundamental discoveries still unclaimed with primes. Also I wonder how many people are going to take a quick look at the simpler end of primes for more of these unclaimed discoveries.
I'm wondering if this isn't merely a correlation to Benford's law being applied to the prime set. IANAM (not a mathematician) but this kind of pattern in primes doesn't seem to be particularly counter-intuitive to me on the face of it.
This comment was written with the intention to opt out of advertising.
The AC intuitive explanation is correct, and you can calculate it by drawing the tree.
After 4 rolls, I get that Alice probability to succeed is 11/16 (1/4 for HT, 1/8 for HHT and THT, 1/16 for HHHT, THHT and TTHT), while Bob probability to succeed is 8/16 (1/4 for HH, 1/8 for THH, 1/16 for HTHH and TTHH)
I have discovered a truly marvelous proof of killer sig, which this margin is too narrow to contain.
Yup, I got 4.00171 for "HT" and 5.999467 for "HH" after a million iteration.
Fun stuff!
No, they don't. 10 in binary is prime.
Another way to see it is to look at the pattern formed by a completed sequence.
For Alice, it is T* H+ T.
For Bob, it is T* H (T+ H)* H.
I have discovered a truly marvelous proof of killer sig, which this margin is too narrow to contain.
Yep, exactly. Specifically, the fact that it's extremely difficult to determine the factors of large prime numbers is the basis for a lot of cryptography - part of the "hard problem" required for any algorithm, where it's simple to compute in one direction, but extremely difficult to determine the components that led to that result. If someone tomorrow discovered a way to do this, it would immediately destroy a lot of our current crypto tech overnight. It wouldn't be an over-exaggeration to call that particular property of primes one of the linchpins of modern crypto.
Note that that elliptic curve crypto, a more recent approach, doesn't rely on prime factorization. As it's name suggests, it relies on properties of elliptic curves for its one way "hard problem" rather than factorization - it turns out that this is a more efficient approach for smaller key lengths. Not that anyone expecting someone to discover a simple prime factorization algorithm in the near future, but it's certainly nice to have alternative approaches.
Irony: Agile development has too much intertia to be abandoned now.
Just to entice some kids onto my lawn, I'll point out that my favorite twin primes are a good example of this. Once you meet Jenny it's hard to forget her. Linky
On the one hand you take life too seriously, and on the other, you do not take playful existence seriously enough. Seth
the fact that it's extremely difficult to determine the factors of large prime numbers is the basis for a lot of cryptography
I think you might have jumbled your words.
It's exceptionally easy to determine the factors of any large prime number because there are only two; the number one the number itself. Determining the prime factors of a large, non-prime number, on the other hand, is a challenge.
It would be most unlikely to find an even prime greater than two :)
I imagine the number theorist in a shower cap screaming "it's crazy as hell!".
http://stream1.gifsoup.com/vie...
You are welcome on my lawn.
Prime numbers are interesting. If you don't agree, well, fuck off. ;)
I do not want your cheap brainburning drugs. They are useless for work. And I am a working man today.
10 = prime
:)
I do not want your cheap brainburning drugs. They are useless for work. And I am a working man today.
Whoops, of course that's what I meant, darn it - thanks for the correction.
Irony: Agile development has too much intertia to be abandoned now.
Fascinating. Does that particular paradox have a name? It reminds me of Monty Hall's game paradox.
Singularity: a belief in the "God" idea with the "demiurge" relation inverted.
You missed the absolutely critical corollary that restores balance to the force: after Bob succeeds, he's already halfway to his next success where after Alice succeeds, she needs to snooze for one toss before she's back in the game, where apparently the game involves some gender-swap role play.
It's so totally male to cease thinking the problem through after attaining the initial success condition.
I think I could teach a very interesting grade XI math class.
Corollary: I would end up behind bars.
Not sure if serious...
Open terminal.
Enter: factor 7 && factor 11 && factor 19 && factor 30
Now, note the differences between the first three results and the fourth result.
"So long and thanks for all the fish."
Well, that would have saved me some time. I gotta learn to scroll down before responding. Your answer is more complete than mine. I just sent 'em to the terminal and pointed in the right direction. Prime factorization, by its very nature - a solved problem. Although I did just learn something. It turns out there's some sort of limit as to the number's length in what it will factor in the terminal. I did no know that.
"So long and thanks for all the fish."
Did you know that all prime numbers appear in consecutive digits of pi, along with the complete works of shakespear?
Pick any statistical anomaly and it likely that some of these will appear over some run of an unpredictable series.
Some drink at the fountain of knowledge. Others just gargle.
Your utterly vacuous comment is more stupid. You should've read it.
I do not want your cheap brainburning drugs. They are useless for work. And I am a working man today.
Happy PI Day /.
There is a link. There is always a link. It has been this way for a year (or so) now. It is the domain name listed right next to the title. You can click on it and see. This is not difficult. In fact, I dare say it's obvious. I know it's been about a year because I've been pointing it out (as have many others) for that long. I'm not really sure you should be commenting about stupidity?
"So long and thanks for all the fish."
I wonder how much tax payer money (grants) was wasted on this, unhelpful, discovery?
Perhaps the issue is that we are looking for primes using a base 10 (2x5) system. Perhaps more consistent patterns emerge using binary, trinary, or base 6 (2x3). This is why primes never end in even numbers or 5 (except for 5 itself).
This obsession with base-10 is tiresome. What if you express the numbers in base 17?
Does the statistical aberation go away?
Does it just shift the balance towards "2" from "16" lets say? Both of which are "odd", togetther, in a binary sense 50% of the time.
Or in base-2 where all primes are 1.
Perhaps the pattern that pushes the values in base-10 completely disappears in larger bases.
Perhaps from the certainty of base-2 through base-9 the percentage drop of the apparent biase would show us this is an anomoly of how we express numbers, not the intrinsic mathematics nor apparent numerology-belief of primes some of their searchers.
I don't think so. Elliptic curves?
Best done in prime fields.
No one uses the Koblitz curves. That would be stupid. Oh wait ... Bitcoin.
I should use this sig to advertise my book ISBN-13 : 978-1501515132.
10 is divisible by 1,2, 5, and 10, so how is it prime?
I've fallen off your lawn, and I can't get up.
Not so much anymore since they started using USPS for nearly all shipments. USPS is run by the "Mo" brothers -> Mo-ron and Mo-lasses.
This "discovery" is just ridiculously stupid.
They looked at prime numbers up to a billion. In that range, about one in 20.7 numbers are prime. But if we look only at numbers ending in 1, 3, 7 and 9, about one in 8.3 are prime.
If p ends in 9, then the chance that the next number ending in 1, 3, 7, 9 etc. is a prime is one in 8.3 or about 12.06% for each of these numbers. But the probability that each of them is _the next prime_ changes: p + 2 has a chance of 12.06% of being the next prime. p + 4 has a chance of (0.8794 * 12.06) = 10.61% of being the next prime. p + 6 ends in 5; p + 8 has a chance of (0.8794^2 * 12.06) = 9.33% of being the next prime, and for p + 10 the chance is (0.8794^3 * 12.06) = 8.20%.
Is this true in all bases? There's nothing special about base 10, other than the fact that we have 10 fingers.
There are 11 kinds of women. Those can count and those whose cunt!
* Mixed Metaphor - Check
* Fun with Number - Check
* SJW Bait - Check
What's not to like?
Simple. Alice and Bob must both start by throwing coins until they have a head. They then both have a 50% chance of finishing in the next throw. However, if the next throw is the wrong case, then Alice, who wanted head/tail, has head/head so she has another 50% chance in her next throw. Bob however, who is waiting for head/head, has head/tail so he first has to throw coins again until he gets head before he has another chance of finishing.
This is what happens when somebody tries to use applied math to a pure math problem. Who cares what string patterns you see when you express a prime in a certain base. Primeness has no relationship whatsoever to base.
Oh, wait, now there's 212...never mind...
Have you read my blog lately?
Both Alice and Bob have equal chance of rolling a head
But Henry VIII had a much higher chance of rolling a head.
Have you read my blog lately?
My experience is analogous to yours. We were required to take a foreign language in Junior High. I was assigned to take Spanish, and hated it. All memorization, no principles (I guess there was a principal...).
Then one day I saw a Spanish paradigm, probably the present indicative of hablar (a regular verb, happens to mean "to speak"). But not only was it the paradigm of hablar, it was the paradigm of every other -ar verb in Spanish. (There are two other conjugation classes, but -ar verbs are the majority.) I was astounded--it was *not* all memorization, there were rules! From that day I grooved on Spanish, figured out all the rules I could. And today I am a "fully papered" (to use your term) linguist, and my special interest is inflectional morphology (which includes paradigms).
BTW, there are lots of irregularities in Spanish verbs...but that was to come, and as it turns out, there are rules for the irregulars too.
I wonder how many kids there are out there who don't have this kind of ah-ha! experience, and who never find the sort of thing that they would be good at.
And I wonder what application this might have. Perhaps in determining a crack for encryption? Obviously it is good for giving certain mathematicians something to do.
Self-importance and self-indulgence is the root of ALL evil.
But you don't know that it's prime until you've discovered its factors... (Specifically, that they don't include anything other than itself.)
And proving that a large prime number is in fact prime is actually quite hard. Fortunately, it's not too difficult to very nearly prove it. What actually happens in real-world large-prime crypto is that you run enough statistical tests on the number that the probability of it not being prime becomes lower than the probability of someone just guessing the key with pure luck, or is otherwise not the weakest link in the chain.