Octoproths

[robert44444uk]

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]

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

[axn]

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]

k=3539387145, n=65

[Templus]

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!

[axn]

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 !!

[axn]

Nothing for n=67 either

[robert44444uk]

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

[Templus]

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:

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?

[robert44444uk]

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

[axn]

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 !

[robert44444uk]

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^71-1

So Anx1's record still stands.

Regards

Robert

[Templus]

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 log-file. I still have the sieve file, so anyone who wishes to redo it can ask me for the sieve-file. 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)

[ltd]

Are n=74,75,76 free ?

I would like to test them.

Lars

[axn]

Originally Posted by robert44444uk

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

Hmmm.... Must be the version. I am using 2.82. If I put k higher than 2^32-1 it just wont budge :

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

[axn]

And the winner is:

k=61574201535, n=80

[robert44444uk]

Originally Posted by ltd

Are n=74,75,76 free ?

I would like to test them.

Lars

You might want to try a bit higher, given the latest record. This is addictive!!

Regards

Robert Smith

[ltd]

OK i take 100,101,102

Lars

[axn]

Another one for n = 80

k = 632893190475 !!

[axn]

n = 80 finished for k < 10^12. On to bigger n's

[ltd]

Originally Posted by axn1

Hmmm.... Must be the version. I am using 2.82. If I put k higher than 2^32-1 it just wont budge :

Strange i use 2.82 also and i have no problems sieving >2^32.

[axn]

Originally Posted by ltd

Strange i use 2.82 also and i have no problems sieving >2^32.

D'oh! It looks like I've run into a bug in NewPGen. Try putting kmax = 4294967296 (2^32). It doesnt do anything. If you put any other number in there (including really big numbers), it springs into action!

Well, anyway, my new sieve is a lot better suited for this search.

[axn]

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

[ltd]

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

[robert44444uk]

I did n=110 last night to k=10^11, no octoproths thier either

Regards

Robert Smith

[robert44444uk]

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

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

[axn]

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

[ET_]

Originally Posted by axn1

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

May I ask you which boost of performance gave the substitution of Pascal code with asm code?

Luigi

[axn]

Originally Posted by ET_

May I ask you which boost of performance gave the substitution of Pascal code with asm code?

Luigi

The two divisions in TestK - gave appr. 35% speedup. Not much but I'll take any speedup especially since I am running these for 2-3 days at a stretch. Actually, there is one more optimization there - the division of k by p is done by two back-to-back divisions; for most cases you only need one division. I plan to code it up and try it out. Let's see what kind of improvement it brings. For people needing non-asm version, you can use suitable qword operations. But in such cases, it might be worthwhile to use alternatives to division.

[axn]

Originally Posted by axn1

Results for n = 97 (after 65% completion to k<10^13)

1926973493115
2212009461375
2412877121565
5647136892825

One more to the list for n = 97

6832047128535

[axn]

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.

[robert44444uk]

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

[Dougy]

Here's two small ones I found using axn1's program.

8299358445 50
3920165865 54

[Dougy]

And of course as soon as I posted those I found some more...

13419352155 52
14002823745 52
19306888875 52
26648959155 52

[axn]

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.

[axn]

Originally Posted by axn1

One more to the list for n = 97

6832047128535

The rest for n = 97:

8246997577755
8883883726185
9417272582445
9910177359165

These are the last for k < 10^13

[robert44444uk]

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

[robert44444uk]

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

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

[axn]

Originally Posted by robert44444uk

However, how do you write the line script to create an output file? It is years since I saw dos.

octo 50 10 > candidates.txt

Originally Posted by robert44444uk

I wonder what is so special about 52, it seems statistically well outside of normal variances?

Yes. I too have observed this. A few posts back, I had said that 81 was "low weight" compared to 82. My guess is that for some of the n's, some small prime(s) might be eliminating a lot of candidates. Conversely, some n's might be escaping these small primes.

Incidentally, these "heavy weight" n's all seem to be of the form 3x+1.

[robert44444uk]

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 3-PRP! (0.0001s+0.0002s)
374526655755*2^113-1 is 3-PRP! (0.0001s+0.0045s)
- Twin -
374526655755*2^(113+1)+1 is 3-PRP! (0.0001s+0.0079s)
374526655755*2^(113+1)-1 is 3-PRP! (0.0001s+0.0045s)
- BiTwin -
2^113+374526655755 is 3-PRP! (0.0030s+0.0002s)
2^113-374526655755 is 3-PRP! (0.0001s+0.0067s)
2^(113+1)+374526655755 is 3-PRP! (0.0001s+0.0042s)
2^(113+1)-374526655755 is 3-PRP! (0.0001s+0.0042s)
- Complete Set -

Regards

Robert Smith

[Dougy]

Well done robert, they're all prime by the way. However the largest known is
k=405777203685 n=120 found by axn1.

[Dougy]

These are the smallest octoproths for their corresponding bases. Why 56 is so large is a real head-scratcher.

8299358445 50
106546113135 51
13419352155 52
216800357445 53
3920165865 54
72038479785 55
590925115935 56
138429315465 57
84183246225 58
107884757295 59

[axn]

Results for n = 130, (k < 10^13)

1075252753275
3408331609305
7076113724805

[Dougy]

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^1-1 = 29
15*2^(1+1)+1 = 61
15*2^(1+1)-1 = 59
2^1+15 = 17
2^1-15 = -13
2^(1+1)+15 = 19
2^(1+1)-15 = -11

If you count negative primes too.

[robert44444uk]

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^n-k 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

[robert44444uk]

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

[Dougy]

So, if my program works properly, there are no (certified prime) octoproths within the ranges n=31-50 and k=15-21207165.

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 k-value 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.

I working on the new version now...