First Brian Hayes wrote an excellent post about the remainders when primes are divided by other primes. Then I wrote a follow-on just focusing on the first part of his post. He mostly looked at pairs of primes, but I wanted to look in more detail at the first part of his post, simulating dice rolls by keeping the remainder when consecutive primes are divided by a fixed prime. For example, using a sequence of primes larger than 7 and taking their remainder by 7 to create values from 1 to 6.
The results are evenly distributed with some variation, just like dice rolls. In fact, given these results and results from a set of real dice rolls, most people would probably think the former are real because they’re more evenly distributed. A chi-squared goodness of fit test shows that the results are too evenly distributed compared to real dice rolls.
At the end of my previous post, I very briefly discuss what happens when you look a “dice” with more than six sides. Here I’ll go into a little more detail and look at a large number of examples.
In short, you either get a suspiciously good fit or a terrible fit. If you look at the remainder when dividing primes by m, you get values between 1 and m-1. You can’t get a remainder of 0 because primes aren’t divisible by m (or anything else!). If m itself is prime, then you get all the numbers between 1 and m-1, and as we’ll show below you get them in very even proportions. But if m isn’t prime, there are some remainders you can’t get.
The sequence of remainders looks random in the sense of being unpredictable. (Of course it is predictable by the algorithm that generates them, but it’s not predictable in the sense that you could look at the sequence out of context and guess what’s coming next.) The sequence is biased, and that’s the big news. Pairs of consecutive primes have correlated remainders. But I’m just interested in showing a different departure from a uniform distribution, namely that the results are too evenly distributed compared to random sequences.
The table below gives the chi-square statistic and p-value for each of several primes. For each prime p, we take remainders mod p of the next million primes after p and compute the chi-square goodness of fit statistic with p-2 degrees of freedom. (Why p-2? There are p-1 different remainders, and the chi-square test for k possibilities has k-1 degrees of freedom.)
The p-value column gives the probability of seeing at fit this good or better from uniform random data. (The p in p-value is unrelated to our use of p to denote a prime. It’s an unfortunate convention of statistics that everything is denoted p.) After the first few primes, the p-values are extremely small, indicating that such an even distribution of values would be astonishing from random data.
|-------+------------+------------| | Prime | Chi-square | p-value | |-------+------------+------------| | 3 | 0.0585 | 2.88e-02 | | 5 | 0.0660 | 5.32e-04 | | 7 | 0.0186 | 1.32e-07 | | 11 | 0.2468 | 2.15e-07 | | 13 | 0.3934 | 6.79e-08 | | 17 | 0.5633 | 7.64e-10 | | 19 | 1.3127 | 3.45e-08 | | 23 | 1.1351 | 2.93e-11 | | 29 | 1.9740 | 3.80e-12 | | 31 | 2.0052 | 3.11e-13 | | 37 | 2.5586 | 3.92e-15 | | 41 | 3.1821 | 9.78e-16 | | 43 | 4.4765 | 5.17e-14 | | 47 | 3.7142 | 9.97e-18 | | 53 | 3.7043 | 3.80e-21 | | 59 | 7.0134 | 2.43e-17 | | 61 | 5.1461 | 6.45e-22 | | 67 | 7.1037 | 5.38e-21 | | 71 | 7.6626 | 6.13e-22 | | 73 | 7.5545 | 4.11e-23 | | 79 | 8.0275 | 3.40e-25 | | 83 | 12.1233 | 9.92e-21 | | 89 | 11.4111 | 2.71e-24 | | 97 | 12.4057 | 2.06e-26 | | 101 | 11.8201 | 3.82e-29 | | 103 | 14.4733 | 3.69e-26 | | 107 | 13.8520 | 9.24e-29 | | 109 | 16.7674 | 8.56e-26 | | 113 | 15.0897 | 1.20e-29 | | 127 | 16.4376 | 6.69e-34 | | 131 | 19.2023 | 6.80e-32 | | 137 | 19.1728 | 1.81e-34 | | 139 | 22.2992 | 1.82e-31 | | 149 | 22.8107 | 6.67e-35 | | 151 | 22.8993 | 1.29e-35 | | 157 | 30.1726 | 2.60e-30 | | 163 | 26.5702 | 3.43e-36 | | 167 | 28.9628 | 3.49e-35 | | 173 | 31.5647 | 7.78e-35 | | 179 | 33.3494 | 2.46e-35 | | 181 | 36.3610 | 2.47e-33 | | 191 | 29.1131 | 1.68e-44 | | 193 | 29.9492 | 2.55e-44 | | 197 | 34.2279 | 3.49e-41 | | 199 | 36.7055 | 1.79e-39 | | 211 | 41.0392 | 8.42e-40 | | 223 | 39.6699 | 1.73e-45 | | 227 | 42.3420 | 2.26e-44 | | 229 | 37.1896 | 2.02e-50 | | 233 | 45.0111 | 4.50e-44 | | 239 | 43.8145 | 2.27e-47 | | 241 | 51.3011 | 1.69e-41 | | 251 | 47.8670 | 6.28e-48 | | 257 | 44.4022 | 1.54e-53 | | 263 | 51.5905 | 7.50e-49 | | 269 | 59.8398 | 3.92e-44 | | 271 | 59.6326 | 6.02e-45 | | 277 | 52.2383 | 2.80e-53 | | 281 | 52.4748 | 1.63e-54 | | 283 | 64.4001 | 2.86e-45 | | 293 | 59.7095 | 2.59e-52 | | 307 | 65.2644 | 1.64e-52 | | 311 | 63.1488 | 1.26e-55 | | 313 | 68.6085 | 7.07e-52 | | 317 | 63.4099 | 1.72e-57 | | 331 | 66.3142 | 7.20e-60 | | 337 | 70.2918 | 1.38e-58 | | 347 | 71.3334 | 3.83e-61 | | 349 | 75.8101 | 3.38e-58 | | 353 | 74.7747 | 2.33e-60 | | 359 | 80.8957 | 1.35e-57 | | 367 | 88.7827 | 1.63e-54 | | 373 | 92.5027 | 7.32e-54 | | 379 | 86.4056 | 5.67e-60 | | 383 | 74.2349 | 3.13e-71 | | 389 | 101.7328 | 9.20e-53 | | 397 | 86.9403 | 1.96e-65 | | 401 | 90.3736 | 3.90e-64 | | 409 | 92.3426 | 2.93e-65 | | 419 | 95.9756 | 8.42e-66 | | 421 | 91.1197 | 3.95e-70 | | 431 | 100.3389 | 1.79e-66 | | 433 | 95.7909 | 1.77e-70 | | 439 | 96.2274 | 4.09e-72 | | 443 | 103.6848 | 6.96e-68 | | 449 | 105.2126 | 1.07e-68 | | 457 | 111.9310 | 1.49e-66 | | 461 | 106.1544 | 7.96e-72 | | 463 | 116.3193 | 1.74e-65 | | 467 | 116.2824 | 1.02e-66 | | 479 | 104.2246 | 3.92e-79 | | 487 | 116.4034 | 9.12e-73 | | 491 | 127.2121 | 6.69e-67 | | 499 | 130.9234 | 5.90e-67 | | 503 | 118.4955 | 2.60e-76 | | 509 | 130.9212 | 6.91e-70 | | 521 | 118.6699 | 6.61e-82 | | 523 | 135.4400 | 3.43e-71 | | 541 | 135.9210 | 3.13e-76 | | 547 | 120.0327 | 2.41e-89 | |-------+------------+------------|
Consider remainders mod some prime p. Numbers divisible by any other prime q are systematically superflat – they form an arithmetic sequence mod p. So now imagine sieving all the numbers below some large N. You cross out numbers in arithmetic sequences, so it is not altogether implausible that the ones left over over are superflat. Of course these arithmetic sequences overlap so this far from a proof.
Maybe not that far though. Consider a set of set of primes q_i. Numbers not divisible by any of them are, by an inclusion-exclusion argument, superflat mod p.
Now you need to swap the limits, sort of. What we have is that for any set q_i, for sufficiently large N, the numbers not divisible by any of them are superflat. What we need is that for sufficiently large N, for all q_i<p, the numbers not divisible by any of then are super flat.
Sorry that last bit about q_i<p is a typo. I meant q_i<N but that's nonsense . I guess something like $q_i<\sqrt N$ might work.