View Single Post 2003-05-14, 14:56   #34
wblipp

"William"
May 2003
New Haven

26×37 Posts Quote:
 Originally Posted by TTn If no one opposes this statement: "If p divides k, then p does not divide k*2^n-1. This means that N=k*2^n-1 is prime with probability k/phi(k) * 1/ln(N) instead of probability 1/ln(N).
You're looking for an adjustment to the probability of prime estimated from the Prime Number Theorem as 1/ln(x). That estimate applies to consecutive integers; in consecutive integers we know that 1/2 are divisible by 2, 1/3 of the remainder are divisible by 3, 1/5 of the remainder are divisible by 5, 1/7 of the remainder are divisible by 7 etc. You correctly note that divisibility is different for k. But it's different for other numbers, too. 3*2^k-1 is never divisible by 2, 7, 17, 31 and others. 1/4 are divisible by 5 and 1/18 are divisible by 19, but half of the numbers divisible by 19 are also divisible by 5.

What you need is the "Proth-Minus" Weight of k, analogous to Proth Weight. Proth Weight is the adjustment needed for k*2^n+1. Yves Gallot's paper on weights and Jack Brennen's Java calculator are places to start learning about Proth Weight. The concepts for k*2^n-1 should be identical.

From personal experience, the best way to estimate these weights is to use the follow the methods of Brennen and Gallot to calculate the approximate effect of large numbers of primes. I tried calculating the exact effect of small numbers of primes, and ended up with inferior estimates that gradually converge to the Brennan and Gallot estimates as the "small number" gets bigger. 