Register FAQ Search Today's Posts Mark Forums Read

 2006-01-16, 16:13 #1 Greenbank     Jul 2005 38610 Posts 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...
2006-01-16, 16:46   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

29·47 Posts

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

 2006-01-17, 09:24 #3 Kosmaj     Nov 2003 E2616 Posts One more near miss! 52035604613787795 58 is DodecaProth! ... Left_legs=0, Rigth_legs=3.
2006-01-19, 16:18   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101010100112 Posts

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.

2006-01-24, 18:44   #5
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

55316 Posts

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

Attached Files

 2006-01-24, 21:51 #6 Kosmaj     Nov 2003 2×1,811 Posts 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.
 2006-01-25, 01:14 #7 grobie     Sep 2005 Raleigh, North Carolina 1010100012 Posts I was going to try this but wont untill a reserve table is made.
 2006-01-25, 01:59 #8 Kosmaj     Nov 2003 2×1,811 Posts 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
2006-01-25, 09:27   #9
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

55316 Posts

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.

 2006-01-25, 10:08 #10 Kosmaj     Nov 2003 2·1,811 Posts 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.
2006-01-25, 10:18   #11
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

136310 Posts

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!