Numerous web sites talk about the weight of k in the Proth numbers
k*2^{n}+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*2^{n}+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)