mersenneforum.org - View Single Post - Williams' sequence 4*5^n-1 (A046865)

Citrix · 2006-07-25, 22:59

I am not completely sure, but I think jjsieve already does this for me. k=25 seems faster to sieve than k=5. So I think you do not have to implement anything.

I think when you do discrete log, based on factors of p-1, the first factor 2, eliminates the primes if it does not have the right power of 2 in p-1.

edit:
I am working on k=3^16 for base 2^16 from 0 to 2 Million, I am getting about 2150kp/s on a 1.4 ghz p4. What would the speed be for your program, with the above implementation ie. only considering primes 32*a+1?

2006-07-25, 22:59	#21
Citrix Jun 2003 3064₈ Posts	I am not completely sure, but I think jjsieve already does this for me. k=25 seems faster to sieve than k=5. So I think you do not have to implement anything. I think when you do discrete log, based on factors of p-1, the first factor 2, eliminates the primes if it does not have the right power of 2 in p-1. edit: I am working on k=3^16 for base 2^16 from 0 to 2 Million, I am getting about 2150kp/s on a 1.4 ghz p4. What would the speed be for your program, with the above implementation ie. only considering primes 32a+1? Last fiddled with by Citrix on 2006-07-25 at 23:29*