20060116, 13:57  #34 
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
dodeca 2.5 program
In this version you can use T=10^12, see the octoproths thread.
Exe for windows: http://www.robertgerbicz.tar.hu/dodeca_2_5.exe Or see the attachment for the c code. 
20060116, 14:01  #35 
Jul 2005
2×193 Posts 
Thanks Robert!
Links in Welcome  How to Help thread updated to point to Dodeca 2.5. 
20060116, 17:48  #36 
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
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.

20060117, 09:16  #37 
Nov 2003
2×1,811 Posts 
n=58
Found 6 DodecaProths for n=58:
17871561203266155 58 42210084958591935 58 45307176385075605 58 46259463855164175 58 50067984112666905 58 52035604613787795 58 Checked to 7E16. I'm stopping here and releasing n=58 so that Greenbank can continue and register his k. 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 isprime function returns 1 if the input number is a proven prime. 
20060117, 20:02  #38 
Jun 2003
Oxford, UK
2·7·137 Posts 
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 
20060117, 20:58  #39  
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
Quote:
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. Last fiddled with by R. Gerbicz on 20060117 at 21:04 

20060117, 23:05  #40  
Nov 2003
2×1,811 Posts 
Two questions/suggestions.
Quote:
(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)? 

20060118, 00:05  #41  
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
Quote:
Quote:
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. Last fiddled with by R. Gerbicz on 20060118 at 00:20 

20060118, 10:25  #42 
Nov 2003
2×1,811 Posts 
n=60 and n=76
Three found
6584335653605325 60 51593298019338075 60 87084056712267615 60 Checked to 2E17 and stopped. No new reservations today. Just ran into the first one n=76 37990374090023355 76 In progress to 6E16. Last fiddled with by Kosmaj on 20060118 at 10:34 
20060118, 11:11  #43 
Jul 2005
2·193 Posts 
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. 
20060118, 13:10  #44 
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
dodeca 3.0 program
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 http://www.robertgerbicz.tar.hu/dodeca_3_0.exe Or see the attachment for the c code! 