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

3·7·281 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 offline   Reply With Quote
Old 2016-02-08, 17:15   #2
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3·7·281 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 offline   Reply With Quote
Old 2016-02-08, 19:42   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,697 Posts
Default

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

3·7·281 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 offline   Reply With Quote
Old 2016-02-08, 21:37   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,697 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 offline   Reply With Quote
Old 2016-02-09, 23:25   #6
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3·7·281 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 offline   Reply With Quote
Old 2016-02-10, 01:28   #7
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

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

2×1,697 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 offline   Reply With Quote
Old 2016-02-10, 10:23   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

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

53·73 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

65028 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 offline   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 00:58.

Tue Sep 22 00:58:05 UTC 2020 up 11 days, 22:09, 0 users, load averages: 2.41, 1.88, 1.67

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.