mersenneforum.org  

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

Reply
 
Thread Tools
Old 2019-04-20, 01:01   #1
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

11·19·43 Posts
Cool Let's find some large sexy prime pair (and, perhaps, a triplet)

Let's start from Ken Davis' construction. Observe the form that he used (which is similar to the form J.K.Andersen used before him).

Maybe we can find this even cheaper in computrons.
Illustration: Let's take m=3*2^n, so that m+1 is prime. A tiny example m=3*2^534.
Then we will sieve for two forms:
p = k*m*(m^2 - 1)+ 6*m -1, p6 = p+6
...and presto, done:
63166*3*2^534*(9*2^1068-1)+18*2^534-1 is prime, quite trivially, and
63166*3*2^534*(9*2^1068-1)+18*2^534+5 (with 3*2^534+1 as a helper)

Now, repeat with m=
3*2^34350
3*2^42294
3*2^42665
3*2^44685
3*2^48150
3*2^55182
3*2^59973

The only part to write is a simple sieve, then sieve, and then do some PRP'ing.
Batalov is offline   Reply With Quote
Old 2019-04-20, 02:20   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

11·19·43 Posts
Default

One-up
318725*3*2^2208*(9*2^4416-1)+18*2^2208-1
318725*3*2^2208*(9*2^4416-1)+18*2^2208+5

Next up
363629*3*2^3168*(9*2^6336-1)+18*2^3168-1
363629*3*2^3168*(9*2^6336-1)+18*2^3168+5

And slightly larger
2865046*7*2^6614*(49*2^13228-1)+42*2^6614-1
2865046*7*2^6614*(49*2^13228-1)+42*2^6614+5
Batalov is offline   Reply With Quote
Old 2019-04-20, 03:44   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

314510 Posts
Default

I am working on 34350 using -f -o of pfgw for "-1" as feedback to pfgw -f later on an ABC file with +5 & -1 in the header...

Last fiddled with by paulunderwood on 2019-04-20 at 03:46
paulunderwood is online now   Reply With Quote
Old 2019-04-20, 03:56   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

100011000110112 Posts
Default

If you don't sieve, you will waste enormous amount of time on ineligible k values.
I sieved to 1T.
Batalov is offline   Reply With Quote
Old 2019-04-20, 07:51   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

24×83 Posts
Default

Quote:
Originally Posted by Batalov View Post
Maybe we can find this even cheaper in computrons.
Illustration: Let's take m=3*2^n, so that m+1 is prime. A tiny example m=3*2^534.
Then we will sieve for two forms:
p = k*m*(m^2 - 1)+ 6*m -1, p6 = p+6
...
Now, repeat with m=
3*2^34350
3*2^42294
3*2^42665
3*2^44685
3*2^48150
3*2^55182
3*2^59973
You can do it even much denser:
Let r=k*2^n+1 ~ sqrt(N) Proth prime, then search p in the form:

Code:
p=c*r*2^n+6*r-5 where c=1,2,3,.. is running.
Then p-1 is divisible by 2^n, and p+5 is divisible by r, what is a known prime.
Bingo, and the sieve is blazingly fast, because you need only 2^n mod s, where s is prime.

example:
Code:
k=165;n=100 for that r=k*2^n+1 is a Proth prime, and turned out that c=2920 is good.
R. Gerbicz is offline   Reply With Quote
Old 2019-04-20, 11:12   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×17×37 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I am working on 34350 using -f -o of pfgw for "-1" as feedback to pfgw -f later on an ABC file with +5 & -1 in the header...
I did not get far.

I have now written a sieve in pari-gp (which I will convert to PrimeSieve+GMP) and am testing the world record contender:

p=c*(3*2^34350+1)*2^34350+6*(3*2^34350+1)-5
paulunderwood is online now   Reply With Quote
Old 2019-04-20, 19:43   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×17×37 Posts
Default

I just can't my sieves to behave

Moreover, I feel that any record breaking sexy pair needs to involve primorials in order to get the required density when searching.
paulunderwood is online now   Reply With Quote
Old 2019-04-20, 21:23   #8
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

24·83 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I just can't my sieves to behave

Moreover, I feel that any record breaking sexy pair needs to involve primorials in order to get the required density when searching.
That is just wrong assumption, if you'd be correct we would search only on the form say k*p#+1 and not Mersenne.

And for sieve why not use my ancient polysieve: https://primes.utm.edu/bios/page.php?id=3934 . That handle this problem also, I'll give how to feed this problem for the code.
R. Gerbicz is offline   Reply With Quote
Old 2019-04-20, 21:40   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

24·83 Posts
Default

Here it is:
Code:
$ ./polysieve
Sieve P(s)+a*Q(s)+c for multiple c values, with fixed s=k*b^n+d; P,Q is polynom.
Give k: 1
Give b: 2
Give n: 34350
Give d: 0
Give the degree of the P polynom: 1
Give the 0-th coefficient of P: 0
Give the 1-th coefficient of P: 18
Give the degree of the Q polynom: 2
Give the 0-th coefficient of Q: 0
Give the 1-th coefficient of Q: 1
Give the 2-th coefficient of Q: 3
Give the number of c values for the sieve: 2
0-th c value: 1
1-th c value: 7
Give start and end value for 'a' (in billions)! 0 10
Give the limit for sieving primes (maxp): 1000000000000
Give the name of the file to output the numbers! sexy.txt
Using primes for wheelsieve up to 5
On line 18 of the c code set:
#define bound_small_primes 5//11 // used up to this bound all primes in wheel sieve (change it, but it is very critical)
to lower the wheelsieve.
The range for 'a' is really what you like (what was c in my previous post), above we test 'a' from 0 to 10 (in billions), and maxp=1000000000000. Note that we needed to use the s=2^n to make it an integer polynom.

ps. use smaller example to test it out, say 534 instead of the large 34350 (you need to change only that line) to handle that case. My code also works for the general case, on every Proth numbers (with some modification on the polynoms).

Last fiddled with by R. Gerbicz on 2019-04-20 at 21:45
R. Gerbicz is offline   Reply With Quote
Old 2019-04-20, 21:54   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

C4916 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
That is just wrong assumption, if you'd be correct we would search only on the form say k*p#+1 and not Mersenne.

And for sieve why not use my ancient polysieve: https://primes.utm.edu/bios/page.php?id=3934 . That handle this problem also, I'll give how to feed this problem for the code.
When searching for arithmetic progressions we have always used primorials -- I think this sexy types are similar, but I willing to give it another shot without them.

I downloaded and successfully compiled PolySieve.c.

[code deleted due to cross post]

Last fiddled with by paulunderwood on 2019-04-20 at 21:58
paulunderwood is online now   Reply With Quote
Old 2019-04-20, 22:31   #11
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101001100002 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
When searching for arithmetic progressions we have always used primorials -- I think this sexy types are similar, but I willing to give it another shot without them.
In general we use primorials for small numbers, say when you're searching 18 primes in ap, then the sieve bound is also smaller, and it is better to use primorials. In our case with primorials you'd only lost in sieving for these large numbers.

Btw polysieve as you can see is single threaded and there is no save option, so don't stop it, however maybe from Puzzle-Peter there is an updated code with save option somewhere in the forum. Not thought that somebody would run my code for weeks/months(?).
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
a 27 digit twin prime pair enzocreti enzocreti 2 2019-04-08 15:25
Best Way to find large factors mahnouman Information & Answers 19 2013-02-22 06:11
Gigantic Probable Prime Triplet found Cybertronic Twin Prime Search 18 2011-08-20 13:36
Search for sexy or octy prime Joshua2 Twin Prime Search 11 2009-04-02 12:57
How large a factor can P-1 testing find ? dsouza123 Software 3 2003-12-11 00:48

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

Sun Apr 5 20:56:59 UTC 2020 up 11 days, 18:30, 2 users, load averages: 1.86, 1.83, 1.84

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.