mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > Octoproth Search

 
 
Thread Tools
Old 2005-04-05, 21:53   #1
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

111010100112 Posts
Default Octoproths

I am posting this again for those looking for a challenge - but this time in the Maths thread:

Try to find the smallest and largest integer (maybe larger than you think) k*2^n+1 such that:

k*2^n+1, k*2^n-1, k*2^(n+1)+1, k*2^(n+1)-1, 2^n+k, 2^n-k, 2^(n+1)+k,
2^(n+1)-k, all probable prime

I have called these octoproths. On the large side of things, I have looked at n=32 and 1<k<4 billion and found only 6, with the following k values:

409668105
664495755
2368386195
2709707805
3383804865
3692088225

Interestingly, but not surprisingly these k are all multiples of k=105
(3*5*7) as this is a requirement for bitwins (I think). And therefore of interest to 15k searchers.

I have no idea about the smallest octoproths.

The really interesting thing about these groups is that it combines twins, Cunninghams and Payam Samidoost's observation about 2^n+/- k, these have the same covering sets as their Proth equaivalents.

Watch out for negative values, because 2^n-k can be really small

Regards

Robert Smith
robert44444uk is offline  
Old 2005-04-06, 22:58   #2
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

3×54 Posts
Default A bit bigger

Maybe I am just being a bit shy, but I did not raise n too much but I devoted a whole 8 hours to sieving and came across a lot of larger values at n=40, namely:

3721055715
8781593205
9073509705
15541397325
20640857145
23820338205
27678219015
28483380255
29056766445
34144356345
38016547275
38354659875
43635963015
43838018925
48817120275
57779210775
58422340185
58443226395
59679412785
61308889305
62456594325
64989748725
76695589755
76715178345
79069804605
89329921695
92992163025
93765951525
97257415185
98114137575
99030787695

They are not all divisible by 105, but are all divisible by 15

I think this means that tonight my compuiter will sieve at the n=50 level

Regards

Robert Smith
robert44444uk is offline  
Old 2005-04-07, 08:40   #3
axn
 
axn's Avatar
 
Jun 2003

121C16 Posts
Default

k=925905105, n=64

925905105*2^64+1
925905105*2^64-1
925905105*2^(64+1)+1
925905105*2^(64+1)-1
2^64 + 925905105
2^64 - 925905105
2^(64+1) + 925905105
2^(64+1) - 925905105

All are prime!!

Searched for 1 < k < 2^32
axn is offline  
Old 2005-04-07, 10:31   #4
axn
 
axn's Avatar
 
Jun 2003

10010000111002 Posts
Default

k=3539387145, n=65
axn is offline  
Old 2005-04-07, 10:47   #5
Templus
 
Templus's Avatar
 
Jun 2004

2×53 Posts
Default

How do you find these 'k'-s? Do you first sieve for a range 1 < k < 2^32 with a given 'n' for the form k*2^n+1, and after that you use that sieve as seed for a sieve for the form k*2^n-1? And use those results as seed for another sieve for another form, etcetera etcetera? Or is there are another (sieve-)program that can help?

Quite interesting numbers though!

Last fiddled with by Templus on 2005-04-07 at 10:47
Templus is offline  
Old 2005-04-07, 12:04   #6
axn
 
axn's Avatar
 
Jun 2003

121C16 Posts
Default

I used NewPGen BiTwin option which sieves for the 4 forms: k.2^n+/-1 and k.2^(n+1)+/-1

This reduces the billions of k's to about 10000. It is then run thru LLR, first for k.2^n+1, whose output is again LLR-ed for k.2^n-1, whose output is *again* LLR-ed for k.2^(n+1)+1, and finally (you guessed it!) LLR-ed for k.2^(n+1)-1

The resulting k's are then normalized (I sieve for even k's also) to odd k's. Then after a bit of script magic and Dario Alpern's batch factorization, I reduce the list to 2^n+k primes, then to 2^n-k primes, and finally the last two forms to come up with the solutions.

Incidentally, just completed n=66 and no solutions

Oh well. On to 67 !!

Last fiddled with by axn on 2005-04-07 at 12:16
axn is offline  
Old 2005-04-07, 13:00   #7
axn
 
axn's Avatar
 
Jun 2003

22·19·61 Posts
Default

Nothing for n=67 either
axn is offline  
Old 2005-04-07, 16:08   #8
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

3·54 Posts
Default Another way

I also use the bitwin option in NewPGen to reduce to an acceptable number of candidates. Sieving to 1 billion is fine, which is the minimum p which the large k range option NewPGen uses. My NewPgen splits the range into 120 or so smaller ranges and then batches all of the survivors together when each range is tested to 1 billion.

At the next stage, I do not check the output for primes. Instead I alter the first line of the NewPgen output file to make this into an ABC file, and use the & option to check for the four other values of the octoproth. This file is then put through pfgw, with the -f100 option, which, for n=50 checks around 10,000 values of k a second. The output file for this run can be inspected to see if there are any values where all four possibilities are prp. It is quicker this way because the pfgw will give up testing the value of k as soon as it spots a composite. If you test the original output file then a lot of values will have to be tested for all four options as none of them, if they are composite, have factors of less than 1 billion.

The final stage is to extract the few (maybe only ten values) where the output file shows the complete set is prp, and make this into a PFGW input file with the first line of the file the same as the output file from the bitwin output file. About half of the values will be octoproths.

Therefore almost all of the work is in the sieving because a very large number of k must be looked at, for a given n. My computer takes 8 hours to sieve k=2 to k=10^11 up to p=1 billion. A further 2 hours takes the file to p=30 billion.

I ran this range for n=50, and found about 8 octoproths. But it looks as if I have been overtaken by events. The bar has been raised!

Regards

Robert Smith
robert44444uk is offline  
Old 2005-04-07, 18:01   #9
Templus
 
Templus's Avatar
 
Jun 2004

2×53 Posts
Default

I tried this method for n=81 and 2 < k < 2^32. I made a sieve file which contains about 16000 lines, but I'm not sure about the ABC rule I have to construct.

I now have:

Code:
ABC $a*2^$b+1 & $a*2^$b-1 & $a*2^($b+1)+1 & $a*2^($b+1)-1 & 2^$b+$a & 2^$b-$a & 2^($b+1)+$a & 2^($b+1)-$a
Is this definition correct? When I run this code and I check the pfgw.log file I only see lines of the form k*2^n+1, k*2^n-1, k*2^(n+1)+1, k*2^(n+1)-1 but not of the form 2^n+k, 2^n-k, 2^(n+1)+k, 2^(n+1)-k.

What am I doing wrong?
Templus is offline  
Old 2005-04-07, 21:35   #10
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

3×54 Posts
Default Answer

The line I use is (followed by first putput from the NewPGen file):

ABC 2^$b+$a & 2^$b-$a & 2^($b+1)+$a & 2^($b+1)-$a
708435 40

Regards

Robert Smith
robert44444uk is offline  
Old 2005-04-08, 03:48   #11
axn
 
axn's Avatar
 
Jun 2003

22·19·61 Posts
Default

Quote:
Originally Posted by robert44444uk
My computer takes 8 hours to sieve k=2 to k=10^11 up to p=1 billion. A further 2 hours takes the file to p=30 billion.
How do you sieve with k as high as 10^11. I thought that NewPGen only supported upto k < 2^32 !
axn is offline  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Small Primes for Octoproths <= 155 ValerieVonck Octoproth Search 100 2007-02-16 23:43
Found Octoproths - Range Archive ValerieVonck Octoproth Search 0 2007-02-14 07:24
Number of octoproths per n Greenbank Octoproth Search 15 2006-01-20 16:29
Need help with NewPGen(octoproths) jasong Software 1 2005-05-10 20:08

All times are UTC. The time now is 14:24.

Tue Jul 14 14:24:34 UTC 2020 up 111 days, 11:57, 1 user, load averages: 1.19, 1.30, 1.38

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.