| QUOTE (icarus @ Jul 9 2007, 11:00 AM) |
One interesting observation is that all primes greater than 3 occur either 1 step before or one step after a multiple of six. So any given prime may be regarded like:
41 = (6*7)-1
43 = (6*7)+1
47 = (6*8)-1
As all primes greater than 3 are confined to 1 and 5 modulus 6. |
Right: A prime modulo 6 can't be 0, 2, or 4 (i.e., a multiple of 2); or 0 or 3 (i.e., a multiple of 3), so that just leaves 1 and 5.
| QUOTE (icarus @ Jul 9 2007, 11:00 AM) |
| See wikipedia's "sieve of eratosthenes" and related articles for how 6 and 60 is used to help determine primes. |
Well, the set {2, 3, 6ną1} is what's left over after the second pass of the
Sieve of Eratosthenes. Wasn't aware of this significance of 60 until I read the article on the
Sieve of Atkin.
BTW, here's my code for the Sieve of Eratosthenes as I attempt to learn
D:
| CODE |
import std.conv;
import std.stdio;
int[] primes(int max)
{
int numPrimes = 0;
bit[] compFlags = new bit[max];
int nextPrime = 2;
while (nextPrime < max)
{
++numPrimes;
// mark all multiples of nextPrime as composite
for (int multiple = nextPrime * 2; multiple < max; multiple += nextPrime)
{
compFlags[multiple] = true;
}
// search for the next prime
do
{
++nextPrime;
}
while (nextPrime < max && compFlags[nextPrime]);
}
// scan through compFlags looking for prime numbers,
// storing the result in an array
int[] result = new int[numPrimes];
for (int num = 2, index = 0; num < max; num++)
{
if (!compFlags[num])
{
result[index++] = num;
}
}
return result;
}
void main(char[][] args)
{
if (args.length == 2)
{
foreach (prime; primes(toInt(args[1])))
{
writefln(prime);
}
}
else
{
writefln("Usage: primes MAX");
}
} |
| QUOTE (Dan @ Jul 8 2007, 04:40 PM) |
| QUOTE (Ellume @ Jul 7 2007, 10:23 PM) | | Edit: I think it is interesting that base 30, 60, and 90 are all tied for top probability. |
More generally, all bases with the same prime factors have the same ratio.
|
Still more generally:
Not only the probability is related to the prime decomposition of the base, it can also be obtained through precise formulae. Here's the ones I've managed to find out so far:
- For bases with one prime factor, n, the probability is given by the formula: 1/n; that is, the reciprocal of the prime.
- For bases with two prime factors, n and m, the probability is: (n+m-1)/(n*m).
- For bases with three prime factors, n, m and p (with p > m > n), the provided data are not enough to arrive at a general formula, but for n = 2 the formula seems to be: [(m*p) + (m+p-1)]/(n*m*p).
Additional insight:
The probabilities reach relative maxima at the first element in each series if you order it by ascending primes, and they increase as the number of primes increases. That is, the maximum probability for the series of "uniprimal" bases (bases with only one distinct prime factor) is at the 2-smooth bases (2, 4, 8, 16..., prime factor 2) with a probability of 0.5; for the series of "biprimal" bases, the maximum is at the 3-smooth bases (6, 12, 18, 24..., prime factors 2 and 3) with a probability of 0.6667, which is greater than the maximum for uniprimal bases; for the series of "triprimal" bases, the maximum is at the 5-smooth bases (30, 60, 90..., prime factors 2, 3 and 5) with a probability of 0.7333, greater than that for biprimal bases; etc. The probability for the first "quadriprimal" base (base 2*3*5*7 = base 210) should expectably be greater than 0.7333.
Then, from each relative maximum, the probabilities in each series keep descending; e.g., the biprimal series in ascending order is: 2*3, 2*5, 2*7, 2*11, 2*13, ..., 3*5, 3*7, 3*11, 3*13, ..., 5*7, 5*11, 5*13, ..., 7*11, 7*13, ... (expressed in exponential prime-factorization notation: [1,1,0,0,0,0,...], [1,0,1,0,0,0,...], [1,0,0,1,0,0,...], [1,0,0,0,1,0,...], [1,0,0,0,0,1,...], ..., [0,1,1,0,0,0,...], [0,1,0,1,0,0,...], [0,1,0,0,1,0,...], [0,1,0,0,0,1,...], ..., [0,0,1,1,0,0,...], [0,0,1,0,1,0,...], [0,0,1,0,0,1,...], ..., [0,0,0,1,1,0,...], [0,0,0,1,0,1,...], ...), and their respective probabilites are: 0.6666, 0.6, 0.5714, 0.5454, 0.5384, ..., 0.4666, 0.4286, 0.3939, 0.3846, ..., 0.3143, 0.2727, 0.2615, ..., 0.2208, 02088, ...