mersenneforum.org Carol / Kynea search (Near-power primes)
 Register FAQ Search Today's Posts Mark Forums Read

 2015-12-26, 17:39 #1 rogue     "Mark" Apr 2003 Between here and the 2×5×17×41 Posts Carol / Kynea search (Near-power 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.
 2016-02-08, 17:15 #2 rogue     "Mark" Apr 2003 Between here and the 2×5×17×41 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.
 2016-02-08, 19:42 #3 paulunderwood     Sep 2002 Database er0rr 24·281 Posts These trinomial forms would greatly benefit from a "special" mod
2016-02-08, 21:18   #4
rogue

"Mark"
Apr 2003
Between here and the

1B3A16 Posts

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

2016-02-08, 21:37   #5
paulunderwood

Sep 2002
Database er0rr

24×281 Posts

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

2016-02-09, 23:25   #6
rogue

"Mark"
Apr 2003
Between here and the

2×5×17×41 Posts

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

 2016-02-10, 01:28 #7 rogue     "Mark" Apr 2003 Between here and the 2·5·17·41 Posts 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. Last fiddled with by rogue on 2016-02-10 at 01:30
2016-02-10, 03:18   #8
paulunderwood

Sep 2002
Database er0rr

10001100100002 Posts

Quote:
 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!

Last fiddled with by paulunderwood on 2016-02-10 at 03:20

 2016-02-10, 10:23 #9 paulunderwood     Sep 2002 Database er0rr 24·281 Posts 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 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)
2016-02-10, 10:53   #10
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×7×479 Posts

Quote:
 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: Code: 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

 2016-02-10, 11:15 #11 paulunderwood     Sep 2002 Database er0rr 119016 Posts GIGO. Thx Serge. Code:  gtogshiftright ( k2, a, b ); gmaskbits ( k2, a ); gshiftleft ( kp1, b ); Are there gwnum equivalents? Last fiddled with by paulunderwood on 2016-02-10 at 11:27

 Similar Threads Thread Thread Starter Forum Replies Last Post rogue And now for something completely different 335 2022-06-05 21:36 rogue And now for something completely different 256 2022-05-17 19:50 JeppeSN And now for something completely different 27 2018-04-12 14:20 flava Open Projects 18 2010-12-04 05:24 Unregistered Math 8 2005-04-27 00:55

All times are UTC. The time now is 20:32.

Tue Feb 7 20:32:23 UTC 2023 up 173 days, 18 hrs, 1 user, load averages: 1.13, 1.10, 1.08