Dodecaproths

[R. Gerbicz]

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.

[Greenbank]

Thanks Robert!

Links in Welcome - How to Help thread updated to point to Dodeca 2.5.

[R. Gerbicz]

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.

[Kosmaj]

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.

[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

[R. Gerbicz]

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.

[Kosmaj]

Two questions/suggestions.

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)?

[R. Gerbicz]

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% ).

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.

[Kosmaj]

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.

[Greenbank]

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.

[R. Gerbicz]

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!