Carol / Kynea search (Near-power primes)

[rogue]

These are special forms of Near Square primes.

It has been more than four years since the last update.

I plan to pull MultiSieve out of the grave to do sieving for up to k=1000000. If anyone wants to write a more efficient sieving program, go for it.

[rogue]

I'm still working on a more efficient sieve, but I have been using MultiSieve for what I've done so far. I've tested up to n=360,000 and have verified all Carol/Kynea primes to that point.

[paulunderwood]

These trinomial forms would greatly benefit from a "special" mod

[rogue]

Originally Posted by paulunderwood

These trinomial forms would greatly benefit from a "special" mod

Trinomial? For sieving or pfgw?

As for the updated sieve, I have run into a problem where my discrete log is not working correctly.

[paulunderwood]

Originally Posted by rogue

Trinomial? For sieving or pfgw?

As for the updated sieve, I have run into a problem where my discrete log is not working correctly.

PFGW: e.g. Carol: a*2^(2*k) == a*2^(k+1) + a (mod...). With a couple of passes of this and you are almost done. It is all shifts and adds -- much quicker than the generic mod.

[rogue]

Originally Posted by paulunderwood

PFGW: e.g. Carol: a*2^(2*k) == a*2^(k+1) + a (mod...). With a couple of passes of this and you are almost done. It is all shifts and adds -- much quicker than the generic mod.

The code is open source, so if you want to poke around and make some changes...

[rogue]

Imagine my total surprise today when I found this:

(2^369581+1)^2-2 is prime!

and this:

(2^376050+1)^2-2 is prime!

One was found Sunday and one today and I didn't even notice.

I also found a bug in the PRPNet client that prevented it from doing the primality test correctly for them (they were shown as PRP) and I also found that MultiSieve somehow missed 7 as a factor of about 20% of the candidates (all +1 form). That will save me a lot of tests as I go forward.

[paulunderwood]

Originally Posted by rogue

The code is open source, so if you want to poke around and make some changes...

I hardly know where to begin. Is it prp_using_gwnum? It might be quicker for me to write my own script and ask someone else to incorporate it into PFGW. Or even quicker: someone else writes the code.

Anyway, with a quicker PRP routine you can sieve way deeper

PS. Congrats for those 2 primes!

[paulunderwood]

I hacked a script in to shape for Carol numbers, but I think it is too giants-biased rather than gwnum:

time ./a.out ck_test 
(2^100224-1)^2-1 is PRP!

real	6m59.020s
user	6m26.060s
sys	0m0.080s

I will do some more hacking in an attempt to beat PFGW, which btw gives:

./pfgw64 -q"(2^100224-1)^2-1"
PFGW Version 3.7.10.64BIT.20150809.x86_Dev [GWNUM 28.7]

(2^100224-1)^2-1 is composite: RES64: [AAAAAAAAAAAAAAAB] (48.2093s+0.0003s)

[Batalov]

Originally Posted by paulunderwood

I hacked a script in to shape for Carol numbers, but I think it is too giants-biased rather than gwnum:

time ./a.out ck_test 
(2^100224-1)^2-1 is PRP!

Didn't you want to use -2?
-1 gives you an even number: (2^100224-1)^2-1 = (2^100224-2)*2^100224

[paulunderwood]

GIGO. Thx Serge.

        gtogshiftright ( k2, a, b );

        gmaskbits ( k2, a );

        gshiftleft ( kp1, b );

Are there gwnum equivalents?