20050405, 21:53  #1 
Jun 2003
Oxford, UK
11×173 Posts 
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^n1, k*2^(n+1)+1, k*2^(n+1)1, 2^n+k, 2^nk, 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^nk can be really small Regards Robert Smith 
20050406, 22:58  #2 
Jun 2003
Oxford, UK
11·173 Posts 
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 
20050407, 08:40  #3 
Jun 2003
2^{3}·3·199 Posts 
k=925905105, n=64
925905105*2^64+1 925905105*2^641 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 
20050407, 10:31  #4 
Jun 2003
1001010101000_{2} Posts 
k=3539387145, n=65

20050407, 10:47  #5 
Jun 2004
2·53 Posts 
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^n1? 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 20050407 at 10:47 
20050407, 12:04  #6 
Jun 2003
2^{3}×3×199 Posts 
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 LLRed for k.2^n1, whose output is *again* LLRed for k.2^(n+1)+1, and finally (you guessed it!) LLRed 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^nk 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 20050407 at 12:16 
20050407, 13:00  #7 
Jun 2003
2^{3}×3×199 Posts 
Nothing for n=67 either

20050407, 16:08  #8 
Jun 2003
Oxford, UK
76F_{16} Posts 
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 
20050407, 18:01  #9 
Jun 2004
2×53 Posts 
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^$b1 & $a*2^($b+1)+1 & $a*2^($b+1)1 & 2^$b+$a & 2^$b$a & 2^($b+1)+$a & 2^($b+1)$a What am I doing wrong? 
20050407, 21:35  #10 
Jun 2003
Oxford, UK
11·173 Posts 
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 
20050408, 03:48  #11  
Jun 2003
2^{3}×3×199 Posts 
Quote:


20050408, 07:23  #12 
Jun 2003
Oxford, UK
11×173 Posts 
Dont know
I didn't know there was an upper limit, I just do it!
I am using version 2.81, and I set max Mb ram to 100.0 I ran n=71 last night  only one value survived the sieve and the first pfgw run, and that turned out to be composite for k.2^711 So Anx1's record still stands. Regards Robert 
20050408, 08:53  #13 
Jun 2004
2·53 Posts 
I tried n=81 yesterday for 2<k<2^32. As far as I know, there is no upperbound, since NewPGen splits this large range into smaller pieces (dependent on the max. RAM assigned?) and sieves these ranges until 1 billion.
As I said, I tested n=81 yesterday with OpenPFGW and there was no complete set in the logfile. I still have the sieve file, so anyone who wishes to redo it can ask me for the sievefile. I uploaded the sieve file on http://www.diamondvalley.nl/octoproth I'm taking 82+....sieving until k=2^32 takes about 1,5 or 2 hours for me. Testing these numbers for PRP is done in less than a minute (small n) Last fiddled with by Templus on 20050408 at 09:04 
20050408, 10:49  #14 
Apr 2003
2^{2}·193 Posts 
Are n=74,75,76 free ?
I would like to test them. Lars 
20050408, 11:00  #15  
Jun 2003
2^{3}·3·199 Posts 
Quote:
But on the plus side, I went and wrote up a sieve program for myself. The initial results are *very* encouraging. I sieve all 8 forms simultaneously. Some statistics. After sieveing for k < 10^10, with p < 1M, I get just 90 (count'em) candidates 

20050408, 11:35  #16 
Jun 2003
2^{3}·3·199 Posts 
And the winner is:
k=61574201535, n=80 
20050408, 13:26  #17  
Jun 2003
Oxford, UK
11×173 Posts 
For Lars
Quote:
Regards Robert Smith 

20050408, 15:17  #18 
Apr 2003
2^{2}·193 Posts 
OK i take 100,101,102
Lars 
20050408, 16:01  #19 
Jun 2003
2^{3}·3·199 Posts 
Another one for n = 80
k = 632893190475 !! 
20050408, 16:17  #20 
Jun 2003
2^{3}×3×199 Posts 
n = 80 finished for k < 10^12. On to bigger n's

20050408, 21:26  #21  
Apr 2003
2^{2}×193 Posts 
Quote:


20050409, 06:21  #22  
Jun 2003
2^{3}×3×199 Posts 
Quote:
Well, anyway, my new sieve is a lot better suited for this search. 

20050409, 10:31  #23 
Jun 2003
1001010101000_{2} Posts 
For n=82, there are 4 k's < 10^12
42290329515 481562533725 549711786105 624949113615 EDIT: No luck for n=81 for k < 10^12. This n was a "low weight" one compared to n=82 Last fiddled with by axn on 20050409 at 10:41 
20050409, 13:59  #24 
Apr 2003
2^{2}·193 Posts 
No luck for n=100,101,102.
@axn1 What OS are you using for your siever programm. If it is windows is it possible that i can download it somewhere? Lars 
20050409, 14:34  #25 
Jun 2003
Oxford, UK
11×173 Posts 
no luck either
I did n=110 last night to k=10^11, no octoproths thier either
Regards Robert Smith 
20050410, 08:46  #26 
Jun 2003
Oxford, UK
76F_{16} Posts 
109
Checked 109 last night, one candidate that fell at the last hurdle, unlike the horse I chose for the Grand National, which cost me a tenner when it fell at the first!
Will do 108 tonight. Regards Robert Smith 
20050411, 02:51  #27 
29 Posts 
interesting
Robert,
Nice find, I will have to check it out. I have been touching up RMA a bit, and have'nt been online to catch up on what's going on. TTn 
20050411, 09:04  #28 
Jun 2003
2^{3}×3×199 Posts 
Results for n = 97 (after 65% completion to k<10^13)
1926973493115 2212009461375 2412877121565 5647136892825 @ltd  see the attached Pascal source code  Its not much. You'll have to modify the constants in the program and compile (you can use FreePascal compiler). I plan to later clean it up and make it accept command line parameters Last fiddled with by axn on 20050411 at 09:05 
20050411, 09:43  #29  
Banned
"Luigi"
Aug 2002
Team Italia
13×367 Posts 
Quote:
Luigi 

20050411, 10:11  #30  
Jun 2003
2^{3}·3·199 Posts 
Quote:


20050411, 11:38  #31  
Jun 2003
2^{3}×3×199 Posts 
Quote:
6832047128535 

20050411, 13:01  #32 
Jun 2003
2^{3}×3×199 Posts 
Uploading the latest version of the sieve along with the executable. The output needs to be redirected to some file. The resulting file can be further sieved using NewPGen.

20050411, 13:09  #33 
Jun 2003
Oxford, UK
11×173 Posts 
108
Ran 108 last night to 10^11, and no octos, sadly to say.
Axn1, will you be writing your code in a windows executable? I would certainly be interesting in devoting some raw computer power to take it further. Regards Robert Smith 
20050412, 03:13  #34 
Aug 2004
Melbourne, Australia
2^{3}·19 Posts 
Here's two small ones I found using axn1's program.
8299358445 50 3920165865 54 
20050412, 03:23  #35 
Aug 2004
Melbourne, Australia
2^{3}·19 Posts 
And of course as soon as I posted those I found some more...
13419352155 52 14002823745 52 19306888875 52 26648959155 52 
20050412, 03:24  #36 
Jun 2003
1001010101000_{2} Posts 
k = 405777203685, n = 120
Thats the only one for k < 10^13. Robert, the last attachment had a windows executable (console mode). You can run it from cmd prompt and redirect the output to a file. 
20050412, 09:31  #37  
Jun 2003
1001010101000_{2} Posts 
Quote:
8246997577755 8883883726185 9417272582445 9910177359165 These are the last for k < 10^13 

20050412, 14:58  #38 
Jun 2003
Oxford, UK
11×173 Posts 
Oops
Oops should have tried first!
However, how do you write the line script to create an output file? It is years since I saw dos. I tried this c:\octo 50 10 and got an output on my screen with about 10 candidates. Are these candidates or are they in fact octos? Sorry to be a bit naive, but I cannot read music and I cannot read other people's computer programs! Regards Robert Smith 
20050412, 15:21  #39 
Jun 2003
Oxford, UK
11×173 Posts 
odd statistics
I ran Axn1's prgram, up to 10^10 for n=50 through 58. The number of candidates (octos?) produced by the programme are:
50 11 51 5 52 47 53 7 54 28 55 27 56 5 57 18 58 17 I wonder what is so special about 52, it seems statistically well outside of normal variances? Regards Robert Smith 
20050412, 18:49  #40 
2^{2}×3×37 Posts 
Octo RMA1.74
This sounds like a nice easy addition to RMA 1.74, and will be listed under "Preferences" "Other options" "Octoproth".
I'll need about a week to get on it. If there are any additional behaviours or options, that you think should be included under the octoproth option, please post them. TTn 
20050413, 09:30  #41  
Jun 2003
2^{3}×3×199 Posts 
Quote:
Quote:
Incidentally, these "heavy weight" n's all seem to be of the form 3x+1. 

20050414, 07:18  #42 
Jun 2003
Oxford, UK
1903_{10} Posts 
New Record!
Playing around with Axn1's software has allowed Great Britain to regain the World record for largest octoproth. Hurrah for that, hip, hip, hooray.
374526655755*2^113+1 is 3PRP! (0.0001s+0.0002s) 374526655755*2^1131 is 3PRP! (0.0001s+0.0045s)  Twin  374526655755*2^(113+1)+1 is 3PRP! (0.0001s+0.0079s) 374526655755*2^(113+1)1 is 3PRP! (0.0001s+0.0045s)  BiTwin  2^113+374526655755 is 3PRP! (0.0030s+0.0002s) 2^113374526655755 is 3PRP! (0.0001s+0.0067s) 2^(113+1)+374526655755 is 3PRP! (0.0001s+0.0042s) 2^(113+1)374526655755 is 3PRP! (0.0001s+0.0042s)  Complete Set  Regards Robert Smith 
20050414, 07:36  #43 
Aug 2004
Melbourne, Australia
2^{3}·19 Posts 
Well done robert, they're all prime by the way. However the largest known is
k=405777203685 n=120 found by axn1. 
20050414, 08:14  #44 
Aug 2004
Melbourne, Australia
2^{3}·19 Posts 
Small Octoproths
These are the smallest octoproths for their corresponding bases. Why 56 is so large is a real headscratcher.
8299358445 50 106546113135 51 13419352155 52 216800357445 53 3920165865 54 72038479785 55 590925115935 56 138429315465 57 84183246225 58 107884757295 59 
20050415, 04:26  #45 
Jun 2003
2^{3}×3×199 Posts 
Results for n = 130, (k < 10^13)
1075252753275 3408331609305 7076113724805 
20050415, 08:38  #46 
Aug 2004
Melbourne, Australia
2^{3}×19 Posts 
Small Octos
I've been looking at the small bases. (primes, rather than probable primes) I wrote my own program to look at these.
There are no octoproths with base n = 26 or below. The first one is 109989075 27 and is the only one with base 27. The next are 21207165 28 191093475 28 are the only two with base 28. ...more to come One interesting one is n=1, k=15. 15*2^1+1 = 31 15*2^11 = 29 15*2^(1+1)+1 = 61 15*2^(1+1)1 = 59 2^1+15 = 17 2^115 = 13 2^(1+1)+15 = 19 2^(1+1)15 = 11 If you count negative primes too. 
20050415, 15:38  #47 
Jun 2003
Oxford, UK
11101101111_{2} Posts 
Really suprised
Dougy
I am really surprised that there are no "small" octos. The way I have defined them means that negative numbers, created through the 2^nk calculation, rule that number out, so your interesting case has to remain as that. But thank you for looking at the small case. I just find the result hard to believe, but the negative rule counts out a lot for small n, especially when k goes in multiples of 15 (almost 2^4), so maybe I should have realised. Maybe you should post the full decimal value of this find to Chris Caldwell's Prime curios page: http://primes.utm.edu/curios/ Regards Robert Smith 
20050415, 15:45  #48 
Jun 2003
Oxford, UK
11×173 Posts 
More for Dougy
Dougy
I just realised, (as I am sure you have) that you will need also to look at higher n, because they may have a smaller k value, such that k.2^n+1 is a smaller number. So that you will have to check almost all the way up to n=50 to make totally sure there are no smaller octos. Regards Robert 
20050416, 01:20  #49 
Aug 2004
Melbourne, Australia
2^{3}×19 Posts 
Smallest
So, if my program works properly, there are no (certified prime) octoproths within the ranges n=3150 and k=1521207165.
Furthermore 328724235 29 233752995 30 are the only octoproths with those bases. So this is a proof that 21207165*2^28+1 = 5692755007242241. 109989075*2^27+1 = 14762483751321601. are the smallest two octoproths. Also 21207165 is also the smallest known kvalue forming a octoproth. I wonder if it's actually the smallest possible. I might search with a fixed k and varying n instead. (but that'd require writing a whole new program) It would be nice if someone could verify this independently before I submit it anywhere. 
20050416, 03:30  #50 
3999_{10} Posts 
oct
I working on the new version now...

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Small Primes for Octoproths <= 155  ValerieVonck  Octoproth Search  100  20070216 23:43 
Found Octoproths  Range Archive  ValerieVonck  Octoproth Search  0  20070214 07:24 
Number of octoproths per n  Greenbank  Octoproth Search  15  20060120 16:29 
Need help with NewPGen(octoproths)  jasong  Software  1  20050510 20:08 