Speed up your prime research : the weight of n in the Proth numbers




Numerous web sites talk about the weight of k in the Proth numbers k*2n+1 in order to find more prime numbers.
I found recently that it is also possible with the weight of n and that the method could be more interesting because :

     - With a fixed n, the Proth numbers divisible by the smallest prime numbers represent the majority of the numbers in any range of k.

     - With a fixed n, we find a prime number approximately every ln(2)*n = 0.7*n  k  ( with precisely the same measured standard error of 0.7*n )

So I had the idea of sieving different values of n for a fixed range of  k  (kmax-kmin>>ln(2)*n)  in order to find the worst values of n ( those where k*2n+1 is often divisible by small primes in this range of k). Thus, I avoid some long "compute powers" ( I use the program Proth made by Yves Gallot ) which makes those n the fastest for this range of k. So, I go over my range of k as faster as possible and because of the quite regular space between primes in a range of k for a fixed n, I often find primes faster than any other value of n.

Here is a simple and reproductive example :
I've asked my program the best and the worst n in the range 5000-5200 for the fixed range of k 3-10001 with a sieve of 200 prime numbers. The slower n given is 5032 and the faster is 5143 (the faster n is the n with the lower score). Effectively, the speed of the faster is 96.7 odd k/minute and 87.3 odd k/minute for the slower (Tests were made using the program Proth on a Pentium Pro 200Mhz). So, in this example, a 2.20% bigger n is approximately 10.8% faster and this could be more with other values of n and k (5143 finished its range of k when 5032 was at k=8967) ! "But did I find the same number of primes ?" you will ask me. Yes, I found 3 primes with each n (n=5032 : k=1023, 1327, 9291 and for n=5143 : k=2037, 5819, 9819) :
(kmax-kmin)/(ln(2)*n)=2.84, as expected !

Click here to download my program (zip archive : 53 Ko)

Back to home page