There is a faster way to sieve out numbers of the form q*2^q+1 that are divisible by a given prime p>=3.
Suppose that q*2^q+1 is divisible by p. Then q*2^q = 1 (mod p) or alternatively q =  2^(q) (mod p).
Let q = k (mod p1) where 0 <= k < p1, then q =  2^(q) =  2^k (mod p).
From q = k (mod p1) and q =  2^k (mod p) we can reconstruct q modulo p*(p1) using Chinese theorem:
q = k * p + 2^k * (p1) (mod p*(p1)) .............. (x)
In other words, for every k=0,...,p2, there is an unique solution modulo p*(p1) to the system of congruences
q*2^q + 1 = 0 (mod p)
q = k (mod p1)
and this solution is given by formula (x).
Therefore, sieving can be done as follows: for each prime p in selected range, let k go from 0 to p2, compute
r = ((p1k) * p + (2^k mod p) * (p1)) mod (p*(p1)) (i.e., the smallest nonnegative solution to (x)), and eliminate candidates
r, r + (p*(p1)), r + 2*(p*(p1)), ..., up to selected upper bound (for large p, it may appear that r is greater than the upper bound, in which case no actual elimination happens).
P.S. Of course, the powers (2^k mod p) can be computed incrementally as k goes from 0 to p2:
having 2^k mod p=y computed, the value of 2^(k+1) mod p is computed as (y*2) mod p.
P.P.S. There is another speed up possible if we replace p1 with the multiplicative order of 2 modulo p (that is a divisor of p1). So, instead of letting k go from 0 to p2, we compute incrementally and store values u[i]=2^i mod p, i=1,2,... until we get u[z]=1, meaning that z is the multiplicative order of 2 modulo p. Then we let k go from 0 to z1, compute
r = ((zk) * p + u[k] * z) mod (p*z), and eliminate candidates r, r + (p*z), r + 2*(p*z), ..., up to selected upper bound.
Last fiddled with by maxal on 20061201 at 21:11
