4 ms·

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

by crnt2 11y ago

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%)

vessenes 11y ago
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.
- crnt2 11y ago
  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%)
  - furyofantares 11y ago
    Could you rule out all pairs that are less than 11 apart in order to calculate how large a factor that is?
    - crnt2 11y ago
      I made an attempt to do this elsewhere in the thread, take a look at https://news.ycombinator.com/threads?id=crnt2 https://news.ycombinator.com/threads?id=crnt2 The result - the factor is actually surprisingly large!
      - furyofantares 11y ago
        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.
        Bognar 11y ago
        > 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).
        furyofantares 11y ago
julien-c 11y ago
It looks symmetric along the anti-diagonal. Strange.
- Steuard 11y ago
  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.
  - julien-c 11y ago
    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.
    - tgb 11y ago
      I find this more interesting than the article and want to know more.
    - contravariant 11y ago
      > 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.
    - Steuard 11y ago
      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.

by crnt2 11y ago

vessenes 11y ago

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.

crnt2 11y ago
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%)
- furyofantares 11y ago
  Could you rule out all pairs that are less than 11 apart in order to calculate how large a factor that is?
  - crnt2 11y ago
    I made an attempt to do this elsewhere in the thread, take a look at https://news.ycombinator.com/threads?id=crnt2 https://news.ycombinator.com/threads?id=crnt2 The result - the factor is actually surprisingly large!
    - furyofantares 11y ago
      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.
      - Bognar 11y ago
        > 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).
        furyofantares 11y ago

julien-c 11y ago

It looks symmetric along the anti-diagonal. Strange.

Steuard 11y ago
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.
- julien-c 11y ago
  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.
  - tgb 11y ago
    I find this more interesting than the article and want to know more.
  - contravariant 11y ago
    > 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.
  - Steuard 11y ago
    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.