Dodecaproths exist!
Check me if I am wrong, but I ran the first 65000 octoproths through my spider routine and turned up the following dodecaproths (3chain):
44 9604223498415 1 4 5 47 45960089776965 1 4 5 49 374180855930805 1 4 5 44 10872870991605 0 4 4 44 7946515823715 0 4 4 47 69283546229205 0 4 4 49 19000157002995 0 4 4 49 502414540060965 0 4 4 49 555428994253665 0 4 4 45 9604223498415 4 1 5 45 7946515823715 4 0 4 45 10872870991605 4 0 4 48 69283546229205 4 0 4 48 45960089776965 4 0 4 The firs column is n, the second is k, the third is the four types, with n1, the fourth column is the four types with n+2, and the final column the number of legs on the spider. So we have some 5's but no 6's. They maybe hope for a 4 chain yet!!! Regards Robert Smith 
Statistics
Some stats relating to ther frequency of "legs" in my test:
lower legs upper legs total legs 0 53444 81.549% 49382 75.351% 40477 61.763% 1 11031 16.832% 14524 22.162% 19846 30.283% 2 1012 1.544% 1513 2.309% 4459 6.804% 3 44 0.067% 108 0.165% 673 1.027% 4 5 0.008% 9 0.014% 71 0.108% 5 0 0.000% 0 0.000% 10 0.015% 65536 65536 65536 Regards Robert Smith 
Re: Dodecaproths
[B]Robert[/B], congrats on locating first dodecaproths. :cool: But note that there are 9 not 14 distinct ones because you counted some twice (once to the right, once to the left) like for example:
44 9604223498415 1 4 5 45 9604223498415 4 1 5 I verified that members of all 9 are primes, here is the output of my Pari script: [CODE] 7946515823715 44 is OctoProth! ... and DodecaProth!! 9604223498415 44 is OctoProth! ... and DodecaProth!! 10872870991605 44 is OctoProth! ... and DodecaProth!! 45960089776965 47 is OctoProth! ... and DodecaProth!! 69283546229205 47 is OctoProth! ... and DodecaProth!! 19000157002995 49 is OctoProth! ... and DodecaProth!! 374180855930805 49 is OctoProth! ... and DodecaProth!! 502414540060965 49 is OctoProth! ... and DodecaProth!! 555428994253665 49 is OctoProth! ... and DodecaProth!! [/CODE] where I define (k,n) to be DodecaProth if both (k,n) and (k,n+1) are OctoProths. BTW, I checked the table provided by Greenbank but found no DodecaProths for n=50. 
n=51
Found 3 DodecaProths for n=51 :cool:
[CODE] 145174433549145 51 is OctoProth! ... and DodecaProth!! 246834311745945 51 is OctoProth! ... and DodecaProth!! 868049887559295 51 is OctoProth! ... and DodecaProth!! [/CODE] No more legs neither to the left (n=50) nor to the right (n=54). 
[QUOTE=Kosmaj]
I define (k,n) to be DodecaProth if both (k,n) and (k,n+1) are OctoProths. [/QUOTE] What a nice definition! Probably it is also possible to write a GMP program for this search, like for octoproth. Sometime before I thought to define ....proth ( what is the correct name for sixteen? ), where (k,n) and (k,n+2) are Octoproths ( this means that this is also a DodecaProth because it is easy to prove that if (k,n) and (k,n+2) are Octoproths then (k,n+1) is also an octoproth ). It means 16 primes, but today to find such a pattern is impossible, even by a fast sieve and fast prp checking. Ps. Searching for Dodecaproth would be faster for a given n value and a given Range than searching for Octoproths. You don't need to find all octoproths in that range! 
[QUOTE]Sometime before I thought to define ....proth ( what is the correct name for sixteen? )[/QUOTE]I think it should be called [I]HexadecaProth[/I], and the next one if we ever encounter it is [I]IcosaProth[/I] :smile:
[QUOTE]It means 16 primes, but today to find such a pattern is impossible, even by a fast sieve and fast prp checking.[/QUOTE]I don't think it's impossible! We have to find enough (i.e., many!) DodecaProths and one of them will surely be HexadecaProth. Check the following chain of 16 primes (the socalled bitwin with 7 links): 517144126484002331*13#*2^n+/1 n=0,1,2,3,4,5,6,7; and "#" denotes primorial. composed of 8 twins, and two Cunningham chains of first and second kind. Have you ever thought that such a chain exists? :shock: Only two such chains are currently known. The twin for n=0 has 23 digits. This is I think the place to look for HexadecaProths, around our exponent n=65 or 70. If you can change your program to search for DodecaProths (ignoring of course potenital OctoProths whose "right legs" have small factors) I'll be willing to try! :cool: 
dodeca program version 1.0
1 Attachment(s)
I've finished a new program. It is searching for dodecaproths, and it is faster than octoproths!!!
It is sieving all 12 numbers. The speed up is very very different for different ranges and n values. Here I sieve only up to 32000 ( so I can use unsigned short variables ) and magic_constant=32000 The size of used memory is about 130 KB. The number of Prp tests is also much much smaller. You can find the results also in results_dodeca.txt file. Exe for windows: [URL="http://www.robertgerbicz.tar.hu/dodeca_1_0.exe"]http://www.robertgerbicz.tar.hu/dodeca_1_0.exe[/URL] Or see the attachment for the code. It isn't very easy to test because we know only a very few of dodecaproths, but for n=44 and n=47 it is correct. It would be good to test this program. Greenbank: I would like to see a new thread: Number of dodecaproths per n Using your tables it isn't hard to create this table. It is easier to find this number than octoproth's number, so maybe we can go further n=55, perhaps n=56, but before this check my program. I've disabled to use n>99, because in this case the expected smallest dodecaproth's k value is very large ( larger than 10^20>2^60=kmax limit ). 
[QUOTE=Kosmaj]This is I think the place to look for HexadecaProths, around our exponent n=65 or 70.
[/QUOTE] Sieving for Hexadecaproth would be faster than my new Dodeca program. Because it is also possible to sieve 16 forms at once!!! I've calculated that the smallest n value for that there exist a Hexadecaproth is probably n=71 But in this case the smallest k value is also very large, say about 2^70, and it is much larger than 2^60=k max limit. So by this program you won't able to find a Hexadecaproth. 
new dodecaproth for n=52 !!!
I've found this by dodeca_1_0.exe The 12 numbers are primes.
2808528662035845 52 I'm still running n=52, if Greenbank finish all octoproths for n=52 then it will be a quick and good check to see if my new program is good or not. Ps. I've calculated that the expected number of dodecaproths for n=52 is 2 
You are so fast! Thanks for the new program.[QUOTE]So by this program you won't able to find a Hexadecaproth.[/QUOTE] No problems, let's first see how many DodecaProths can we find. For some n's most likely we'll have to go all the way to k=1E17 or more. BTW, using your new program I confirmed those for n=49 and n=51 and now I'm trying n=56 (because we can trivially locate those for n=5255 when the guys find all OctoProths). Up to k=1000T (1E15) nothing...

[QUOTE=Kosmaj]You are so fast! Thanks for the new program.[/QUOTE]
:lol: I haven't written that program between 14 Jan 06 03:39 PM and 03:51 PM. ( See the times. ) I have started the writing some hours before, but still today, it wasn't very hard. [QUOTE=Kosmaj]No problems, let's first see how many DodecaProths can we find. For some n's most likely we'll have to go all the way to k=1E17 or more. BTW, using your new program I confirmed those for n=49 and n=51 and now I'm trying n=56 (because we can trivially locate those for n=5255 when the guys find all OctoProths). Up to k=1000T (1E15) nothing...[/QUOTE] When you are checking this I hope you are using kmin=1 and kmax=1+2^n 
[QUOTE]I haven't written that program between 14 Jan 06 03:39 PM and 03:51 PM.[/QUOTE] Yes, I guess you began after writing message #259? As for limits I'm using kmin=15 and kmax between 1E15 and 1E16 (for the time being).

n=57
Found first DodecaProth for n=57:
[B]87653084113035 57[/B] And imagine, for such a small k<100T. Has one extra leg to the left, none to the right. 
No more dodecaproth for n=52
I've searched the full range for n=52 to find all dodecaproth.
Here is the full report: on Pentium4 Celeron 1.7 GHz: C:\>dodeca_1_0 52 1 4503599627370495 You can also find the k n values in results_dodeca.txt file ( These are 3probable primes ) n=52, kmin=1, kmax=4503599627370495, version=1.0 Starting the sieve... Using the first 10 primes to reduce the size of the sieve array 2808528662035845 52 The sieving is complete. Number of Prp tests=613089 Time=8917 sec. Ps. I've verified all 12 numbers are primes. 
I don't get all the other stuff with legs and everything. just ran the program (dodeca_1_0.exe) here's what I got:
n=66, kmin=1, kmax=1000000000000000, version=1.0 Starting the sieve... Using the first 10 primes to reduce the size of the sieve array 229350894172785 66 The sieving is complete. Number of Prp tests=138495 Time=2992 sec. 
Probably we can start a new thread for reservation for dodecaproth search, to avoid the duplication.
[QUOTE=Kosmaj]Yes, I guess you began after writing message #259?[/QUOTE] Yes. 
Congrats to [B]tcadigan[/B] for a new DodecaProth! I found 3 for n=62:
[B]99828673281855 62 286846836764775 62 1692654062704395 62[/B] BTW, I checked n=56 to 1200T (1.2E15) and n=5762 to 2000T (2E15) but besides the one for n=57 I found none. I'm proceeding with n=6370 to 2000T (will skip n=66). 
R. Gerbicz
I noticed a large slowdown of dodeca.exe ver. 1.0 on a large range. Have a look. Case 1:
[CODE] n=70, kmin=15, kmax=3000000000000000, version=1.0 Using the first 10 primes to reduce the size of the sieve array Time=1968 sec.[/CODE] Case 2: [CODE]n=70, kmin=3000000000000000, kmax=10000000000000000, version=1.0 Using the first 11 primes to reduce the size of the sieve array Status: 0.3 percentage of the project is complete. Time thusfar: 69 sec.[/CODE] I stopped the second instance but 0.3% in 69 sec means 23000 sec for the range 7000T wide, while less than 2000sec were needed for a range 3000T wide. The only difference is the number of primes used (10 > 11) so I guess it's related to [I]magic_constant[/I] now set to 32000. Can you have a look and tell us how to avoid this kind of problems. Can you possibly set [I]magic_constant[/I] dynamically based on input parameters (kmin and kmax) or enable "x" on the cmdline as you mentioned before for octo.exe. Thanks. BTW, I checked all n=6770 to 3000T but found no new DodecaProths. 
[QUOTE=Kosmaj]I noticed a large slowdown of dodeca.exe ver. 1.0 on a large range. Have a look. Case 1:
[CODE] n=70, kmin=15, kmax=3000000000000000, version=1.0 Using the first 10 primes to reduce the size of the sieve array Time=1968 sec.[/CODE] Case 2: [CODE]n=70, kmin=3000000000000000, kmax=10000000000000000, version=1.0 Using the first 11 primes to reduce the size of the sieve array Status: 0.3 percentage of the project is complete. Time thusfar: 69 sec.[/CODE][/QUOTE] OK I'll see it. Yesterday I have not calculated this, but I thought that there will be such a problem using many primes in the sieving area ( first 11 primes means we are using primes up to 31 ). Probably this occured because we are sieving more numbers ( 12 numbers ). 
1 Attachment(s)
All right, thanks.
BTW, I just ran into the first DodecaProth for n=70: [B]14494401979227555 70[/B] [2E16] Note that [I]k[/I] has 17 digits. k*2^n+/1 members have 38, while 2^n+/k have 22 digits. One leg on the left and one on the right. I'm also enclosing a Pari script I use to verify DodecaProths and count legs. To use it start Pari from the folder where you saved the file, then type: [CODE] gp> read("isddp.txt") gp> isddp(14494401979227555,70) 14494401979227555 70 is DodecaProth! ... Left_legs=1, Rigth_legs=1. [/CODE] 
All right, thanks.
BTW, I just ran into the first DodecaProth for n=70: [B]14494401979227555 70[/B] [2E16] Note that [I]k[/I] has 17 digits. k*2^n+/1 members have 38, while 2^n+/k have 22 digits. One leg on the left and one on the right. I'm also enclosing a Pari script I use to verify DodecaProths and count legs. To use it start Pari from the folder where you saved the file, then type: [CODE] gp> read("isddp.txt") gp> isddp(14494401979227555,70) 14494401979227555 70 is DodecaProth! ... Left_legs=1, Rigth_legs=1. [/CODE] 
New dodeca program version 2.0
1 Attachment(s)
This is faster than dodeca 1.0, but the speed up is very very different for different n values and ranges.
To obtain this I've eliminated almost all modular multiplications ( in the part when we see if "g" is good or not ). Now magic_constant=32000 is good for this version. I'll think what would be a good "default" value. But note that we are sieving also up to 32000 and one block length is also 32000. Kosmaj can you test this version, I've checked only for n=44,47. And test your previous case 1 and case 2. You can download exe for windows from: [URL="http://www.robertgerbicz.tar.hu/dodeca_2_0.exe"]http://www.robertgerbicz.tar.hu/dodeca_2_0.exe[/URL] Or see the attachment for the c code. 
Thanks a lot, now is much better :smile:
n=70 to 3E15, was 1970 sec, now 1300 sec (estimate) n=70 3E151E16, was 23000sec (est), now 2900 sec! (est) n=71 to 1E15, was 5500sec, now 5000 sec (est) Also confirmed a number of already found DodecaProths. I'm now trying to find more DodecaProths for n=62 which was most prolific so far. ps. To moderators: Please remove my duplicate post #276. 
There are 6 dodecaproths for n=53
I've searched the full range for n=53
Here is the full report. On my P4 Celeron 1.7 GHz: C:\>dodeca_2_0 53 1 9007199254740991 You can also find the k n values in results_dodeca.txt file ( These are 3probable primes ) n=53, kmin=1, kmax=9007199254740991, version=2.0 Starting the sieve... Using the first 11 primes to reduce the size of the sieve array 243175720207035 53 2045619551693025 53 5622222735873975 53 2468433344406645 53 4167419818747185 53 2104470659030355 53 The sieving is complete. Number of Prp tests=1692282 Time=21101 sec. 
27 DodecaProths Found
Here is the list of all DodecaProths found so far and the status of search. I found two more for n=62.
[CODE] 7946515823715 44 9604223498415 44 10872870991605 44 Robert [Done] 45 None [Done] 46 None [Done] 45960089776965 47 69283546229205 47 Robert [Done] 48 None [Done] 19000157002995 49 374180855930805 49 502414540060965 49 555428994253665 49 Robert [Done] 50 None [Done] 145174433549145 51 246834311745945 51 868049887559295 51 Kosmaj [Done] 2808528662035845 52 R.Gerbicz [Done] 243175720207035 53 2045619551693025 53 2104470659030355 53 2468433344406645 53 4167419818747185 53 5622222735873975 53 R.Gerbicz [Done] 5455 [Not tested] 56 [1.2E15] 87653084113035 57 Kosmaj [2E15] 58 [2E15] 59 [2E15] 60 [2E15] 61 [2E15] 99828673281855 62 286846836764775 62 1692654062704395 62 3574476316006155 62 6553886937433395 62 Kosmaj [9E15] 63 [2E15] 64 [2E15] 65 [2E15] 229350894172785 66 tcadigan [1E15] 67 [3E15] 68 [3E15] 69 [3E15] 14494401979227555 70 Kosmaj [2E16] 71 [1E15] [/CODE] 
First DodecaProth n=56
[B]4356015966090075 56 [/B] [5E15]
I'm now working on n=58 and n=71. BTW, it will be good to creata a separate thread for DodecaProths and move related posts there. Tell Citrix in his thread about it, and tell him that his thread will be soon deleted because at the time he wrote it we already discussed DodecaProths here but he never bother to have a look. 
OK, will do, will also create a separate reservation/results thread and grab the info from here.
OK: Reservations thread: [url]http://www.mersenneforum.org/showthread.php?t=5359[/url] Please post only reservations or results in that thread. Use this thread for discussions. Thanks for the help Kosmaj. 
Estimation of the number of dodecaproths for n
As I estimated the number of octoproths for a given n value, it is also possible to give an estimation for dodecaproths:
Let's define the "weight" for n: [CODE] w(n)=T=2048.0;forprime(p=3,10^4,l=listcreate(12);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];\ a=lift(a);for(i=1,12,listput(l,a[i],i));l=listsort(l,1);T*=(1length(l)/p)/(11/p)^12);return(T)[/CODE] then by this we can estimate the number of dodecaproths for a given n by: [CODE] f(n)=round(w(n)*2^n/(n*log(2))^12*1/64)[/CODE] For example if n=53 then f(n)=4. The true number is 6. 
Can someone else check this one. The list above stated None for n=50.
But the PARI script (isddp.txt) run against all known Octoproth's gave this: 717083008036395 50 is DodecaProth! ... Left_legs=1, Rigth_legs=0. Either there is a problem with dodeca_2_0.c or that PARI script: $ ../dodeca20 50 7170000000000000 7200000000000000 You can also find the k n values in results_dodeca.txt file ( These are 3probable primes ) n=50, kmin=7170000000000000, kmax=7200000000000000, version=2.0 Starting the sieve... Using the first 9 primes to reduce the size of the sieve array The sieving is complete. Number of Prp tests=1567 Time=22 sec. 
[QUOTE=Greenbank]Can someone else check this one. The list above stated None for n=50.
But the PARI script (isddp.txt) run against all known Octoproth's gave this: 717083008036395 50 is DodecaProth! ... Left_legs=1, Rigth_legs=0. Either there is a problem with dodeca_2_0.c or that PARI script: $ ../dodeca20 50 7170000000000000 7200000000000000 You can also find the k n values in results_dodeca.txt file ( These are 3probable primes ) n=50, kmin=7170000000000000, kmax=7200000000000000, version=2.0 Starting the sieve... Using the first 9 primes to reduce the size of the sieve array The sieving is complete. Number of Prp tests=1567 Time=22 sec.[/QUOTE] That is a new dodecaproth! I think somebody made a mistake when he searched this n value ( for this he used your tables!). For my program: you have typed 10 times larger number than original!!! Try again. For me it is correctly found this number! 
Yup, just noticed that:
$ ../dodeca20 50 717000000000000 720000000000000 You can also find the k n values in results_dodeca.txt file ( These are 3probable primes ) n=50, kmin=717000000000000, kmax=720000000000000, version=2.0 Starting the sieve... Using the first 8 primes to reduce the size of the sieve array 717083008036395 50 The sieving is complete. Number of Prp tests=213 Time=6 sec. This proves that double checking is useful (and necessary!). Also got: $ ../dodeca20 58 10000000000000000 100000000000000000 You can also find the k n values in results_dodeca.txt file ( These are 3probable primes ) n=58, kmin=10000000000000000, kmax=100000000000000000, version=2.0 Starting the sieve... Using the first 11 primes to reduce the size of the sieve array 74362823389729875 58 Status: 6.0 percentage of the project is complete. Time thusfar: 990 sec. Yes, that's in the range 10000T (1E16) to 100000T (1E17). [B]Sorry Kosmaj, this was in your reserved range, I was supposed to be testing n=55. Should teach me to check things more closely.[/B] 
49 and 50
By the way, my first effort looked at the first 65000 octoproths, due to limiations of file handling in MS Excel, and therefore 49 was incomplete. It needs to be run with Robert's program.
Regards Robert Smith 
[QUOTE=robert44444uk]By the way, my first effort looked at the first 65000 octoproths, due to limiations of file handling in MS Excel, and therefore 49 was incomplete. It needs to be run with Robert's program.
Regards Robert Smith[/QUOTE] I took my octo_complete.txt file and ran it through (a slightly modified) "isddp.txt" in PARI. That's how I found the missing n=50 one. I've done this for all n in that file (up to and including n=54) and everything else is correct. (Will double double check that though ;) ). 
dodeca 2.5 program
1 Attachment(s)
In this version you can use T=10^12, see the octoproths thread.
Exe for windows: [URL="http://www.robertgerbicz.tar.hu/dodeca_2_5.exe"]http://www.robertgerbicz.tar.hu/dodeca_2_5.exe[/URL] Or see the attachment for the c code. 
Thanks Robert!
Links in Welcome  How to Help thread updated to point to Dodeca 2.5. 
I've checked Greenbank's ocproths table ( up to n=54 ) by UBASIC. All numbers are strong pseudoprimes for base 5, and I've found only the known dodecaproths for n<55. This is good because this is also an independent verification of the results, the running time was about 15 minutes.

n=58
Found 6 DodecaProths for n=58:
[B]17871561203266155 58 42210084958591935 58 45307176385075605 58 46259463855164175 58 50067984112666905 58 52035604613787795 58[/B] Checked to 7E16. I'm stopping here and releasing n=58 so that Greenbank can continue and register his k. :smile: BTW, I don't think there is any need to check again primality of Dodeca/OctoProth numbers already checked by Pari script because Pari's [I]isprime [/I] function returns 1 if the input number is a proven prime. 
Even and odd
This is really aimed at Robert G.
Does your program lookfor dodecas either side one less n and one greater n  for example if I am searching for 59, isnt that going to overlap with 58 and 60? Shoudl we not be tailoring appropriately, though looking only at k between, in this instance, 2^58 and 2^59, when searching for 59's? Regards Robert Smith 
[QUOTE=robert44444uk]This is really aimed at Robert G.
Does your program lookfor dodecas either side one less n and one greater n  for example if I am searching for 59, isnt that going to overlap with 58 and 60? Shoudl we not be tailoring appropriately, though looking only at k between, in this instance, 2^58 and 2^59, when searching for 59's? Regards Robert Smith[/QUOTE] My program will print k n if and only if (k,n) and (k,n+1) is an octoproth. It isn't possible to look for (k,n1) and (k,n) octoproths so we couldn't double the speed of the program because n1,n and n,n+1 doesn't generate the same remainder classes and we are searching in remainder classes. Here it is a small description of the algorithm. We are searching in remainder classes this is "g" in the program, we are searching for k, where k==g mod step, here step is the product of the first x primes. We define g as "good" if all twelve numbers are relative prime to step, i.e. they aren't divisible by the first x primes ( otherwise not all numbers are primes!). If "g" is good then we are making a classic sieve on these numbers! We are sieving up to 32000 ( in octoproth up to 10^5, because there are only eight numbers ), we have to cancel out k from the sieve if q divides one numbers from the twelve numbers ( here q<32000 ), see one case: k*2^n+1==0 mod q and also note that k==g mod step. Rewriting the first equation: k==(1/2)^n mod q, where 1/2 is the multiplicative inverse of 2 modulo q. So we have to solve k==(1/2)^n mod q and k==g mod step. This is a linear congurence system, it is easy to solve, note that gcd(q,step)=1, because q is greater than the x. prime number. The solution is a class modulo q*step ( because gcd(q,step)=1 ). But we are now searching only in k==g mod step remainder class, it means that we have to cancel out every qth number from the table ( we have to do this for all twelve numbers ). If we are done all prime numbers up to 32000, then we are searching for survivors and for these numbers we make a 3prp checking. If all numbers are 3prp, then we have found a dodecaproth candidate. Ps. But it is possible to find hexadecaproth by the program, but it isn't very efficient for this. 
Two questions/suggestions.
[QUOTE=R. Gerbicz]We are searching in remainder classes this is "g" in the program, we are searching for k, where k==g mod step, here step is the product of the first x primes. [/QUOTE] (1)While doing this are you using the fact that [I]k[/I] must be a multiple of several first primes, for example, for DodecaProths [I]k[/I] must be an odd multiple of 3*5*7 for all [I]n[/I], while for some[I] n[/I] (like 58 above) it also must be a multiple of 11. Then you can increase [I]step[/I] by including up to 3 (or 4) more primes. By doing this you can also reduce the values kept in internal variables, for example instead of k you can keep k/105 and thus increase the range of k while using the same int type. (2) In the second step are you sure you are not oversieving? It is possible that sieving above a certain value removes only a small portion of candidates and is therefore more time consuming than prp test because modular division ("%" in C) requires many cpu cycles. Maybe in case of DodecaProths we can stop sieving at 10000 instead of going to 32000 (there are more than 2200 primes between 10k and 32k)? 
[QUOTE=Kosmaj]Two questions/suggestions.
(1)While doing this are you using the fact that [I]k[/I] must be a multiple of several first primes, for example, for DodecaProths [I]k[/I] must be an odd multiple of 3*5*7 for all [I]n[/I], while for some[I] n[/I] (like 58 above) it also must be a multiple of 11. Then you can increase [I]step[/I] by including up to 3 (or 4) more primes. By doing this you can also reduce the values kept in internal variables, for example instead of k you can keep k/105 and thus increase the range of k while using the same int type. [/QUOTE] Yes that's included in dodeca_2_0 and 2_5, but not dodeca_1_0 ( that was the reason that this was too slow! in some cases ). Now I'm using g==105 mod 210 see the code, note that I'm not using your multiple 11 trick ( I've observed this also before ), because this is really a zero speedup ( OK less than 0.1% ). [QUOTE=Kosmaj] (2) In the second step are you sure you are not oversieving? It is possible that sieving above a certain value removes only a small portion of candidates and is therefore more time consuming than prp test because modular division ("%" in C) requires many cpu cycles. Maybe in case of DodecaProths we can stop sieving at 10000 instead of going to 32000 (there are more than 2200 primes between 10k and 32k)?[/QUOTE] No there is no oversieve! ( note there is also no oversieve in octo ). In fact there is a veryvery small oversieve is still exist ( say we examine one or two more numbers for every good g value ). When I've written this dodeca program I've just rewritten the original octo program so the two programs contains the same ideas. OK perhaps we can choose smaller parameters. The reason why I've choosen 32000 that in this case I can use unsigned and signed short variables ( because 32000<2^15=32768 ). See my quick computations: my suggestion: use prime limit=2000, block length=8000, magic_constant=8000. Then we can get much more prp tests, but how many? This is simple: (ln(32000)/ln(2000))^8=12.04 times more prp tests, this will be still not much ( note that we are testing very small n values ). But what can we gain from sieve? It's also simple by Merten's theorem: it would be: lnln(32000)/lnln(2000)=1.15 times faster. So we can get in theory an 15% faster sieve. But there is an additional speedup, because in this case 4*prime limit=block length, so there would be much less initialization in the sieve. The overall Ram is also much smaller, probable all of them will fit in the very fast L1 cache? Tomorrow I'll try these parameters, now I'm running octo program, all night. 
n=60 and n=76
Three found
[B]6584335653605325 60 51593298019338075 60 87084056712267615 60[/B] Checked to 2E17 and stopped. No new reservations today. :sleep: Just ran into the first one n=76 :shock: [B]37990374090023355 76[/B] In progress to 6E16. 
Thanks Kosmaj, I'll update the results/reservation thread with this info.
In my own checking there are no Dodecaproths for n=79 below 50000T (5E17). Bumping up the search in 1E17 increments today while I can watch it. Found some Dodecaproths for n=63. The smallest being 94550773355550435. I'll add these to the thread too. 
dodeca 3.0 program
1 Attachment(s)
I've changed: primelimit=2000, block length=magic_constant=8000.
Note that there will be much more prp tests, but it's cost is still small, in every cases I think this is about 2 times faster than previous was. I've tested this only for n=44,47. You can download it from [URL="http://www.robertgerbicz.tar.hu/dodeca_3_0.exe"]http://www.robertgerbicz.tar.hu/dodeca_3_0.exe[/URL] Or see the attachment for the c code! 
Re: dodeca3
[B]R. Gerbicz[/B]
Thanks for your quick reaction! The new version is indeed up to 2 times faster than before. I'll now check whether it correctly detects already known DodecaProths. Once I wrote a similar program to search for a long arithmetic progression of primes so I have some /limited/ experience. 
Dodecaproth n 'weights'
I'm defining the 'weight' of an n as the number of PRP tests that dodeca_30 needs to perform when checking that n for a range of 0,10T.
The lower the weight the faster it will be to check that n. The higher the weight the slower it will be. n=80 weight=45489 n=81 weight=50735 n=82 weight=36134 n=83 weight=31322 n=84 weight=79800 n=85 weight=11925 n=86 weight=71370 n=87 weight=46678 n=88 weight=10297 n=89 weight=452294 n=90 weight=19023 n=91 weight=31650 n=92 weight=57436 n=93 weight=18424 n=94 weight=76983 n=95 weight=17651 n=96 weight=23206 n=97 weight=72811 n=98 weight=77654 n=99 weight=86727 n=89 sticks out somewhat! And I've already taken n=88 :) 
[QUOTE=Greenbank]
n=89 weight=452294 n=89 sticks out somewhat! And I've already taken n=88 :)[/QUOTE] See my benchmarks for n=89, comparing dodeca_2_5 and 3_0 ( just for [0T,1T] ): dodeca_2_5: Number of Prp tests=1225 Time=46 sec. dodeca_3_0 Number of Prp tests=45391 Time=23 sec. So it isn't very important the number of prp tests, see my mpz_powm() instruction for n=89 bits modulus takes about say 50000 clock cycles, so if we are checking 45391 prp tests, then that take about 2*10^9 clock cycles or about 1.3 sec. for my pc ( 1.7 GHz ), so the prp testing time is about 5% of the total time, 95% is the sieving time! That was the reason why I've decreased all parameters in 2_5 version of dodeca program. I've also defined the weight of n ( for dodeca numbers ). See post #28 in this thread. 
R.Gerbicz
Why is [I]k[/I] maxed to 2^60 in dodeca.c? There are 4 more bits in 8byte unsigned int and furthermore, if you keep k/105 instead of [I]k[/I], the range can be extended to 105*(2^641) without using gmp variables, not so?

new dodeca program version 4.0
1 Attachment(s)
In this version there is no limitation on k, and I've also decreased prime_limit from 2000 to 1000 ( and try also O1 optimization flag ).
See the attachment for the code. Or download exe from [URL="http://www.robertgerbicz.tar.hu/dodeca_4_0.exe"]http://www.robertgerbicz.tar.hu/dodeca_4_0.exe[/URL] 
My first tests indicate that ver.4 is about 30% slower than ver.3. Please tell me, can I use ver.3 to test n=103 for k<2^60 (by removing the n>=100 condition from the source).

[QUOTE=Kosmaj]My first tests indicate that ver.4 is about 30% slower than ver.3. Please tell me, can I use ver.3 to test n=103 for k<2^60 (by removing the n>=100 condition from the source).[/QUOTE]
In some cases it is possible because it is using sieve_limit=1000. Yes you can change ver.3, by removing that condition. Note that in all of the new programs now you can change sieve_limit in the source and to do this you have to change also number_of_primes, because there is an error checking for this in the program, you can also change block_length and magic_constant, and of course magic_constant>=block_length>=sieve_limit has to be true . But note that in hexadeca program you can change only sieve_limit ( and number_of_primes ), don't change block_length otherwise the program won't search for the whole interval for n=76 ( there is no magic_constant for this hexadeca ). I've changed the source in dodeca_4_0 to use sieve_limit=2000 and number_of_primes=303 but this was still slower by 7% for n=99. I don't know why perhaps because we are using in that part mpz_t integers and not long variables. 
All times are UTC. The time now is 18:45. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.