Comment by crnt2 | Hacker News Reader

Comment by crnt2 | Hacker News Reader

The results are particularly striking in base 11 - looking at primes below 100 million, only 4.3% of primes ending in 2 are followed by another prime ending in 2 (compared to the 9.1% you would naively expect) with similar numbers for other pairs.

A prime ending in 2 (in base 11) is also unlikely to be following by a prime ending in 5, 7 or 9, whereas it is particularly likely to be following by a prime ending in 4 or 8.

It would be interesting to know what structure there is (if any) in this NxN "transition matrix" for various bases.

   1: ( 1,  4.3%) ( 2, 13.0%) ( 3, 14.3%) ( 4,  7.7%) ( 5, 11.5%) ( 6,  6.3%) ( 7, 18.0%) ( 8,  9.0%) ( 9, 10.7%) (10,  5.2%) 
   2: ( 1, 10.0%) ( 2,  3.7%) ( 3, 11.3%) ( 4, 14.1%) ( 5,  7.5%) ( 6, 12.1%) ( 7,  5.3%) ( 8, 17.5%) ( 9,  7.8%) (10, 10.7%) 
   3: ( 1,  6.1%) ( 2, 10.3%) ( 3,  3.7%) ( 4, 12.5%) ( 5, 14.0%) ( 6,  9.2%) ( 7, 12.1%) ( 8,  5.6%) ( 9, 17.5%) (10,  9.0%) 
   4: ( 1, 11.1%) ( 2,  6.1%) ( 3,  9.9%) ( 4,  4.1%) ( 5, 11.5%) ( 6, 14.5%) ( 7,  7.7%) ( 8, 12.0%) ( 9,  5.3%) (10, 18.0%) 
   5: ( 1,  9.6%) ( 2, 12.7%) ( 3,  6.3%) ( 4, 11.5%) ( 5,  4.0%) ( 6, 13.6%) ( 7, 14.5%) ( 8,  9.2%) ( 9, 12.1%) (10,  6.4%) 
   6: ( 1, 17.9%) ( 2,  8.5%) ( 3, 10.6%) ( 4,  5.0%) ( 5,  9.6%) ( 6,  4.0%) ( 7, 11.4%) ( 8, 14.0%) ( 9,  7.5%) (10, 11.5%) 
   7: ( 1,  6.0%) ( 2, 19.1%) ( 3,  8.8%) ( 4, 11.1%) ( 5,  5.1%) ( 6, 11.6%) ( 7,  4.1%) ( 8, 12.5%) ( 9, 14.1%) (10,  7.7%) 
   8: ( 1, 12.0%) ( 2,  5.5%) ( 3, 17.5%) ( 4,  8.8%) ( 5, 10.6%) ( 6,  6.3%) ( 7,  9.9%) ( 8,  3.7%) ( 9, 11.3%) (10, 14.3%) 
   9: ( 1,  8.8%) ( 2, 12.4%) ( 3,  5.5%) ( 4, 19.1%) ( 5,  8.6%) ( 6, 12.7%) ( 7,  6.0%) ( 8, 10.3%) ( 9,  3.7%) (10, 13.0%) 
  10: ( 1, 14.3%) ( 2,  8.8%) ( 3, 12.0%) ( 4,  6.0%) ( 5, 17.8%) ( 6,  9.6%) ( 7, 11.1%) ( 8,  6.1%) ( 9, 10.0%) (10,  4.3%)

It looks symmetric along the anti-diagonal. Strange.

Wow, that's really interesting. The same seems to be true for base 7; I haven't tried any other prime bases yet (and I don't know how it might extend to non-prime bases). Anyone have an idea why this seems to hold?

Edit: This basically works for base 10, too. I feel like the reason must either be very obvious or very deep.

I also tested in base 10, with primes under 1e9, got this:

             1       3       7       9
  1       0.0458  0.0746  0.0756  0.0540
  3       0.0599  0.0439  0.0707  0.0755
  7       0.0638  0.0677  0.0438  0.0747
  9       0.0805  0.0638  0.0599  0.0458

It appears to have the same transition probabilities as in base 5 (with the two center rows and columns swapped):

             1       2       3       4
  1       0.0458  0.0756  0.0746  0.0540
  2       0.0638  0.0438  0.0677  0.0747
  3       0.0599  0.0707  0.0439  0.0755
  4       0.0805  0.0599  0.0638  0.0458

I share your feeling about it being either obvious or deep.

I find this more interesting than the article and want to know more.

> It appears to have the same transition probabilities as in base 5 (with the two center rows and columns swapped):

Well, yeah that's because 1,3,7,9 modulo 5 becomes 1,3,2,4 which is 1,2,3,4 with the centre two swapped.

I'm pretty solidly convinced of the pattern at this point: I've checked the "reflect across the anti-diagonal" pattern for the first 10 million primes, expressed in every base from 3 to 20, and it seems to hold up. (I haven't tried to establish any sort of bounds.)

As I've expressed in another comment, my preferred way of thinking about this symmetric pattern goes something like this:

The probability that (a prime congruent to x mod b is followed by a prime congruent to y mod b) seems to be equal to the probability that (a prime congruent to -y mod b is followed by a prime congruent to -x mod b).

I still haven't figured out whether it ought to be obvious, though if it is then I expect the language I've used above to be relevant. It's definitely not trivially obvious, because it's not an exact equality: if the pattern only shows up clearly after you've accumulated thousands or millions of primes, then it doesn't seem that it could be enforced by any sort of exact transformation. (For example, if the symmetric entries were somehow just counting the same pairs in two different ways, the numbers ought to be precisely equal rather than just increasingly close.)

There are a rather a lot of other patterns in the data; I expect that at least some of them must be accounted for in the original paper, but I haven't more than glanced through it yet.

Well, whether it's obvious or not, I think it's in the paper. Immediately under equation (1.1) of http://arxiv.org/abs/1603.03720, the authors are discussing the second correction term to the distribution of primes mod q, and they state:

"We can also show that c2(q; (a, b)) = c2(q; (−b,−a)) for any two reduced residue classes a and b (mod q)."

I'm not 100% certain this is responsible for the phenomenon that we're seeing, but it seems exceedingly likely. I think I'd need to stare at their formula for c2 for a long time to understand where this relation comes from, though.

So a number ending in 'x' is as likely to be followed by 'y' as a number ending in 'n-x' is to be preceded by a number ending in 'n-y' (where n is the base).

Can't think of a trivial reason why that would be the case, something weird is happening.

Framing this differently, a prime congruent to x mod b is as likely to be followed by a prime congruent to y mod b as a prime congruent to -y mod b is to be followed by one congruent to -x mod b.

Why would you expect 9.1%? At low numbers like these, primes are likely to be closely packed, meaning you are not as likely to have to search forward 11 numbers as just dividing by 11 would imply.

Miscalculation - obviously no primes end in 0 (base 11) so I should have said "10% as you would naively expect".

I take your point about primes being closely packed at low numbers, but I think this is a small correction (i.e. you might expect 8-9% of primes ending in 2 to be followed by another prime ending in 2, but certainly not <4%)

Could you rule out all pairs that are less than 11 apart in order to calculate how large a factor that is?

I made an attempt to do this elsewhere in the thread, take a look at

https://news.ycombinator.com/threads?id=crnt2

The result - the factor is actually surprisingly large!

Nice!

I did my own investigation using base 3 and noticed something peculiar.

In the first 100k primes, we go from 1 to 2 29028 times and from 2 to 1 29029 times.

Then I filtered out the twin primes since those are the ones that exploit the fact that the next "possible" prime is one that flips the last digit.

This filtered out 10249 primes going from 2 to 1 (bringing the total below both the number of primes that stay at 2 (21008) and the number of primes that stay at 1 (20932)).

It didn't factor out any primes that go from 1 to 2. Are there no twin primes (p,p') where p%3 == 1 and p'%3 == 2?

edit: Oh hey, this is obvious, if p%3 is 1 then p+2 is divisible by 3. It does mean we don't need to take measurements to know that the result we are investigating cannot possibly account for everything since it isn't a factor at all when going from 1 to 2.

> Are there no twin primes (p,p') where p%3 == 1 and p'%3 == 2?

By definition, no there aren't. Twin primes are a distance of 2 apart, so your mod 3 options are 0 -> 2, 1 -> 0, and 2 -> 1. Anything involving 0 means it's divisible by 3, so your only mod 3 possibility for twin primes is 2 -> 1.

EDIT: Excluding the possibility where 3 mod 3 = 0, of course. This allows a 0 -> 2 transition with (3,5).

Yeah, I managed to get an edit in just before you replied -- I thought I was missing something obvious but I kept looking for a bug in my code instead of realizing that it's mathematically obvious :)

Reply on news.ycombinator.com