CRUS-like sieving challenge

[gd_barnes]

Originally Posted by Batalov

Well, 2^(2^n)-k sieve in k should be an appallingly easy sieve to write from scratch and even without GMP (raising 2^(2^n) mod p is very easy and then just zero some bits), but will it do better than a "sieve" like this?

# gp -p 80000000
write("kcan","ABC 2^65536-$a")
forstep(k=17,99999999,12, \
   if(k%60==17||k%60==29||k%60==53, \
   m=1;forprime(p=7,80000000,if(lift(Mod(2,p)^65536-k)<2,m=0;break)); \
   if(m>0,write("kcan",k))) \
)

and after a bit of time start "pfgw -f0 -llog kcan" in parallel?

Is this PARI code? I don't have PARI and am not familiar with it.

[Batalov]

Yes, it is. It is an invaluable tool and is easy to install (not as easy to use, but that's a different story; however, there are experts here on forum who will help). But this is only for prototyping.

I am sure that a plain C 50-liner siever will take care of the problem much easier and faster. I'll probably give it a crack over weekend. One could use the k%60==17||k%60==29||k%60==53 packing in it (or even tighter), or rather I am inclined to just keep only 1 (mod 12) 2Gb byte array (for k<24G) and then clear proper, equally spaced bytes relentlessly for each p until 2^32 or until too bored.

[Batalov]

Quick'n'dirty... and lazy (no bit packing or any fancy stuff) and limited to sieving to 2B. Attached. Can be vastly improved (but of course Geoff could write a totally superior sieve with his left foot in 15 minutes).