20151226, 17:39  #1 
"Mark"
Apr 2003
Between here and the
2×3,203 Posts 
Carol / Kynea search (Nearpower primes)
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. 
20160208, 17:15  #2 
"Mark"
Apr 2003
Between here and the
2×3,203 Posts 
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.

20160208, 19:42  #3 
Sep 2002
Database er0rr
13×293 Posts 
These trinomial forms would greatly benefit from a "special" mod

20160208, 21:18  #4 
"Mark"
Apr 2003
Between here and the
2×3,203 Posts 

20160208, 21:37  #5 
Sep 2002
Database er0rr
13×293 Posts 
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.

20160209, 23:25  #6 
"Mark"
Apr 2003
Between here and the
1906_{16} Posts 

20160210, 01:28  #7 
"Mark"
Apr 2003
Between here and the
2×3,203 Posts 
Imagine my total surprise today when I found this:
(2^369581+1)^22 is prime! and this: (2^376050+1)^22 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. Last fiddled with by rogue on 20160210 at 01:30 
20160210, 03:18  #8  
Sep 2002
Database er0rr
13·293 Posts 
Quote:
Anyway, with a quicker PRP routine you can sieve way deeper PS. Congrats for those 2 primes! Last fiddled with by paulunderwood on 20160210 at 03:20 

20160210, 10:23  #9 
Sep 2002
Database er0rr
111011100001_{2} Posts 
I hacked a script in to shape for Carol numbers, but I think it is too giantsbiased rather than gwnum:
Code:
time ./a.out ck_test (2^1002241)^21 is PRP! real 6m59.020s user 6m26.060s sys 0m0.080s Code:
./pfgw64 q"(2^1002241)^21" PFGW Version 3.7.10.64BIT.20150809.x86_Dev [GWNUM 28.7] (2^1002241)^21 is composite: RES64: [AAAAAAAAAAAAAAAB] (48.2093s+0.0003s) 
20160210, 10:53  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×11×433 Posts 

20160210, 11:15  #11 
Sep 2002
Database er0rr
13×293 Posts 
GIGO. Thx Serge.
Code:
gtogshiftright ( k2, a, b ); gmaskbits ( k2, a ); gshiftleft ( kp1, b ); Last fiddled with by paulunderwood on 20160210 at 11:27 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Carol / Kynea Primes  rogue  And now for something completely different  251  20210913 07:59 
Carol / Kynea Coordinated Search  Reservations  rogue  And now for something completely different  294  20210830 08:07 
Search primes of form 2*n^n ± 1  JeppeSN  And now for something completely different  27  20180412 14:20 
Factorial primes search?  flava  Open Projects  18  20101204 05:24 
Why Search for these Huge Primes?  Unregistered  Math  8  20050427 00:55 