mersenneforum.org  

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

 
 
Thread Tools
Old 2006-01-16, 16:13   #1
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2·193 Posts
Default Hexadecaproths

So, the natural progression is to extend this and search for hexadecaproths:-

Definition, (k,n) is a hexadecaproth if (k,n), (k,n+1) and (k,n+2) are octoproths!

Looking at all of the Dodecaproths that have been found so far, the closest we get is this:-

69283546229205 47 is Dodecaproth! ... Left_legs=0, Rigth_legs=3.

No program exists (yet) to search for them, but I'm sure it will soon...
Greenbank is offline  
Old 2006-01-16, 16:46   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

17×83 Posts
Default

Quote:
Originally Posted by Greenbank
Definition, (k,n) is a hexadecaproth if (k,n), (k,n+1) and (k,n+2) are octoproths!
Small exercise:
Prove that if (k,n) and (k,n+2) is an octoproth then (k,n+1) is also an octoproth!

Last fiddled with by R. Gerbicz on 2006-01-16 at 16:46
R. Gerbicz is offline  
Old 2006-01-17, 09:24   #3
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

2×1,811 Posts
Default

One more near miss!

52035604613787795 58 is DodecaProth! ... Left_legs=0, Rigth_legs=3.
Kosmaj is offline  
Old 2006-01-19, 16:18   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

17·83 Posts
Default

Quote:
Originally Posted by Greenbank
No program exists (yet) to search for them, but I'm sure it will soon...
Yes. There will be a program, probably 2 or 3 weeks, I've other tasks now. But I think that it would be a little different than octo or dodeca program, because it's computation time is ( much ) larger. Here it is my suggestion:
We could start a distributed search for n=76, because for this number the expected number of hexadecaproths is about 16.
Weight of n ( for hexadecaproth ) is ( PARI ):
Code:
w(n)=T=32768.0;forprime(p=3,10^4,l=listcreate(16);g=Mod(2,p)^n;h=1/g;\
a=[g,-g,h,-h,2*g,-2*g,h/2,-h/2,4*g,-4*g,h/4,-h/4,8*g,-8*g,h/8,-h/8];\
a=lift(a);for(i=1,16,listput(l,a[i],i));l=listsort(l,1);\
T*=(1-length(l)/p)/(1-1/p)^16);return(T)
Then we can esimate the number of hexadecaproths for a given n by:
Code:
f(n)=round(w(n)*2^n/(n*log(2))^16*1/256)
The first value that f(n)>0 is n=71:
f(71)=1
f(72)=0
f(73)=0
f(74)=1
f(75)=2
f(76)=16
f(77)=1
f(78)=1
f(79)=15
Probably we could search for n=71, but it seems much better n=76, and we can also find some dodecaproth as we search for hexadecaproth, but not all of them, because the program will optimized for hexadecaproth search.

The expected running time to find one! hexadecaproth for n=76 is about 2 years for my PC ( 1.7 GHz Celeron ) ( if my calculation is correct, note that this is only true to find one hexadecaproth! for n=76, not for all of them, to find all of them the expected time is 16 times larger). So we can find hexadecaproth!
I imagine this that there will be "workunits", so you can complete one workunit in about half an hour on an average computer. In one workunit the computer examine all possible cases in one remainder class modulo T. So the search is not an interval search like in octo-dodeca program.
R. Gerbicz is offline  
Old 2006-01-24, 18:44   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

17·83 Posts
Default

Here it is a program to find hexadecaproths!

There are 3869775 workunits in this search, from workunit=0 to workunit=3869774, to use it just type for example:
hexadeca_1_0 100 104
if you want to complete start_workunit=100 to end_workunit=104 ( this is 5 workunits ).
Each workunit has got the same probability that it is containing a hexadecaproth, and to finish this workunit has got the same running time.

Note that we are searching only for n=76, for this n there are about 16 hexadecaproth. If the program find some dodecaproth then these will be saved to results_ex.txt file, but won't display, I think that we can find also about 6728 dodecaproths in this search but not all of them because this is optimized for hexadecaproth search.

We are using primes only up to 1000. And in every cases 15 primes in the sieve reduction, but not the first 15 primes: we are using: 2,3,5,7,11,13,17,19,23,37,41,43,47,67,71, because using the first 15 primes is suboptimal.

Here it is my first completed workunit for this search:

C:\>hexadeca_1_0 456789 456789
You can also find the results in results_hexadeca.txt file ( These are 3-probable primes )
If the program find some dodecaproths then these will be saved to results_ex.txt file, but we won't display these
n=76, start_workunit=456789, end_workunit=456789, version=1.0
Starting the sieve...
Using 15 primes to reduce the size of the sieve array
The sieving is complete.
Number of Prp tests=16198758
Time=2769 sec.

It means that the average expected running time to find only one! hexadecaproth for n=76 is about 2769*3869775/16 sec.=21 years for Penitum 4 Celeron 1.7 GHz. In my previous prediction I've forgotten to multiply by about 10, the program isn't slow!

It isn't impossible to test this program, because it is possible to print the examined k values then I've checked that 16 forms hasn't got small prime factors for various k values, however as a subproject it would be good to find at least one dodecaproth by this program.

Note Kosmaj has found one dodecaproth for n=76, but that won't find this program because the remaining 4 forms has got small prime factors!

See my attachment for c code

Or you can download exe for windows from:http://www.robertgerbicz.tar.hu/hexadeca_1_0.exe
Attached Files
File Type: txt hexadeca_1_0.txt (17.8 KB, 158 views)
R. Gerbicz is offline  
Old 2006-01-24, 21:51   #6
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

362210 Posts
Default

Thanks for the new program!

I'll try some workunits beginning at 3M (3,000,000).
... Just finished the first one in 1703 sec on my Athlon-MP 2000.
Kosmaj is offline  
Old 2006-01-25, 01:14   #7
grobie
 
grobie's Avatar
 
Sep 2005
Raleigh, North Carolina

337 Posts
Default

I was going to try this but wont untill a reserve table is made.
grobie is offline  
Old 2006-01-25, 01:59   #8
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

1110001001102 Posts
Default R.Gerbicz

First impressions:
(1) When testing several WUs it will be good if they are processeed one after the other and after completing each WU a record is written to the results file. So, if I stop the process while running I have some WUs completed and in the worst case I lose work only on one (most recent) WU. Now, if one stops the process while running he has to redo the whole range.

(2) No big problem but some text is written to the "results_dodeca.txt" file, see lines 260-262. You can remove that one as far as I'm concerned.

Nothing found yet but so far I processed only 3 WUs.

Last fiddled with by Kosmaj on 2006-01-25 at 02:01
Kosmaj is offline  
Old 2006-01-25, 09:27   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26038 Posts
Default

Quote:
Originally Posted by Kosmaj
First impressions:
(1) When testing several WUs it will be good if they are processeed one after the other and after completing each WU a record is written to the results file. So, if I stop the process while running I have some WUs completed and in the worst case I lose work only on one (most recent) WU. Now, if one stops the process while running he has to redo the whole range.

(2) No big problem but some text is written to the "results_dodeca.txt" file, see lines 260-262. You can remove that one as far as I'm concerned.

Nothing found yet but so far I processed only 3 WUs.
For (2): OK I see, I'll remove that because in every case we are using 15 primes, it isn't very important to print this to a file. Sorry for this small error, when I've written this I simply rewritten dodeca program.

For (1): OK I can do it. When I've written this I haven't calculated the expected running time for 1 workunit. But it is easy to do this: see the program: there is a for cycle to do the workunits from start_workunit to end_workunit.
R. Gerbicz is offline  
Old 2006-01-25, 10:08   #10
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

E2616 Posts
Default

OK, thanks! And sorry, I didn't have time to study the code, I only checked that by-product DodecaProths are being written. BTW, do you have any rough idea after how many WUs can I expect the first DodecaProth? So far I did 15 WUs but found none.
Kosmaj is offline  
Old 2006-01-25, 10:18   #11
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

58316 Posts
Default

Quote:
Originally Posted by Kosmaj
OK, thanks! And sorry, I didn't have time to study the code, I only checked that by-product DodecaProths are being written. BTW, do you have any rough idea after how many WUs can I expect the first DodecaProth? So far I did 15 WUs but found none.
If program find some dodecaproths then these will be saved only to results_ex.txt file.

We can find about 6728 dodecaproths while searching for hexadecaproth, but I don't know if this is a correct prediction, it isn't trivial to give an estimation for this. There are 3869775 WU it means that if my prediction is correct then we have to complete 3869775/6728=575 WU to find at least one dodecaproth!

Note that there are about f(76)=773157 dodecaproths for this n ( this is a correct estimation ), but this program won't find all of them!
R. Gerbicz is offline  
 

Thread Tools


All times are UTC. The time now is 10:08.

Mon Oct 26 10:08:53 UTC 2020 up 46 days, 7:19, 0 users, load averages: 1.51, 1.40, 1.53

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.