What else have we missed about the primes?

March 14, 2016 4:13 AM

Prime numbers, it seems, have decided preferences about the final digits of the primes that immediately follow them.
posted by Proofs and Refutations (37 comments total)

Kinda weird, kinda cool
posted by caddis at 4:22 AM on March 14, 2016

The Universe keeps turning out to be less random than we thought it was... but it doesn't necessarily mean it gets any more orderly.
posted by oneswellfoop at 4:38 AM on March 14, 2016 [4 favorites]

I have a strong feeling that this is related to the Ulam spiral, which also displays apparent patterns among primes.

In the case of the Ulam spiral the answer is distressingly trivial: functions of the form 4n² + bn + c form 45° lines on the spiral, and well-chosen quadratic coefficients produce series of primes that can be quite long: Euler found that n² + n + 41 produces forty consecutive primes for n valued between 0...39. It's worth working through the values to see how the increasing skipping distance avoids composite numbers. Anyway, as I said, I feel that that there's a connection here - that the increased density of primes along quadratic curves favors particular skip distances, which in turn affects the final digit of successive primes.
posted by Joe in Australia at 4:47 AM on March 14, 2016 [2 favorites]

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.

Can anyone explain why this is? I'm baffled.
posted by ultraviolet catastrophe at 5:06 AM on March 14, 2016 [1 favorite]

Tadashi Tokiedo, btw, is a popular guest presenter on Numberphile.
posted by carter at 5:10 AM on March 14, 2016

Can anyone explain why this is? I'm baffled.

It's more about the confusing wording of the phenomenon.
posted by bluefly at 5:19 AM on March 14, 2016 [4 favorites]

Turns out that all the primes went to the same high school in Toledo, and also all have the middle name of Wayne.
posted by Halloween Jack at 5:24 AM on March 14, 2016 [5 favorites]

Can anyone explain why this is? I'm baffled.

Look at the first sixteen numbers in binary, and pretend that the zeroes represent tails, and the ones represent heads. You can see that after four throws, there are two possibilities where nobody wins, three where Bob wins, six where Alice wins, and five where they both win. Alice has an advantage because a head-head combination doesn't preclude her winning on her next throw, while a head-tails combination precludes a win for Bob on his next throw.

 0 = 0000 Nobody wins
 1 = 0001 Nobody wins
 2 = 0010 Alice wins
 3 = 0011 Bob wins
 4 = 0100 Alice wins
 5 = 0101 Alice wins
 6 = 0110 Alice and Bob win
 7 = 0111 Bob wins
 8 = 1000 Alice wins
 9 = 1001 Alice wins
10 = 1010 Alice wins
11 = 1011 Alice and Bob win
12 = 1100 Alice and Bob win
13 = 1101 Alice and Bob win
14 = 1110 Alice and Bob win
15 = 1111 Bob wins

posted by Joe in Australia at 5:26 AM on March 14, 2016 [16 favorites]

As which of us does not?
posted by IndigoJones at 5:47 AM on March 14, 2016

I have a strong feeling that this is related to the Ulam spiral

My instinct is no. In the Ulam spiral, you actually get a different density of primes as you travel along one of those diagonal lines. The phenomenon Robert and Sound are studying doesn't violate equidistribution: in the long run, the proportion of pairs of consecutive primes ending in (1,1) is supposed to be the same as the proportion ending in (1,9) (namely, 1/16) but they find a secondary term creating a deviation from this long-term density, which deviation decays quite slowly, so you can still see it even if you look at the first billion primes or so.
posted by escabeche at 6:01 AM on March 14, 2016 [3 favorites]

Remember: The only even prime is 2. Since it's literally 1 number out of an infinite number of primes, this makes it different. Very different.

One might even call it "odd."
posted by eriko at 6:35 AM on March 14, 2016 [13 favorites]

This is probably a dumb question, but is it possible that this seemingly non-random variation in terminal digits of prime numbers is in any way a consequence or artifact of the manner in which values are represented? Would there still be non-random variation if we counted in hexadecimal, for example?
posted by clockzero at 8:27 AM on March 14, 2016 [2 favorites]

They checked several base systems (the first checks were in base-3) and found the phenomenon, so it looks like it's not a representation thing.
posted by Shutter at 8:30 AM on March 14, 2016 [4 favorites]

Would there still be non-random variation if we counted in hexadecimal, for example?

The article addresses that. They discovered it while looking in base 3, and:

Lemke Oliver and Soundararajan discovered that this sort of bias in the final digits of consecutive primes holds not just in base 3, but also in base 10 and several other bases; they conjecture that it’s true in every base
posted by DreamerFi at 8:33 AM on March 14, 2016 [4 favorites]

I just checked base 2 and found that *every* prime ending in a 1 is followed by another prime ending in a 1! (And yes, I checked *all* the primes.)
posted by uosuaq at 8:35 AM on March 14, 2016 [25 favorites]

But 1 is followed by 2!
posted by AlexiaSky at 8:51 AM on March 14, 2016 [2 favorites]

Wait I did a stupid.
posted by AlexiaSky at 8:52 AM on March 14, 2016 [10 favorites]

Saying that the final digits of consecutive primes prefers to change regardless of base is saying that the gap between consecutive primes prefers not to be divisible by the base in which it's expressed. Since the gaps are base independent, this is an insane thing to conjecture.
posted by Obscure Reference at 9:42 AM on March 14, 2016

Or maybe not. If we consider primality an extreme case of having few divisors, we can conjecture that the gaps between consecutive primes tend toward primishness.
posted by Obscure Reference at 9:53 AM on March 14, 2016

Can anyone explain why this is? I'm baffled.

I think the easiest way to understand it is to realize that if you toss a coin three times, there are 4 ways that Alice will get heads followed by tails, but only three ways that Bob can get heads followed by heads (because the toss Heads, Heads, Heads would still only count once).

T, T, T
T, T, H
T, H, T (Alice)
T, H, H (Bob)
H, T, T (Alice)
H, T, H (Alice)
H, H, T (Alice and Bob)
H, H, H (Bob)

If you change the set up slightly so that each of them tosses two coins at a time, it behaves exactly like you'd expect and it takes each of them an average of four tosses.
posted by nzero at 10:02 AM on March 14, 2016 [2 favorites]

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.

Can anyone explain why this is? I'm baffled.

Penney's Ante [PDF]:

Consider [again] the four possible outcomes of the first two tosses: HH, HT, TH, TT. If either HH or TH (which are equally likely) occurs, the game is over. But if either HT or TT (also equally likely) occurs on the first two tosses, the next toss will either complete the game (if H), or cause it to continue (if T), and in the latter case tossing will continue until an H occurs. The general rule is that once a T has occurred, the combination TH is bound to occur before HH does. HH wins this game only if that is the combination on the first two tosses, which has a probability of 1/4, so this game is three times as likely to end with TH than with HH. (A similar analysis will show that HT is more likely to occur first in a string than is TT.)
With longer target sequences the differences in probabilities can become large. Consider, for example, the sequences HHHHH and THHHH. If either of the two target sequences occurs with the first five tosses, the game is over, but if the first five tosses produce any other sequence, it will be impossible for HHHHH to occur before THHHH. It follows that the probability that HHHHH will occur before THHHH is 1/32, or that the odds favoring THHHH are 31 to 1.

posted by alby at 10:03 AM on March 14, 2016 [1 favorite]

:-o

You have GOT to be kidding me!! It's so weird that no one ever noticed this near-trivial pattern I'm almost wondering if it's hoax - but it's too easy to verify.

Now I'm kicking myself for not noticing this myself. Damn! I could have written a computer program in literally 20 minutes any time in the last 20 years and discovered this!!! (I or a million other people, but it should have been me! ;-) )

---

> Can anyone explain why this is? I'm baffled.

An even simpler example!

Our robot friend stands there and flips a coin over and over again. I'm waiting to see the sequence THH and you're waiting for HHH.

Now, if you just throw three coins in a row, either of these sequences is equally likely - they both have a one chance in eight.

But the only way that you can win this game is if HHH appears as the first three throws.

Seven times in eight, I win the game - because once a T has appeared, there's just no way to create a HHH combination without first creating a THH on the flip before.
posted by lupus_yonderboy at 11:00 AM on March 14, 2016 [9 favorites]

The Penney Ante article is great. It's been a few years since I saw that one. I love the fact that, for *any* combination of 3 coin tosses in a row, you can find another sequence which will occur first in a race of flips with a higher probability.

In fact, it's simple to use for a bar bet: For any combination of 3 Heads/Tails flips picked by the "victim", which I'll label as sequence "ABC", you will have higher probability by picking a new sequence, "bAB" (b is the opposite of whatever B was)**. This will give you odds of at least 2-1 (66.6% chance of a win), and potentially as high as 7-1 (87.5% chance of a win). Thus, the trick is to go a minimum number of rounds, to iron out the probabilities even further in your favor.

** A side-effect of this pattern is that of the 8 possible combinations the "victim" may pick, your response will always be one of only 4 patterns, all of which have exactly 2 of the same flip result adjacent.

Edit: Brian Brushwood's Scam School did a video on exactly this trick years ago...
posted by mystyk at 12:28 PM on March 14, 2016 [4 favorites]

The moment Alice gets a head, she's all set -- either she gets a tail and wins, or she gets a head and remains one step away from winning. But for Bob, getting a head doesn't put him in such a secure position -- if he gets a tail after that, he goes back to square one and is now two steps away from victory. Poor Bob.
posted by a car full of lions at 12:28 PM on March 14, 2016 [2 favorites]

Remember: The only even prime is 2. Since it's literally 1 number out of an infinite number of primes, this makes it different. Very different.

One might even call it "odd."

Does this mean you're launching a Tau Manifesto-type campaign to convince mathematicians to refer to integers 1, 3, 5, 7, 9, 11... as even and 2, 4, 6, 8, 10, 12... as odd? Or do you just want us to include '2' in the set of odd integers (1, 2, 3, 5, 7 9, 11, etc?) Or maybe 2 should be considered both odd and even?
posted by straight at 12:33 PM on March 14, 2016 [2 favorites]

My first thought was that this might be some version of Benford's Law, but the authors also seem to have considered that and ruled it out:

Lemke Oliver and Soundararajan’s first guess for why this bias occurs was a simple one: Maybe a prime ending in 3, say, is more likely to be followed by a prime ending in 7, 9 or 1 merely because it encounters numbers with those endings before it reaches another number ending in 3. For example, 43 is followed by 47, 49 and 51 before it hits 53, and one of those numbers, 47, is prime.

But the pair of mathematicians soon realized that this potential explanation couldn’t account for the magnitude of the biases they found. Nor could it explain why, as the pair found, primes ending in 3 seem to like being followed by primes ending in 9 more than 1 or 7.

posted by straight at 12:41 PM on March 14, 2016

No, that's not related to Benford's Law.
posted by escabeche at 12:45 PM on March 14, 2016 [1 favorite]

If you used base 14, then numbers ending in 7 would be divisible by 7, and you would have primes ending in 5 (and the symbol for 11).
posted by 445supermag at 3:47 PM on March 14, 2016

I know I'm late to the party but I made a jsfiddle out of the idea.
posted by the antecedent of that pronoun at 5:54 PM on March 14, 2016

No, that's not related to Benford's Law.

It's a similar phenomenon to Benford's Law because one way of thinking about why numbers (of the sort to which Benford's Law applies) start with 1 or 2 more often than 8 or 9 is that you have to go past a whole bunch of numbers that begin with 1 and 2 before you get to the ones that get to 8 or 9, and if your numbers are large enough to start with 8 or 9, you can get just a little bit bigger to get to the numbers that start with 1 or 2 again (but you have to get a whole lot bigger to keep going out to 8 or 9 again).
posted by straight at 8:02 PM on March 14, 2016

(Or it would be similar to Bedford's Law if it were the correct explanation for this prime number pattern.)
posted by straight at 8:08 PM on March 14, 2016

Can anyone explain why this is? I'm baffled.

OK, so you've gotten like seven cogent explanations of this so far, but here's another which I don't think anyone has said yet. In an infinite series of coin flips, 1/4 of consecutive pairs will be HH and 1/4 will be HT. But the HH flips can chain together (like this: HHH, or HHHH, or...), while the HT's can't. So "HH events" tend to occur in clusters, which increases the average waiting time for the first such event to appear.

To draw an analogy, imagine two bus lines that run 4 times an hour, but the first bus tends to show up at regular intervals while the second tends to "clump" (where two or more buses show up in quick succession, leaving longer gaps between clusters). Both buses have the same average frequency, but average waiting time for passengers on the clumpy system is worse, for the same reason that you'll tend to wait longer to see HH in a series of coin flips than HT.
posted by aws17576 at 10:40 PM on March 14, 2016 [1 favorite]

Incidentally, as an urban bus rider, I really feel that analogy.
posted by aws17576 at 10:41 PM on March 14, 2016

My first thought was that this might be some version of Benford's Law, but the authors also seem to have considered that and ruled it out

Strikes me as more likely to be a hot spot type result.
posted by eviemath at 1:24 PM on March 15, 2016

OK, I just realised something that supports my Ulam spiral/quadratic curve theory. Take the forty numbers produced by Euler's formula n²+n+41:
41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641.

Euler's formula is remarkably good, but as far as we know there are an infinite number of similar formulas. The coefficients aren't random; they're related to the discriminant which in this case is the very special number -163. The final digits of the primes produced by Euler's formula follow a regular pattern: 1, 3, 7, 3, 1, 1, 3, 7, 3, 1 and as you can see 1 never follows 7, 3 never follows 3, and 7 never follows either 1 or 7.

So. Given that many prime numbers have a higher probability to lie on these quadratic curves; given that the curves determine the primes' final digits in a non-random way; and given that the coefficients of these curves are themselves not random, I think it likely that there's a subtle rule governing the repeating pattern of final digits that may be found on these curves and in turn influences the distribution of final digits. However, it's also possible that this pattern is just a reflection of a higher-order pattern, and that if we went high enough the imbalance would disappear and even reverse itself.
posted by Joe in Australia at 4:41 PM on March 15, 2016

Good and much more detailed explanation by Terence Tao.

(I had no idea there was nonuniformity of the distribution of moduli even for single primes: Chebyshev's bias.)

About Benford's law: that is about the leading digit(s) in a quantity that spans multiple orders of magnitude; this is about the final digit, i.e., the remainder modulo some small number.
posted by mubba at 12:46 PM on March 16, 2016

Something we missed else about prime gaps.
posted by Obscure Reference at 8:33 AM on March 19, 2016