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

- - **Octoproths**
(*https://www.mersenneforum.org/showthread.php?t=3956*)

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

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

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

[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? |

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.) |

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 |

[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. |

More newies...1 Attachment(s)
610118148045 41
802757470515 41 832494696285 41 |

Bug Fix1 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: |

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

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

All times are UTC. The time now is 20:46. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.