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

 Greenbank 2006-01-16 16:13

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

 R. Gerbicz 2006-01-16 16:46

[QUOTE=Greenbank]
Definition, (k,n) is a hexadecaproth if (k,n), (k,n+1) and (k,n+2) are octoproths!
[/QUOTE]
Small exercise:
Prove that if (k,n) and (k,n+2) is an octoproth then (k,n+1) is also an octoproth!

 Kosmaj 2006-01-17 09:24

One more near miss! :shock:

52035604613787795 58 is DodecaProth! ... Left_legs=0, [B]Rigth_legs=3.[/B]

 R. Gerbicz 2006-01-19 16:18

[QUOTE=Greenbank]
No program exists (yet) to search for them, but I'm sure it will soon...[/QUOTE]

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)[/CODE]
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)[/CODE]
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 2006-01-24 18:44

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

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

 Kosmaj 2006-01-24 21:51

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.

 grobie 2006-01-25 01:14

I was going to try this but wont untill a reserve table is made.

 Kosmaj 2006-01-25 01:59

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

 R. Gerbicz 2006-01-25 09:27

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

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.

 Kosmaj 2006-01-25 10:08

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

 R. Gerbicz 2006-01-25 10:18

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

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 2006-01-25 12:43

1 Attachment(s)
If you complete one workunit then it will be saved to results_hexadeca.txt file, like this:
The workunit=666 has been completed

(I've completed this).
It isn't important to see if there is an information : The sieving is complete, because if this isn't in that file then it means that the program is killed and you can just continue the work from workunit=667. But there is no restart option in the program. See the attachment for the c code or donwload the exe for windows from:

To give an estimation for the time to find a dodecaproth, I've changed the code to see how many prp tests are done in each step:
this is only true for one workunit! ( spec: this was workunit=666 ):
there were 16203093 prp tests
In each step there were:
numprp[1]=12498398
numprp[2]=2851761
numprp[3]=658077
numprp[4]=149567
numprp[5]=35086
numprp[6]=8082
numprp[7]=1865
numprp[8]=222
numprp[9]=29
numprp[10]=5
numprp[11]=1
numprp[12]=0
numprp[13]=0
numprp[14]=0
numprp[15]=0
numprp[16]=0

If it would be numprp[13]>0 then we found a dodecaproth, because it means that the first 12 numbers were 3-prp and the program is testing the 13th number. Seeing the data I think that we can find a dodecaproth after testing about only 100-200 workunits.

 Greenbank 2006-01-25 13:43

Good work Robert.

 Greenbank 2006-01-25 13:51

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

I've put you down for 3,000,000 to 3,000,100 as I wasn't sure exactly how much you were going to do. Please feel free to post in the reservation thread exactly what you want to do!

P.S. roughly 1000 sec per WU on a 2.5GHz G5.

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