Thread: Dodecaproths
View Single Post
Old 2006-01-17, 20:58   #39
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

22·367 Posts

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?


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
R. Gerbicz is offline