View Single Post
Old 2006-06-10, 21:11   #440
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

110010010112 Posts

Hi all!

Are you using newpgen for sieving? Because it doesn't observe algebraic factors, as I can see! So if k is a power of a number: k=a^d ( here a>1 and d>1 ) and n is divisible by d so n=s*d, then k*2^n-1 is composite, because it is divisible by a*2^s-1.

In some cases it is a real improvement, but not very much, because in these cases you have got a very high chance that k*2^n-1 has got a "small" prime divisor, so newpgen will find it very quickly.

Note that for some k, this is a zero improvement, for example if k=49 then 49*2^(2*s)-1 is divisible by 3, so all algebraic numbers are eliminated. For k=125=5^3 all 125*2^(5*s)-1 are divisible by 31.

As I can see: up to 300 the suitable ( odd ) k values for real improvement: k=9, k=27, k=81, k=225, k=243

Last fiddled with by R. Gerbicz on 2006-06-10 at 21:19
R. Gerbicz is offline