mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2015-12-26, 17:39   #1
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

16DA16 Posts
Default 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.
rogue is online now   Reply With Quote
Old 2016-02-08, 17:15   #2
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

16DA16 Posts
Default

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.
rogue is online now   Reply With Quote
Old 2016-02-08, 19:42   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×11×101 Posts
Default

These trinomial forms would greatly benefit from a "special" mod
paulunderwood is online now   Reply With Quote
Old 2016-02-08, 21:18   #4
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

133328 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
rogue is online now   Reply With Quote
Old 2016-02-08, 21:37   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·11·101 Posts
Default

Quote:
Originally Posted by rogue View Post
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.
paulunderwood is online now   Reply With Quote
Old 2016-02-09, 23:25   #6
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·32·52·13 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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 is online now   Reply With Quote
Old 2016-02-10, 01:28   #7
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2×32×52×13 Posts
Default

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
rogue is online now   Reply With Quote
Old 2016-02-10, 03:18   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×11×101 Posts
Default

Quote:
Originally Posted by rogue View Post
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
paulunderwood is online now   Reply With Quote
Old 2016-02-10, 10:23   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·11·101 Posts
Default

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)
paulunderwood is online now   Reply With Quote
Old 2016-02-10, 10:53   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×5×227 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
Batalov is offline   Reply With Quote
Old 2016-02-10, 11:15   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×11×101 Posts
Default

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
paulunderwood is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Carol / Kynea Primes rogue And now for something completely different 239 2020-08-03 06:58
Carol / Kynea Coordinated Search - Reservations rogue And now for something completely different 257 2020-06-20 03:13
Search primes of form 2*n^n ± 1 JeppeSN And now for something completely different 27 2018-04-12 14:20
Factorial primes search? flava Open Projects 18 2010-12-04 05:24
Why Search for these Huge Primes? Unregistered Math 8 2005-04-27 00:55

All times are UTC. The time now is 12:51.

Sat Aug 8 12:51:18 UTC 2020 up 22 days, 8:38, 1 user, load averages: 2.21, 1.99, 1.92

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.