Dividing All Primes By A Given Prime
Question: Is there some pattern to the remainders obtained when the set of all prime numbers is divided by a given prime divisor?
Experiment: Let the first N primes be called the keys (N very large); choose the prime divisor as some small value like 7 or 13 or so. With each possible value of the remainder, one associates a bucket and the full set of primes is split among these buckets. Then count the number caught in each bucket.
Note: with larger values of the prime divisor, there will be many buckets, so the frequencies of each remainder will be small so seeing patterns would be difficult.
The basic observations:
1. With say 7 as divisor and the first N primes as keys (N could be say a million), only 6 remainders are possible ie 1 to 6. All remainders are returned with almost equal frequency. as N gets larger, the spread in numbers of keys trapped in the buckets become even closer - the frequency spread (defined to be the ratio (diff between the max an min frequencies) : (average of the max and min frequencies) *generally* reduces with increase in N although not monotonically.
There is nothing special about 7. Any other prime chosen as divisor yields the same behavior of almost equal frequencies for all remainders. And if a composite number C is chosen as divisor, the frequencies will be 0 for remainders which are factors of C (eg: if C=6 and keys are from the set of primes, 2,3 will appear only once each among the remainders, practically zero that is) but for other remainders from 1 to C-1, again the frequencies come near perfectly balanced.
2. Now, this 'prime-hash' method with divisor 7 might look like an attractive way to generate nos 1-6 randomly; iow, to simulate the toss of a dice. But hold on! The simple chi-squared test for randomness (Ref: Sedgewick's 'Algorithms in C++') emphatically shows this sequence to nos. 1 - 6 to be quite poorly random.
A comparison was made with the case of N numbers generated by the function rand() getting hashed by the same divisor. If a sequence of remainders modulo 7 is acceptably random (function rand() achieves it), the frequencies of possible values should NOT be perfectly equal but ought to have a certain spread. We note, with the above 'prime-hash' method, the frequencies are much more closely bunched than when the keys were generated by rand()(see below). So, the chi-squared deduction that prime-hash is not particularly good as a random number generator looks valider.
-------------
Example:
With prime-hash method, the first 100,000 primes, when hashed into 6 buckets (divisor = 7), the frequencies in each bucket are: 16677, 16649, 16685, 16630, 16673,16685. The range of frequency values is only 55 - they are bunched very close.
When 100,000 random numbers are hashed (modulo 6) into 6 buckets, the frequences found were: 16628, 16719,16459,16751, 16769, 16674. The range of values (= 210) is much higher in this case.
-------------
3. If a particular prime gives remainder r1 (with 7 as divisor, r1 is from 1 to 6), the next prime can give a remainder r2 that can be any of 1 to 6. But (crucially), r1==r2 turns out *clearly less likely than what one would naively expect*. Eg: if say, r1==3, the chance that r2 is also 3 is only around 8 percent and not 16.66 percent (We think of nos 1 to 6 arranged in order in a ring and the cyclic shorter distance between r1 and r2. Then for each of the 6 possible values of r2 there is a cyclic distance from r1 and r1 ==r2 and the cyclic distance of 0 occuring between remainders of successive primes is a lot less likely than if the sequence were perfectly random). The relative probabilites of cyclic distances between remainders of successive primes are fairly robust w.r.to increasing N.
Summary: Two questions (not really dramatic):
1. As obvserved above, with N going to to infinity, with any prime divisor, all remainders tend to be equally likely. Why? Subquestion: Could one quantify the rate at which the frequencies of all remainders equalize with increasing N?
2. If a particular prime, when divided by the chosen prime divisor, gives a certain remainder, why is it that the next prime is (relatively) unlikely to give the same remainder?
Both might have rigorous explanations. Its just that I dunno!
Experiment: Let the first N primes be called the keys (N very large); choose the prime divisor as some small value like 7 or 13 or so. With each possible value of the remainder, one associates a bucket and the full set of primes is split among these buckets. Then count the number caught in each bucket.
Note: with larger values of the prime divisor, there will be many buckets, so the frequencies of each remainder will be small so seeing patterns would be difficult.
The basic observations:
1. With say 7 as divisor and the first N primes as keys (N could be say a million), only 6 remainders are possible ie 1 to 6. All remainders are returned with almost equal frequency. as N gets larger, the spread in numbers of keys trapped in the buckets become even closer - the frequency spread (defined to be the ratio (diff between the max an min frequencies) : (average of the max and min frequencies) *generally* reduces with increase in N although not monotonically.
There is nothing special about 7. Any other prime chosen as divisor yields the same behavior of almost equal frequencies for all remainders. And if a composite number C is chosen as divisor, the frequencies will be 0 for remainders which are factors of C (eg: if C=6 and keys are from the set of primes, 2,3 will appear only once each among the remainders, practically zero that is) but for other remainders from 1 to C-1, again the frequencies come near perfectly balanced.
2. Now, this 'prime-hash' method with divisor 7 might look like an attractive way to generate nos 1-6 randomly; iow, to simulate the toss of a dice. But hold on! The simple chi-squared test for randomness (Ref: Sedgewick's 'Algorithms in C++') emphatically shows this sequence to nos. 1 - 6 to be quite poorly random.
A comparison was made with the case of N numbers generated by the function rand() getting hashed by the same divisor. If a sequence of remainders modulo 7 is acceptably random (function rand() achieves it), the frequencies of possible values should NOT be perfectly equal but ought to have a certain spread. We note, with the above 'prime-hash' method, the frequencies are much more closely bunched than when the keys were generated by rand()(see below). So, the chi-squared deduction that prime-hash is not particularly good as a random number generator looks valider.
-------------
Example:
With prime-hash method, the first 100,000 primes, when hashed into 6 buckets (divisor = 7), the frequencies in each bucket are: 16677, 16649, 16685, 16630, 16673,16685. The range of frequency values is only 55 - they are bunched very close.
When 100,000 random numbers are hashed (modulo 6) into 6 buckets, the frequences found were: 16628, 16719,16459,16751, 16769, 16674. The range of values (= 210) is much higher in this case.
-------------
3. If a particular prime gives remainder r1 (with 7 as divisor, r1 is from 1 to 6), the next prime can give a remainder r2 that can be any of 1 to 6. But (crucially), r1==r2 turns out *clearly less likely than what one would naively expect*. Eg: if say, r1==3, the chance that r2 is also 3 is only around 8 percent and not 16.66 percent (We think of nos 1 to 6 arranged in order in a ring and the cyclic shorter distance between r1 and r2. Then for each of the 6 possible values of r2 there is a cyclic distance from r1 and r1 ==r2 and the cyclic distance of 0 occuring between remainders of successive primes is a lot less likely than if the sequence were perfectly random). The relative probabilites of cyclic distances between remainders of successive primes are fairly robust w.r.to increasing N.
Summary: Two questions (not really dramatic):
1. As obvserved above, with N going to to infinity, with any prime divisor, all remainders tend to be equally likely. Why? Subquestion: Could one quantify the rate at which the frequencies of all remainders equalize with increasing N?
2. If a particular prime, when divided by the chosen prime divisor, gives a certain remainder, why is it that the next prime is (relatively) unlikely to give the same remainder?
Both might have rigorous explanations. Its just that I dunno!
posted by R.Nandakumar @ 10:04 AM
0 comments
