mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > Octoproth Search

 
 
Thread Tools
Old 2005-04-17, 12:32   #56
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

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.
smh is offline  
Old 2005-04-17, 13:12   #57
axn
 
axn's Avatar
 
Jun 2003

22·5·239 Posts
Default

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

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

Quote:
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!
axn is online now  
Old 2005-04-17, 16:21   #58
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

111011100002 Posts
Default 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
robert44444uk is offline  
Old 2005-04-17, 18:50   #59
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

4A516 Posts
Default

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

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


Quote:
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?
smh is offline  
Old 2005-04-18, 05:08   #60
axn
 
axn's Avatar
 
Jun 2003

22·5·239 Posts
Thumbs up New and improved!

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.)
Attached Files
File Type: zip octo1.zip (37.4 KB, 106 views)
axn is online now  
Old 2005-04-18, 10:30   #61
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

23·19 Posts
Arrow 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.

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
Dougy is offline  
Old 2005-04-18, 11:27   #62
axn
 
axn's Avatar
 
Jun 2003

10010101011002 Posts
Default

Quote:
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.
axn is online now  
Old 2005-04-18, 12:09   #63
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

100110002 Posts
Cool More newies...

610118148045 41
802757470515 41
832494696285 41
Attached Files
File Type: txt octoproth.txt (8.2 KB, 181 views)
Dougy is offline  
Old 2005-04-18, 12:25   #64
axn
 
axn's Avatar
 
Jun 2003

22·5·239 Posts
Arrow Bug Fix

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
Attached Files
File Type: zip octo.zip (37.4 KB, 119 views)

Last fiddled with by axn on 2005-04-18 at 12:31
axn is online now  
Old 2005-04-18, 14:00   #65
Templus
 
Templus's Avatar
 
Jun 2004

1528 Posts
Default

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.

Last fiddled with by Templus on 2005-04-18 at 14:04
Templus is offline  
Old 2005-04-18, 15:34   #66
axn
 
axn's Avatar
 
Jun 2003

112548 Posts
Default

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

Last fiddled with by axn on 2005-04-18 at 15:41
axn is online now  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Small Primes for Octoproths <= 155 ValerieVonck Octoproth Search 100 2007-02-16 23:43
Found Octoproths - Range Archive ValerieVonck Octoproth Search 0 2007-02-14 07:24
Number of octoproths per n Greenbank Octoproth Search 15 2006-01-20 16:29
Need help with NewPGen(octoproths) jasong Software 1 2005-05-10 20:08

All times are UTC. The time now is 15:40.

Fri Nov 27 15:40:34 UTC 2020 up 78 days, 12:51, 4 users, load averages: 0.99, 1.20, 1.20

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.