mersenneforum.org Dodecaproths
 Register FAQ Search Today's Posts Mark Forums Read

2006-01-16, 13:57   #34
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

5BA16 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.
Attached Files
 dodeca_2_5.txt (16.1 KB, 278 views)

 2006-01-16, 14:01 #35 Greenbank     Jul 2005 2·193 Posts Thanks Robert! Links in Welcome - How to Help thread updated to point to Dodeca 2.5.
 2006-01-16, 17:48 #36 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 2×733 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.
 2006-01-17, 09:16 #37 Kosmaj     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.
 2006-01-17, 20:02 #38 robert44444uk     Jun 2003 Oxford, UK 1,933 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
2006-01-17, 20:58   #39
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·733 Posts

Quote:
 Originally Posted by 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
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,n-1) and (k,n) octoproths so we couldn't double the speed of the program because n-1,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 q-th 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 3-prp checking. If all numbers are 3-prp, 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 2006-01-17 at 21:04

2006-01-17, 23:05   #40
Kosmaj

Nov 2003

70468 Posts

Two questions/suggestions.

Quote:
 Originally Posted by 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.
(1)While doing this are you using the fact that k must be a multiple of several first primes, for example, for DodecaProths k must be an odd multiple of 3*5*7 for all n, while for some n (like 58 above) it also must be a multiple of 11. Then you can increase step 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 over-sieving? 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)?

2006-01-18, 00:05   #41
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×733 Posts

Quote:
 Originally Posted by Kosmaj Two questions/suggestions. (1)While doing this are you using the fact that k must be a multiple of several first primes, for example, for DodecaProths k must be an odd multiple of 3*5*7 for all n, while for some n (like 58 above) it also must be a multiple of 11. Then you can increase step 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.
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:
 Originally Posted by Kosmaj (2) In the second step are you sure you are not over-sieving? 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)?
No there is no oversieve! ( note there is also no oversieve in octo ). In fact there is a very-very 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.

Last fiddled with by R. Gerbicz on 2006-01-18 at 00:20

 2006-01-18, 10:25 #42 Kosmaj     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 2006-01-18 at 10:34
 2006-01-18, 11:11 #43 Greenbank     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.
2006-01-18, 13:10   #44
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×733 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.
Or see the attachment for the c code!
Attached Files
 dodeca_3_0.txt (16.1 KB, 248 views)