From: "jbrennen"
It has a mathematical basis, of course, but "good" is a relative term.... The index as defined is based on
the premise that the "chance" that a number of the form X = k.2^n+c is prime is generally proportional to
1/n. This is based on the Prime Number Theorem with these three assumptions:
The first two assumptions don't seem to pose a problem, but the third can cause the index to deviate
substantially from the predicted value when k becomes large.
Essentially, the index is equal to: p * Integral{from 1 to n}[1/x] dx I believe that the expected k-adjusted index should be asymptotic to
2*ProthWeight(k)/log(2), which is about 2.88*ProthWeight(k). For 67#, that would give an expected
k-adjusted index of 2.88*4.191 of about 12 - so 67#.2^n+1 seems to be a bit richer in primes than expected especially for n <= 3300.
Personally, I think that a good measure would be how many standard deviations above (or below)
expectation the actual prime count falls.
From Phil Carmody
Don't c==+1 and c==-1 create completely different biases? i.e. c is
just as relevant as k?
Phil
Jack replies:
Whether c is +1 or c is -1 makes negligible difference when one
averages over a large range of k and/or n.
Essentially, each of the following sets should be of roughly the
same cardinality:
{ k*2^n+1 prime, k odd, 1 <= k <= 99, 1 <= n <= 999 }
Of course, for any individual k, it may make a great deal of
difference whether c is +1 or c is -1, which is what I think
you were trying to say. :-)
Phil's reply
Ah, I was assuming that you'd fix two values, vary the third. You're
fixing one, varying two. Different problem, different solution.
Subject: Re: Ray Ballinger suggestion
--- Robert Smith wrote:
I refer readers to http://www.primepuzzles.net/puzzles/puzz_006.htm
There
is a formula referred to as the index p/ln(n) which purports to measure the relative density of primes for
series k.2^n +/-1 Does this formula have good mathematical basis?
-
The number of primes <= x is approximated by LogIntegral[x] -
The effect of the size of the constant term c is negligible -
The effect of the size of the Proth coefficient k is negligible
To incorporate k, this could be reasonably be changed to: p * Integral{from 1 to n}[1/(x+c)] dx
{where c is the base 2 log of k == ln(k)/ln(2)}
Which would give a "k-adjusted" index of: p / (ln(c+n) - ln(c+1))
which is equal to: p / ln((c+n)/(c+1)) or p / ln(1+(n-1)/(log2(k)+1))
This would change the weights from Carlos' page: On the plus side: k = 577294575, weight was 10.836,
becomes 16.088 On the minus side: k = 22932195, weight was 9.083, becomes 13.348
For Robert's numbers on 67#: primes = 70, n = 3300, weight was 8.640, becomes 18.863 primes = 88,
n = 18000, weight was 8.981, becomes 16.334
Draw whatever conclusions you want... One thing seems clear, that 67#.2^n+1 is quite rich in primes
for n <= 3300.
{ k*2^n-1 prime, k odd, 1 <= k <= 99, 1 <= n <= 999 }
{ k*2^n+3 prime, k odd, 1 <= k <= 99, 1 <= n <= 999 }
{ k*2^n-3 prime, k odd, 1 <= k <= 99, 1 <= n <= 999 }
{ k*2^n+1001 prime, k odd, 1 <= k <= 99, 1 <= n <= 999 }
{ k*2^n-1001 prime, k odd, 1 <= k <= 99, 1 <= n <= 999 }
But this set would be of a substantially different cardinality:
{ k*2^n+1 prime, k odd, 101 <= k <= 199, 1 <= n <= 999 }
So in the "macro" sense, the size of k is important, the size of c
is not...
Last updated 20 April 2002