Octoproths

[smh]

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]

Originally Posted by smh

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

That's correct. However, the at the price of about 3 modulo calculations per prime you can test all 8 forms.

Originally Posted by 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.

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.

Originally Posted by 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.

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]

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]

Originally Posted by 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.

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

Originally Posted by 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!).

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.

Originally Posted by axn1

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

Isn't that what makes them more special?

[axn]

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]

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.

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). Furthermore often it seems that terms with small factors (7, 11, 13) are not sieved. 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]

Originally Posted by 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.

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). Furthermore often it seems that terms with small factors (7, 11, 13) are not sieved. 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

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

[Dougy]

610118148045 41
802757470515 41
832494696285 41

[axn]

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

[Templus]

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]

Originally Posted by Templus

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

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