mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Octoproth Search (https://www.mersenneforum.org/forumdisplay.php?f=63)
-   -   Dodecaproths (https://www.mersenneforum.org/showthread.php?t=5358)

robert44444uk 2006-01-13 19:40

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 (3-chain):

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 n-1, 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

robert44444uk 2006-01-13 19:50

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

Kosmaj 2006-01-14 08:44

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.

Kosmaj 2006-01-14 09:33

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

R. Gerbicz 2006-01-14 10:23

[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!

Kosmaj 2006-01-14 14:39

[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 so-called 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:

R. Gerbicz 2006-01-14 14:51

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

R. Gerbicz 2006-01-14 16:27

[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.

R. Gerbicz 2006-01-14 16:45

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

Kosmaj 2006-01-14 16:52

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=52-55 when the guys find all OctoProths). Up to k=1000T (1E15) nothing...

R. Gerbicz 2006-01-14 17:00

[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=52-55 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

Kosmaj 2006-01-14 17:13

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

Kosmaj 2006-01-14 17:30

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.

R. Gerbicz 2006-01-14 18:15

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 3-probable 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.

tcadigan 2006-01-14 18:15

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.

R. Gerbicz 2006-01-14 18:36

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.

Kosmaj 2006-01-15 00:58

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=57-62 to 2000T (2E15) but besides the one for n=57 I found none. I'm proceeding with n=63-70 to 2000T (will skip n=66).

Kosmaj 2006-01-15 10:23

R. Gerbicz
 
I noticed a large slow-down 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 cmd-line as you mentioned before for octo.exe. Thanks.

BTW, I checked all n=67-70 to 3000T but found no new DodecaProths.

R. Gerbicz 2006-01-15 12:05

[QUOTE=Kosmaj]I noticed a large slow-down 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 ).

Kosmaj 2006-01-15 13:24

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]

Kosmaj 2006-01-15 13:29

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]

R. Gerbicz 2006-01-15 13:44

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.

Kosmaj 2006-01-15 15:21

Thanks a lot, now is much better :smile:

n=70 to 3E15, was 1970 sec, now 1300 sec (estimate)
n=70 3E15-1E16, 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.

R. Gerbicz 2006-01-15 20:06

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 3-probable 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.

Kosmaj 2006-01-15 23:46

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]
54-55 [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]

Kosmaj 2006-01-16 10:44

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.

Greenbank 2006-01-16 11:34

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.

R. Gerbicz 2006-01-16 11:54

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*=(1-length(l)/p)/(1-1/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.

Greenbank 2006-01-16 12:14

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 3-probable 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.

R. Gerbicz 2006-01-16 12:29

[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 3-probable 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!

Greenbank 2006-01-16 12:36

Yup, just noticed that:-

$ ../dodeca20 50 717000000000000 720000000000000
You can also find the k n values in results_dodeca.txt file ( These are 3-probable 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 3-probable 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]

robert44444uk 2006-01-16 12:52

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

Greenbank 2006-01-16 13:05

[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 ;-) ).

R. Gerbicz 2006-01-16 13:57

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.

Greenbank 2006-01-16 14:01

Thanks Robert!

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

R. Gerbicz 2006-01-16 17:48

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 2006-01-17 09:16

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.

robert44444uk 2006-01-17 20:02

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

R. Gerbicz 2006-01-17 20:58

[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,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 2006-01-17 23:05

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 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 2006-01-18 00:05

[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 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)?[/QUOTE]
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 2006-01-18 10:25

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.

Greenbank 2006-01-18 11:11

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 2006-01-18 13:10

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!

Kosmaj 2006-01-19 04:11

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.

Greenbank 2006-01-20 12:23

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

R. Gerbicz 2006-01-20 16:19

[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.

Kosmaj 2006-01-24 22:01

R.Gerbicz
 
Why is [I]k[/I] maxed to 2^60 in dodeca.c? There are 4 more bits in 8-byte unsigned int and furthermore, if you keep k/105 instead of [I]k[/I], the range can be extended to 105*(2^64-1) without using gmp variables, not so?

R. Gerbicz 2006-01-24 22:02

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]

Kosmaj 2006-01-25 14:27

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

R. Gerbicz 2006-01-25 14:49

[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 16:45.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.