Carol / Kynea search (Near-power primes)
 

These are special forms of [URL="http://mathworld.wolfram.com/Near-SquarePrime.html"]Near Square[/URL] primes.

It has been more than four years since the last [URL="http://harvey563.tripod.com/Carol_Kynea.txt"]update[/URL].

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.

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.

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

[QUOTE=paulunderwood;425650]These trinomial forms would greatly benefit from a "special" mod :smile:[/QUOTE]

Trinomial? For sieving or pfgw?

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

[QUOTE=rogue;425670]Trinomial? For sieving or pfgw?

As for the updated sieve, I have run into a problem where my discrete log is not working correctly. :cry:[/QUOTE]

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. :smile:

[QUOTE=paulunderwood;425673]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. :smile:[/QUOTE]

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

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.

[QUOTE=rogue;425766]The code is open source, so if you want to poke around and make some changes...[/QUOTE]

I hardly know where to begin. Is it [URL="http://sourceforge.net/p/openpfgw/code/HEAD/tree/pform/pfgw/gw_prp.cpp"]prp_using_gwnum[/URL]? 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 :smile:

PS. Congrats for those 2 primes!

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

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

real 6m59.020s
user 6m26.060s
sys 0m0.080s
[/CODE]

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

[CODE]./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) [/CODE] :no:

[QUOTE=paulunderwood;425827]I hacked a script in to shape for Carol numbers, but I think it is too giants-biased rather than gwnum:

[CODE]time ./a.out ck_test
(2^100224-1)^2-1 is PRP!
[/CODE] :no:[/QUOTE]
Didn't you want to use -2?
[SPOILER]-1 gives you an even number: (2^100224-1)^2-1 = (2^100224-2)*2^100224[/SPOILER]

:rolleyes: GIGO. Thx Serge.

[CODE]
gtogshiftright ( k2, a, b );

gmaskbits ( k2, a );

gshiftleft ( kp1, b );
[/CODE]

Are there gwnum equivalents?