I looked at the first million primes, excluding 2 and 3, to see how
often a prime that's 1 mod 4 is followed by a prime that's 3 mod 4,
and vice versa, as compared with the number of primes that are
followed by another prime of the same 4-remainder. I noticed that
there's a significant bias. A changed 4-remainder happens 281288
times in each direction. An unchanged four-remainder happens 218510
(1->3) and 218913 (3->1) times. So the total number of changes is
562576, which is well over the expected 499999.5.
Next I checked how many changes there are between a prime and the
prime *two* positions later, e.g. from 5 to 11, 7 to 13, or 11 to 17.
Given that the changes between consecutive primes are unexpectedly
high, I thought that changes between primes 2 positions apart would
have to be low. The closer the sequence is to purely alternating,
1,3,1,3,1,3,..., the closer the second changes would have to be from
unchanging, 1,1,1,1,1,... and 3,3,3,3,3,....
But that's not what I saw. The second changes are also well above
half a million: 511084. Likewise with the third changes: 505466.
And the fourth, fifth, etc. Not until the *29th* changes, i.e.
whether a prime has the same 4-remainder as the prime 29 positions
after it, is there a number of changes that is less than half a
million, 499209.
(Note that there are one-million-minus-n nth changes, e.g. 999971
29th changes, of which half, 499985.5 would by chance be different.
Also note that if there's a bias, e.g. more primes 3 mod 4 than 1
mod 4, that ought to *reduce* the number of changes between primes
n places different, for all n. In the limit, if all primes were
3 mod 4, there would be zero differences for every n.)
I'm confused as to how this is possible. Given a long sequence
containing just two numbers, e.g. the first million digits of pi in
binary, if adjacent terms are less likely to be identical than chance
would predict, how can the terms two apart also be less likely to be
identical than chance? And just how large can these biases be? Is a
million-term sequence possible in which there are 900000 differences
between adjacent terms and 800000 differences between terms two places
apart? If not, just how large can those numbers be, and how would one
design a sequence to maximize them?
Maybe it has something to do with Fourier transforms?
Would the Thue-Morse sequence be an interesting example?
As my subject line says, this is no longer about primes, but about
changes in two-valued sequences in general.
