mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Octoproth Search (https://www.mersenneforum.org/forumdisplay.php?f=63)

 robert44444uk 2005-04-05 21:53

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 2005-04-06 22:58

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

 axn 2005-04-07 08:40

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 2005-04-07 10:31

k=3539387145, n=65

 Templus 2005-04-07 10:47

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 2005-04-07 12:04

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 :no:

Oh well. On to 67 !!

 axn 2005-04-07 13:00

 robert44444uk 2005-04-07 16:08

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

 Templus 2005-04-07 18:01

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
[/code]

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 2005-04-07 21:35

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 2005-04-08 03:48

[QUOTE=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.
[/QUOTE]

How do you sieve with k as high as 10^11. I thought that NewPGen only supported upto k < 2^32 !

 robert44444uk 2005-04-08 07:23

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

So Anx1's record still stands.

Regards

Robert

 Templus 2005-04-08 08:53

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 [URL]http://www.diamondvalley.nl/octoproth[/URL]

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 2005-04-08 10:49

Are n=74,75,76 free ?

I would like to test them.

Lars

 axn 2005-04-08 11:00

[QUOTE=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
[/QUOTE]

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

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 :banana:

 axn 2005-04-08 11:35

And the winner is:

k=61574201535, n=80 :banana: :banana:

 robert44444uk 2005-04-08 13:26

For Lars

[QUOTE=ltd]Are n=74,75,76 free ?

I would like to test them.

Lars[/QUOTE]

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

Regards

Robert Smith

 ltd 2005-04-08 15:17

OK i take 100,101,102

Lars

 axn 2005-04-08 16:01

Another one for n = 80

k = 632893190475 !!

 axn 2005-04-08 16:17

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

 ltd 2005-04-08 21:26

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

[/QUOTE]

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

 axn 2005-04-09 06:21

[QUOTE=ltd]Strange i use 2.82 also and i have no problems sieving >2^32.[/QUOTE]

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 2005-04-09 10:31

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 2005-04-09 13:59

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 2005-04-09 14:34

no luck either

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

Regards

Robert Smith

 robert44444uk 2005-04-10 08:46

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

 TTn 2005-04-11 02:51

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 :grin:

 axn 2005-04-11 09:04

1 Attachment(s)
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 :redface:

 ET_ 2005-04-11 09:43

[QUOTE=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 :redface:[/QUOTE]

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

Luigi

 axn 2005-04-11 10:11

[QUOTE=ET_]May I ask you which boost of performance gave the substitution of Pascal code with asm code?

Luigi[/QUOTE]

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 2005-04-11 11:38

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

1926973493115
2212009461375
2412877121565
5647136892825
[/QUOTE]

One more to the list for n = 97

6832047128535

 axn 2005-04-11 13:01

1 Attachment(s)
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 2005-04-11 13:09

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

 Dougy 2005-04-12 03:13

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

8299358445 50
3920165865 54

 Dougy 2005-04-12 03:23

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

13419352155 52
14002823745 52
19306888875 52
26648959155 52

 axn 2005-04-12 03:24

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 2005-04-12 09:31

[QUOTE=axn1]One more to the list for n = 97

6832047128535[/QUOTE]

The rest for n = 97:

8246997577755
8883883726185
9417272582445
9910177359165

These are the last for k < 10^13

 robert44444uk 2005-04-12 14:58

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

 robert44444uk 2005-04-12 15:21

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

 TTn 2005-04-12 18:49

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.

:rolleyes:
TTn

 axn 2005-04-13 09:30

[QUOTE=robert44444uk]However, how do you write the line script to create an output file? It is years since I saw dos. [/QUOTE]
octo 50 10 > candidates.txt

[QUOTE=robert44444uk]I wonder what is so special about 52, it seems statistically well outside of normal variances?[/QUOTE]
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. :whistle:

 robert44444uk 2005-04-14 07:18

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 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 2005-04-14 07:36

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

 Dougy 2005-04-14 08:14

Small Octoproths

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 2005-04-15 04:26

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

1075252753275
3408331609305
7076113724805

 Dougy 2005-04-15 08:38

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^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 2005-04-15 15:38

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^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:

[url]http://primes.utm.edu/curios/[/url]

Regards

Robert Smith

 robert44444uk 2005-04-15 15:45

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

 Dougy 2005-04-16 01:20

Smallest

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.

 TTn 2005-04-16 03:30

oct

I working on the new version now...

:cool:

 Dougy 2005-04-16 06:50

Some maths

If k*2^n+1 is an octoproth then

k = 1 mod 2. If k is even then 2^(n+1) + k is divisible by 2.

k = 0 mod 3. If k = 1 mod 3 then either 3 divides k*2^n+1 or k*2^(n+1)+1. Similarly for k = 2 mod 3

k = 0 mod 5.

k = 0 mod 7 or (n = 1 mod 3 and k = +/- 1 mod 7).

I can't make any other useful criteria from any other primes. Does anybody know of other goodies like this?

 Dougy 2005-04-16 08:43

Completed 31

Only two octoproths for n=31, this base is now complete.
196168335 31
1813059975 31

 axn 2005-04-16 13:56

[QUOTE=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.[/QUOTE]

I have verified that there are no octo's between 10 <= n <= 26. Also there are no octo's in the range 31-50 for k < 10^7. I am right now in the process of checking whether 21207165 is the smallest possible for n <= 1000

 Dougy 2005-04-17 08:43

Weights of certain bases.

1 Attachment(s)
Today I took a look at the number of candidates remaining after running axn1's sieve to 10^10. I ran the sieve over n=50 to n=150.

I will call the "weight" of a base n, to be the number of candidates remaining after running the sieve through 10^10.

The number of candidates remaining:
Average weight = 18.15
Minimum weight = 3 (n=68) the lightest.
Maximum weight = 54 (n=112) the heaviest.

Also
8299358445 50
3920165865 54
7130617935 62
925905105 64
3539387145 65
were the only prime-octoproths found.

I've attached an excel spreadsheet with the details, and 101 text files with the output from the sieve for n=50 to 100.

 Dougy 2005-04-17 12:25

Organised search.

1 Attachment(s)
Firstly it seems that the 'heavy' bases are more likely to produce an octo than the 'light' bases. So n=52, 67, 70, 82, 97, 112, 115, 142, ... (bases with weight >= 40) would be a good place to start searching. With this reasoning (whether sound or not) I discovered:
65498827395 67 :smile:

...

:alien: In an attempt to make this search a bit more organised I've created a text file listing what has already been searched. I'll try to update this regularly, and as often as possible.
Btw, tell me if I've missed anything or you've searched a region more than what is listed.

In this file, a typical base would look like this:

<k> <n> <discoverer>
<k> <n> <discoverer>
...
<k> <n> <discoverer> (searched/2^n)

if an octo exists, and

<n> (searched/2^n)

otherwise. This way we can hopefully not redo others work.

PS: If I haven't missed any, we now know of 97 octoproth-primes. Hopefully we'll make the 100 mark soon. :geek:

PS2: Most wanted octoproths-primes: base 32, 63.

 smh 2005-04-17 12:32

It seems that the program is not sieveing, but trail factoring to a certain prime, am i right?

I've been playing a bit with SMALL_PRIME and MAX_SMALL_PRIME, which does let the program factor further or less deep, (and spit out more or less possible candidates) but surprisingly, it doesn't really finishes a range faster when i factor less deep.

What i want is quickly generate an output file which cancels most candidates by factoring to lets say 1000 or 10000 and continueing with newpgen. This makes it easier to stop/resume, to see how many candidates are removed in respect to prp-ing (important when n gets larger) and it might be faster.

 axn 2005-04-17 13:12

[QUOTE=smh]It seems that the program is not sieveing, but trail factoring to a certain prime, am i right?[/QUOTE]
That's correct. However, the at the price of about 3 modulo calculations per prime you can test all 8 forms.

[QUOTE=smh]I've been playing a bit with SMALL_PRIME and MAX_SMALL_PRIME, which does let the program factor further or less deep, (and spit out more or less possible candidates) but surprisingly, it doesn't really finishes a range faster when i factor less deep.[/QUOTE]
Since the majority of candidates get sieved out (or trial factored out) within a handful of primes, only a few will be tested by the higher primes. Again, it all comes back to all 8 forms being simultanously checked.

[QUOTE=smh]What i want is quickly generate an output file which cancels most candidates by factoring to lets say 1000 or 10000 and continueing with newpgen. This makes it easier to stop/resume, to see how many candidates are removed in respect to prp-ing (important when n gets larger) and it might be faster.[/QUOTE]
There is no real reason to run the sieve output thru NewPGen. The only improvement that I can think of is to augment the trial division approach with a sieve for the first few primes. I have no idea how much improvement that'll make. However, it still will be better to trial divide to higher primes than use NewPGen (4 forms Vs 8 forms = big difference!).

Also, if you are searching higher n's, the chance of finding an octo is *really* low!

 robert44444uk 2005-04-17 16:21

Scarce

So it looks like octos are scarce, but I am wondering if, like twins, they are infinite?

There are a finite number of k to check for each n, and given that each n only multiples the candidates to check by 2, and given the prime occurence rule, 1/ln(x), which has to be scaled by a factor of between 4 and 8 (k.2^n is bigger than 2^n-k), then, we should be able to sigma a formula.

I am not a mathematician, and I know there are big dangers around playing with inifinity and converging and diverging series, let alone proving anything.

If either case you might imagine that there may be dodecaproths (whatever), which are 3 chains, I imagine these might be enormously rare and maybe nonexistent if there are only finite octos. Interesting challenge that to prove that as well!

If anyone proves it and writes a paper I want a credit so that I might get an Erdos number!!!!

Regards

Robert Smith

 smh 2005-04-17 18:50

[QUOTE=axn1]Since the majority of candidates get sieved out (or trial factored out) within a handful of primes, only a few will be tested by the higher primes. Again, it all comes back to all 8 forms being simultanously checked.
[/quote]

Thanks, that makes sence, didn't think of that.

[QUOTE=axn1]There is no real reason to run the sieve output thru NewPGen. .........it still will be better to trial divide to higher primes than use NewPGen (4 forms Vs 8 forms = big difference!).
[/quote]

Probably true, the reason i asked is because i quickly wanted to get a file with (a lot) of candidates, instead of waiting a long time before all candidates are tested. Time on a prp test is short with these low n's anyway.

[QUOTE=axn1]Also, if you are searching higher n's, the chance of finding an octo is *really* low![/QUOTE]

Isn't that what makes them more special?

 axn 2005-04-18 05:08

New and improved!

1 Attachment(s)
New and improved sieve !

3x to 8x speed up (depending on how deep you sieve).

You can sieve specific ranges - start and end values for k.

Three executables - fast, medium and deep sieves (p = 10^5, 10^6 and 10^7 resp.)

 Dougy 2005-04-18 10:30

Troubles with the new program.

I've had both success and troubles with the new software. Firstly
22573117995 37
23055820515 37
45547390455 37
66695049135 37
73828108635 37
78745654785 37
108269914095 37
132750210165 37
136640238735 37
were discovered using the new program. :banana:

However I tested the program on the known n=35 with 231235935 and 422362395 being the only octoproths. Unfortunately it sieved out the latter. (all three versions did it). :sad: Furthermore often it seems that terms with small factors (7, 11, 13) are not sieved. :unsure: For example the following remained.

32803605*2^56+1 = 4884169 * 483961315030365049
32803605*2^56-1 = 7 * 13 * 25975262110665308033069
32803605*2^(56+1)+1 = 4727497704141086062018561
32803605*2^(56+1)-1 = 8220335593 * 575097896023463
2^56+32803605 = 72057594070731541
2^56-32803605 = 72057594005124331
2^(56+1)+32803605 = 17147939 * 8404227943
2^(56+1)-32803605 = 22878377 * 6299187571

 axn 2005-04-18 11:27

[QUOTE=Dougy]I've had both success and troubles with the new software. Firstly
22573117995 37
23055820515 37
45547390455 37
66695049135 37
73828108635 37
78745654785 37
108269914095 37
132750210165 37
136640238735 37
were discovered using the new program. :banana:

However I tested the program on the known n=35 with 231235935 and 422362395 being the only octoproths. Unfortunately it sieved out the latter. (all three versions did it). :sad: Furthermore often it seems that terms with small factors (7, 11, 13) are not sieved. :unsure: For example the following remained.

32803605*2^56+1 = 4884169 * 483961315030365049
32803605*2^56-1 = 7 * 13 * 25975262110665308033069
32803605*2^(56+1)+1 = 4727497704141086062018561
32803605*2^(56+1)-1 = 8220335593 * 575097896023463
2^56+32803605 = 72057594070731541
2^56-32803605 = 72057594005124331
2^(56+1)+32803605 = 17147939 * 8404227943
2^(56+1)-32803605 = 22878377 * 6299187571[/QUOTE]

Hmmm.. That shouldn't happen :no: I'll look into it.

 Dougy 2005-04-18 12:09

More newies...

1 Attachment(s)
610118148045 41
802757470515 41
832494696285 41

 axn 2005-04-18 12:25

Bug Fix

1 Attachment(s)
There was an unnecessary increment of k inside the loop. Fixed it. Can someone test it and confirm ?

@Dougy - You might want to redo the searches done with the last version :sad:

 Templus 2005-04-18 14:00

Using the new version of axn1's program, I found the following octoproths for k=235 until n=3000000000000 (=3*10^12):

562223326335 235
722744559915 235
926010118305 235
2441346583515 235

I'm looking further on k=235!

One question: what's the difference between the 3 sieve executables? I'm currently using octo_deep.exe.

 axn 2005-04-18 15:34

[QUOTE=Templus]One question: what's the difference between the 3 sieve executables? I'm currently using octo_deep.exe.[/QUOTE]

They differ only in the depth of the sieve, ie, the number of p's used to sieve. p < 10^5, 10^6 and 10^7 (resp. for fast, med & deep).

PS:- The numbers you posted are not octos. They are only prime for 2^n+/-k and 2^(n+1)+/-k. They are not prime for the other forms, k*2^n+/-1 and k*2^(n+1)+/-1

 smh 2005-04-18 15:45

I tested n=141 with the old executable upto k=5,555*10^13

This is the closest i got:

[CODE]43354856050725*2^141+1 is 3-PRP! (0.0004s+0.0004s)
43354856050725*2^141-1 is 3-PRP! (0.0002s+0.0038s)
43354856050725*2^(141+1)+1 is 3-PRP! (0.0002s+0.0022s)
43354856050725*2^(141+1)-1 is 3-PRP! (0.0002s+0.0021s)
2^141+43354856050725 is 3-PRP! (0.0001s+0.0021s)
2^141-43354856050725 is 3-PRP! (0.0001s+0.0030s)
2^(141+1)+43354856050725 is 3-PRP! (0.0001s+0.0023s)
2^(141+1)-43354856050725 is composite: [2FAAB440A92EB3DC] (0.0001s+0.0022s)[/CODE]

I'll try 135 next

 axn 2005-04-18 15:52

[QUOTE=smh]I'll try 135 next[/QUOTE]

If you are searching higher n's, try to search n = 4,7, or 10 (mod 15), esp n = 7 (mod 15). These are heavy weight n's. I think n=142 will make a good candidate.

 Templus 2005-04-18 16:41

[QUOTE=axn1]They differ only in the depth of the sieve, ie, the number of p's used to sieve. p < 10^5, 10^6 and 10^7 (resp. for fast, med & deep).

PS:- The numbers you posted are not octos. They are only prime for 2^n+/-k and 2^(n+1)+/-k. They are not prime for the other forms, k*2^n+/-1 and k*2^(n+1)+/-1[/QUOTE]

I am terribly sorry, I forgot to extend the ABC-line :redface: :redface:
I will test k=235 further on!

 smh 2005-04-18 19:32

[QUOTE=axn1]If you are searching higher n's, try to search n = 4,7, or 10 (mod 15), esp n = 7 (mod 15). These are heavy weight n's. I think n=142 will make a good candidate.[/QUOTE]

Okay, i'll test 142 then. I'm running the 'sieve' for a day or so on a p3 700 and see what pops up.

For 135 i didn't find any upto 1.196*10^13

12 had primes for the first 6 forms, of which 2 had also primes for the 7th form

 Dougy 2005-04-18 23:31

Wow 37!!

So far every test I have put the new program through was passed. So I believe it is working fine.

I ran the complete test on bases upto n=37. (and still going). And that base produced a whopping 83 octoproth primes. :showoff:

Secondly, both bases 32 and 33 have no octoproth primes. :sad:

 Dougy 2005-04-19 02:21

Hmmm a bug in Dario Alpern's ECM

When I put these (and others) into the batch factorisation:
2^39-540206575755
2^39-539552526135

and test for primality it says (even if i just type in the decimal too!)
9549238133 is composite
10203287753 is composite

However if I factorize them instead
9549238133 = 9549238133
10203287753 = 10203287753

implying they're prime.

This means that I will have missed some octoproths... :sad: But fortunately I kept the sieved files.

URL: [url]http://www.alpertron.com.ar/ECM.HTM[/url]

 axn 2005-04-19 03:56

[QUOTE=Dougy]When I put these (and others) into the batch factorisation:
2^39-540206575755
2^39-539552526135

and test for primality it says (even if i just type in the decimal too!)
9549238133 is composite
10203287753 is composite

However if I factorize them instead
9549238133 = 9549238133
10203287753 = 10203287753

implying they're prime.

This means that I will have missed some octoproths... :sad: But fortunately I kept the sieved files.

URL: [url]http://www.alpertron.com.ar/ECM.HTM[/url][/QUOTE]

I too ran into this problem yesterday, while working with one of the lower n's (32, I think).

The "deep" version sieves upto p < 10^7, which means that for n <= 45 all the candidates will be automatically prime for 2^n+/-k forms!

You definitely need to recheck base 32 and 33!

 Dougy 2005-04-19 06:16

Interesting things...

1 Attachment(s)
After rechecking the small bases, I've updated the text file again. It should be fixed. I've completed upto n=41. Some interesting properties...

Number of octoproth-primes for n=27,28,29,...
1,2,1,1,2,0,0,7,17,11,90,28,83,331,109,...

n=40 alone has 331 octoproth-primes :exclaim: To think only the other day I was hoping to break the 100 mark.

Number of k-values unsieved (octo_deep) for n=27,28,29,... over all possible k-values.
2,4,4,2,19,22,13,110,137,85,802,360,844,4434,1651,7552,...

 axn 2005-04-19 08:12

[QUOTE=Dougy]After rechecking the small bases, I've updated the text file again. It should be fixed. I've completed upto n=41. Some interesting properties...

Number of octoproth-primes for n=27,28,29,...
1,2,1,1,2,0,0,7,17,11,90,28,83,331,109,...

n=40 alone has 331 octoproth-primes :exclaim: To think only the other day I was hoping to break the 100 mark.

Number of k-values unsieved (octo_deep) for n=27,28,29,... over all possible k-values.
2,4,4,2,19,22,13,110,137,85,802,360,844,4434,1651,7552,...[/QUOTE]

Some missing values for n=32,33,34,35, and 37.

[code]n = 32
---------
409668105
664495755
2368386195
2709707805
3383804865
3692088225
3762658725

n = 33
---------
715414875
6876947175

n = 34
---------
293705775
1183281975
1397861655
3767954715
4597935705
8596001505

n=35
---------
17182250085
17783238795
20646922695
21811399155
22622064465
23416146075
24115395465
24449183535
25380028905

n=37
-----------
7218568995
126139443165[/code]

n = 36,38,39, and 40 are fine.

Also, I have checked all high k's for n =27 thru 64 (high k's are k's that can't be reliably sieved because 2^n-k becomes smaller than the largest sieve prime). There are no hidden octo's in there :smile:

 Dougy 2005-04-19 10:09

Wow lots of holes.

1 Attachment(s)
Wow thanks, I didn't think there could be so many missing... it's all updated now. :smile:

So there might be octo's for all bases after 27. I've added the smallest octo for each base upto 71. :bounce:

Most Wanted: n=72... searched k<1000000000000. :question:

 smh 2005-04-19 20:09

142

I've found the following for n=142, searching K from 1 to 3.09x10^13

[CODE]8444737373415*2^142+1 is 3-PRP! (0.0002s+0.0002s)
8444737373415*2^142-1 is 3-PRP! (0.0002s+0.0023s)
8444737373415*2^(142+1)+1 is 3-PRP! (0.0002s+0.0023s)
8444737373415*2^(142+1)-1 is 3-PRP! (0.0018s+0.0023s)
2^142+8444737373415 is 3-PRP! (0.0001s+0.0024s)
2^142-8444737373415 is 3-PRP! (0.0001s+0.0023s)
2^(142+1)+8444737373415 is 3-PRP! (0.0001s+0.0023s)
2^(142+1)-8444737373415 is 3-PRP! (0.0001s+0.0024s)

9532236817845*2^142+1 is 3-PRP! (0.0002s+0.0029s)
9532236817845*2^142-1 is 3-PRP! (0.0002s+0.0024s)
9532236817845*2^(142+1)+1 is 3-PRP! (0.0002s+0.0024s)
9532236817845*2^(142+1)-1 is 3-PRP! (0.0002s+0.0025s)
2^142+9532236817845 is 3-PRP! (0.0001s+0.0023s)
2^142-9532236817845 is 3-PRP! (0.0001s+0.0023s)
2^(142+1)+9532236817845 is 3-PRP! (0.0001s+0.0023s)
2^(142+1)-9532236817845 is 3-PRP! (0.0001s+0.0026s)

22732824274545*2^142+1 is 3-PRP! (0.0002s+0.0003s)
22732824274545*2^142-1 is 3-PRP! (0.0002s+0.0024s)
22732824274545*2^(142+1)+1 is 3-PRP! (0.0002s+0.0024s)
22732824274545*2^(142+1)-1 is 3-PRP! (0.0002s+0.0024s)
2^142+22732824274545 is 3-PRP! (0.0001s+0.0023s)
2^142-22732824274545 is 3-PRP! (0.0001s+0.0023s)
2^(142+1)+22732824274545 is 3-PRP! (0.0001s+0.0024s)
2^(142+1)-22732824274545 is 3-PRP! (0.0001s+0.0024s)[/CODE]

:banana: :bounce: :banana:

Close to 2 million numbers survived the sieve. Newpgen didn't make sence after this, since it removed candidates much slower than i was able to prp them.

I'll try 157 (another 7 mod 15) next.

 Dougy 2005-04-19 23:07

Yay!

:w00t: Fantastic find! They're all primes too. Three new largest octoproths.

 Dougy 2005-04-20 01:31

Found the most wanted

1 Attachment(s)
Yay!

1689898522725 72
1704984216915 72
1729280652225 72
1993468873725 72

The new most wanted is now n=74 (425575968195/18889465931478580854784 searched)

Oh and I (finally) completed n=42. :sleep:

 Dougy 2005-04-20 01:33

Compression

1 Attachment(s)
Because there were too many octo's with small bases I've zipped up the complete list of octo's for bases n<=42.

 TTn 2005-04-20 01:46

Octo RMA 1.74 delay

I've been sick lately, and have not made much progress with octo code, but I know now, exactly how it will be integrated.

Great work 15k'ers!
TTn

 smh 2005-04-20 07:05

[QUOTE=Dougy]:w00t: Fantastic find! They're all primes too. Three new largest octoproths.[/QUOTE]

I knew i forgot something. I didn't test them for primality. Thanks for doing so. :bow:

 Dougy 2005-04-20 14:37

New most wanted n=87

1 Attachment(s)
I've been trying to find the smallest octos for each base. Lots of success... however n=87 is a stubborn base. Sieved upto 4*10^12, and no success.

Bedtime now. :yawn:

 smh 2005-04-20 14:48

[QUOTE=Dougy]I've been trying to find the smallest octos for each base. Lots of success... however n=87 is a stubborn base. Sieved upto 4*10^12, and no success.

Bedtime now. :yawn:[/QUOTE]

Okay, i have a few hours sieving time available, i'll search a bit further on this K.

FYI, i searched n=142 to 3.09x10^13

 R.D. Silverman 2005-04-20 15:15

[QUOTE=smh]Okay, i have a few hours sieving time available, i'll search a bit further on this K.

FYI, i searched n=142 to 3.09x10^13[/QUOTE]

With so many other established computational projects already available,
why do this one?

I accuse noone. However, I suspect that the answer is:

"Because this project is new, it is relatively easy to get results".

Let me quote John Kennedy:

"We choose to go to the moon and do the other thing... Not because they
are easy, but because they are hard."

There is little reward in using other people's software to do easy computations. Rewards come from succeeding at something that is hard.
The satisfaction one derives from solving a problem is commensurate with the
level of effort. :unsure:

 xilman 2005-04-20 15:45

[QUOTE=R.D. Silverman]
There is little reward in using other people's software to do easy computations. Rewards come from succeeding at something that is hard.
The satisfaction one derives from solving a problem is commensurate with the
level of effort. :unsure:[/QUOTE]

Agreed, but an important question is "hard for whom?" There is little reward in failing to make progress because one doesn't have the resources available to complete the task.

Sometimes relatively easy tasks are best attempted by people with relatively lowly resources. They free up the people with massive resources from having to clear them up for completeness sake. That is why I am factoring 6,768L.c130 personally rather than using the grossly disproportionate resources of NFSNET.

I leave open completely the question of whether everyone has the same value function.

Paul

 axn 2005-04-20 15:51

n = 44 complete

1 Attachment(s)
I am doing n=45 now.

 ET_ 2005-04-20 16:02

[QUOTE=xilman]Agreed, but an important question is "hard for whom?" There is little reward in failing to make progress because one doesn't have the resources available to complete the task.

Sometimes relatively easy tasks are best attempted by people with relatively lowly resources. They free up the people with massive resources from having to clear them up for completeness sake. That is why I am factoring 6,768L.c130 personally rather than using the grossly disproportionate resources of NFSNET.

I leave open completely the question of whether everyone has the same value function.

Paul[/QUOTE]

And please don't forget that those results come from axn1 software. I'm sure he studied hard to get the most from it, and this project is a reward to his effort. The results may (maybe) be easily achieved from other searches or software, but there is little advancement in personal knowledge from using others' programs; instead he, I guess, learnt a lot to code it and gave other people the hint to search and deepen the subject by themselves; perhaps he also gave others the will to try and learn by themselves subjects otherwise not chosen.

Luigi

 smh 2005-04-20 16:48

With so many other established computational projects already available,
why do this one?[/QUOTE]

This one is as good as any other.

But i choose this one because i can't use that pc for anything else (except maybe ecm) and it's only available to me for a few days. PRP-ing takes only 15 minutes on my P4. The pc will be gone tomorrow morning and i didn't want to let it run idle.

For the last year or two, i spent most of my cpu time factoring for a few projects (including Paul's). Unfortunately, Cunningham numbers are a bit to hard for my limited resources. I might be able to do a < c140 with GNFS, but my P4 has only 256MB RAM. I have a laptop with 2GB, but that one is used for work, and part of that memory is often needed. Besides, i'm not sure GGNFS is upto the job yet. Sieving on multiple pc's requires to much book keeping for the time i've currentely got.

I'm open for any number you want to have factored, as long as it can be done in a reasonable amount of time.

 smh 2005-04-20 16:53

N=157

Below the results for N=157 and K<2*10^13 :banana:

All are prp, not tested for primality

[code]541364899635*2^157+1
541364899635*2^157-1
541364899635*2^(157+1)+1
541364899635*2^(157+1)-1
2^157+541364899635
2^157-541364899635
2^(157+1)+541364899635
2^(157+1)-541364899635

5375998941495*2^157+1
5375998941495*2^157-1
5375998941495*2^(157+1)+1
5375998941495*2^(157+1)-1
2^157+5375998941495
2^157-5375998941495
2^(157+1)+5375998941495
2^(157+1)-5375998941495

7137839620995*2^157+1
7137839620995*2^157-1
7137839620995*2^(157+1)+1
7137839620995*2^(157+1)-1
2^157+7137839620995
2^157-7137839620995
2^(157+1)+7137839620995
2^(157+1)-7137839620995

16986089468655*2^157+1
16986089468655*2^157-1
16986089468655*2^(157+1)+1
16986089468655*2^(157+1)-1
2^157+16986089468655
2^157-16986089468655
2^(157+1)+16986089468655
2^(157+1)-16986089468655
[/code]

 TTn 2005-04-20 17:17

Silverman

:nuke:
With so many other established computational projects already available,
why do this one?
I accuse noone. However, I suspect that the answer is:
"Because this project is new, it is relatively easy to get results".
Let me quote John Kennedy:
"We choose to go to the moon and do the other thing... Not because they
are easy, but because they are hard."
There is little reward in using other people's software to do easy computations. Rewards come from succeeding at something that is hard.
The satisfaction one derives from solving a problem is commensurate with the
level of effort. [/QUOTE]

I would appreciate if you respectfully ask questions elsewhere. (buzz off)
This project has been around for awhile, and now has a new spin on the fundamental property that started it.

 robert44444uk 2005-04-20 22:32

Angels

We would still be computing the number of angels on the head of a pin unless we had adapted and explored.

The facts are:

This is original thinking, adaptation and exploration in virgin territory
It is simple, but not so simple, there are pitfalls for the unwary
There is interesting mathematics if anyone wants to look at it
Axn1's program is a masterpiece
This is true 1+1=3, as I like to define human co-operation
This is the shitzit right now

Mr Silverman, have pity on us poor humans, nattering together and taking up your valuable bandwidth. Consider yourself flamed, or at least singed, as I am a pacific sort.

Regards

Robert Smith (aged 53 1/4)

 Dougy 2005-04-21 03:15

What's in a name?

Silverman? Hmmm... sounds familiar. Are you related to Joseph H. Silverman who published (among others) the paper "Wieferich's Criterion and the abc-Conjecture" in the Journal of Number Theory?

 Dougy 2005-04-21 05:14

Predicting the next octoproth.

I've been looking at the "weights" of certain bases again. Working as I defined it previously, W(157) = 62. Is the heaviest W(n) for n <= 200.

The next three heaviest are :showoff:
W(175) = 60
W(187) = 56
W(112) = 54

So the bases n = 112, 175, 187 should be good for finding octos.

 Dougy 2005-04-21 13:04

Update

Newies:

4358737887315 87 (a monster!) :exclaim:
2232065722095 88
2148136610235 88

for n=89-96 there are no known octoproths.

Searched n=89 to k=780321515295.

 TTn 2005-04-22 04:26

bitwin

[QUOTE]Okay, i have a few hours sieving time available[/QUOTE]

Is'nt it faster to verify bitwin primality first?
With RMA 1.75 in 2 minutes I was able to find no octoproth's for n=5000, with k<200000000.

TTn

 smh 2005-04-22 06:25

[QUOTE=TTn]Is'nt it faster to verify bitwin primality first?[/QUOTE]
No, the remaining 4 possibilities often have small factors.

[QUOTE=TTn]With RMA 1.75 in 2 minutes I was able to find no octoproth's for n=5000, with k<200000000.
[/QUOTE]
With octo_fast it took less then 1 second to 'sieve' this range, with only 4 possible candidates left.

[CODE]1297905 5000
111183135 5000
116381265 5000
176976555 5000[/CODE]

All times are UTC. The time now is 05:45.