Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
AP26  AP27 Search :
Change to AP27 search parameters
Author 
Message 
Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13827 ID: 53948 Credit: 374,054,093 RAC: 399,789

When we started the AP 27 search, we decided to search both shift 0 and shift 640 equally.
With an AP27 challenge starting in a few weeks, I decided to look into whether it was time to also start searching shift 1280.
The higher the shift, the fewer AP sequences you'll find. But as k increases within a shift, the number of sequences you find also decreases. There comes a point where you should start searching the next shift.
Right now, for every million k we search, we're finding about 1400 APs at shift 0 and about 1050 APs at shift 640.
If we started shift 1280, we'd probably get something between 700 and 1000 APs per million k. Definitely less than either 0 or 640.
Rather than open up 1280, we've closed down 640 and will run only shift 0 for a while until it's producing about 1050 APs per million k.
Both shift 0 and shift 640 are currently at approximately k=74M.
____________
My lucky number is 75898^{524288}+1  


I may have missed it in my thread browsing, but what exactly are "shifts"?
Also, will this affect task size (i.e. runtime) and/or credit?
____________
Eating more cheese on Thursdays.  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13827 ID: 53948 Credit: 374,054,093 RAC: 399,789

I may have missed it in my thread browsing, but what exactly are "shifts"?
Also, will this affect task size (i.e. runtime) and/or credit?
Read this:
http://www.math.uni.wroc.pl/~jwr/AP26/AP26v3.pdf
If this was GFN, you could think of the shift as "N" and k as "B". It's not the same numerical relationship, but the roles are similar. The shift is a set of candidates that are going to be tested, with k iterating through the set.
In the paper, each shift was 64 bits, so the shifts were 0, 64, 128, 192, etc.
In the AP27 version of the search, we search 10 shifts at once, effectively creating 640 bit shifts, so the shifts are 0, 640, 1280, 1920, etc.
Right now, both shift 0 and shift 640 are at k = ~74M. We're freezing shift 640 where it is, and continuing with shift 0 until it reaches k = 143 M. At that point we will resume shift 640 and we will also start shift 1280.
From then on we will follow this pattern:
* All the shifts that have been started (initially, 0, 640, and 1280) will run in parallel until the most recently started shift (1280 initially) reaches k = 70M. Every shift will be approximately 70M k's ahead of the next shift.
* When the most recent shift gets to k = 70M, another shift (the next will be 1920) is started at k=0.
* The process then repeats.
* When a shift reaches k = 318M, it is shut down (the AP27 program will overflow otherwise).
* Shift 9600 is the last shift where k can go up to 318M. Shifts beyond 9600 have lower K limits.
____________
My lucky number is 75898^{524288}+1  


That clears it up a bit, thanks. The paper was an interesting read, will need some digesting, though.
____________
Eating more cheese on Thursdays.  

dukebgVolunteer tester
Send message
Joined: 21 Nov 17 Posts: 242 ID: 950482 Credit: 23,670,125 RAC: 0

In the AP27 version of the search, we search 10 shifts at once, effectively creating 640 bit shifts, so the shifts are 0, 640, 1280, 2560, etc.
Wouldn't the next after 1280 be 1920 then?  


In the AP27 version of the search, we search 10 shifts at once, effectively creating 640 bit shifts, so the shifts are 0, 640, 1280, 2560, etc.
Wouldn't the next after 1280 be 1920 then?
Either: ..., 0, 640, 1280, 1920, 2560, 3200, 3840, ... or: ..., 5, 10, 20, 40, 80, 160, 320, 640, 1280, 2560, 5120, 10240, ... /JeppeSN  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13827 ID: 53948 Credit: 374,054,093 RAC: 399,789

In the AP27 version of the search, we search 10 shifts at once, effectively creating 640 bit shifts, so the shifts are 0, 640, 1280, 2560, etc.
Wouldn't the next after 1280 be 1920 then?
Yes, it would be. I'll correct the 'plan'. Thanks.
____________
My lucky number is 75898^{524288}+1  


So here's a somewhat "lazy" question because I haven't done any digging. I'm wondering how the list of ap's found is sorted. I ask because several ap's I've found recently are listed much lower than earlier finds.
Is this because of the change in parameters and we are only doing shift 0 at the moment? Also, is there a size for the ap (not referring to whether it's a 20 or 21 or ....) but with in the same range? (maybe this is the reason for the order)
Cheers  


So here's a somewhat "lazy" question because I haven't done any digging. I'm wondering how the list of ap's found is sorted. I ask because several ap's I've found recently are listed much lower than earlier finds.
Is this because of the change in parameters and we are only doing shift 0 at the moment? Also, is there a size for the ap (not referring to whether it's a 20 or 21 or ....) but with in the same range? (maybe this is the reason for the order)
Cheers
Currently, looking only at your AP24, I see this:AP24: 316274648710690823+72225058*23#*n for n=0..23 (20181007 12:11:54 UTC)
AP24: 288692820895984987+15022730*23#*n for n=0..23 (20161130 21:36:43 UTC)
AP24: 243773399004862751+10054941*23#*n for n=0..23 (20161118 23:03:18 UTC)
AP24: 265437309240041647+4081573*23#*n for n=0..23 (20161002 02:09:19 UTC)
AP24: 251506340752380587+4245962*23#*n for n=0..23 (20161003 09:24:18 UTC)
AP24: 213679296184640981+6537955*23#*n for n=0..23 (20161023 03:20:27 UTC)
AP24: 194193315973220033+5435343*23#*n for n=0..23 (20161014 01:35:27 UTC)
AP24: 57568392051724789+24248430*23#*n for n=0..23 (20170313 07:15:13 UTC)
This seems to be "unsorted". It is not sorted by smallest term (the part before the plus, such as 316274648710690823). It is not sorted by the common difference in the progression (the coefficient to n, such as 72225058*23#). And it is also not sorted by the date (such as (20181007 12:11:54 UTC)).
/JeppeSN  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13827 ID: 53948 Credit: 374,054,093 RAC: 399,789

So here's a somewhat "lazy" question because I haven't done any digging. I'm wondering how the list of ap's found is sorted. I ask because several ap's I've found recently are listed much lower than earlier finds.
Is this because of the change in parameters and we are only doing shift 0 at the moment? Also, is there a size for the ap (not referring to whether it's a 20 or 21 or ....) but with in the same range? (maybe this is the reason for the order)
Cheers
There's two places the AP list is displayed, the big list of everyone's APs (including some that weren't found at PrimeGrid), and your personal list.
Both are sorted first by length, i.e., the AP26s are shown by AP25s, and within each length, by size. Size is the largest prime in that AP sequence.
This seems to be "unsorted". It is not sorted by smallest term (the part before the plus, such as 316274648710690823). It is not sorted by the common difference in the progression (the coefficient to n, such as 72225058*23#). And it is also not sorted by the date (such as (20181007 12:11:54 UTC)).
You were SO close! It's sorted by the largest term. That incorporates both the first term and the difference between terms.
____________
My lucky number is 75898^{524288}+1  


There's two places the AP list is displayed, the big list of everyone's APs (including some that weren't found at PrimeGrid), and your personal list.
Both are sorted first by length, i.e., the AP26s are shown by AP25s, and within each length, by size. Size is the largest prime in that AP sequence.
This seems to be "unsorted". It is not sorted by smallest term (the part before the plus, such as 316274648710690823). It is not sorted by the common difference in the progression (the coefficient to n, such as 72225058*23#). And it is also not sorted by the date (such as (20181007 12:11:54 UTC)).
You were SO close! It's sorted by the largest term. That incorporates both the first term and the difference between terms.
Thanks much  I just wasn't sure how things were sorted.
Cheers Rick
____________
@AggieThePew
 


You were SO close! It's sorted by the largest term. That incorporates both the first term and the difference between terms.
Ah, yes, that is true:(largest term: 686871244638829403) AP24: 316274648710690823+72225058*23#*n for n=0..23 (20181007 12:11:54 UTC)
(largest term: 365776491767492287) AP24: 288692820895984987+15022730*23#*n for n=0..23 (20161130 21:36:43 UTC)
(largest term: 295366668848388161) AP24: 243773399004862751+10054941*23#*n for n=0..23 (20161118 23:03:18 UTC)
(largest term: 286380415437785377) AP24: 265437309240041647+4081573*23#*n for n=0..23 (20161002 02:09:19 UTC)
(largest term: 273292949267672207) AP24: 251506340752380587+4245962*23#*n for n=0..23 (20161003 09:24:18 UTC)
(largest term: 247226432516900531) AP24: 213679296184640981+6537955*23#*n for n=0..23 (20161023 03:20:27 UTC)
(largest term: 222082800167221463) AP24: 194193315973220033+5435343*23#*n for n=0..23 (20161014 01:35:27 UTC)
(largest term: 181990384410689089) AP24: 57568392051724789+24248430*23#*n for n=0..23 (20170313 07:15:13 UTC) /JeppeSN  


Just a question. Since we've changed the search pool so to speak and limited it to just 0 for now was wondering if your estimate of found APs was holding true.  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13827 ID: 53948 Credit: 374,054,093 RAC: 399,789

Just a question. Since we've changed the search pool so to speak and limited it to just 0 for now was wondering if your estimate of found APs was holding true.
I'm not sure I understand your question.
____________
My lucky number is 75898^{524288}+1  


Asked the wrong question.
Since the change to shift 0 only, is there any change in the distribution of APs found? Ie, more AP20's or more AP22's ? Just curious if the increase in units being worked made any difference what so ever in what AP's were found both in number and/or number (2027).  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13827 ID: 53948 Credit: 374,054,093 RAC: 399,789

Asked the wrong question.
Since the change to shift 0 only, is there any change in the distribution of APs found? Ie, more AP20's or more AP22's ? Just curious if the increase in units being worked made any difference what so ever in what AP's were found both in number and/or number (2027).
A) I don't know. This isn't the kind of thing I normally look at.
B) The change has only been in place for a few days.
C) When analyzing the data while we were considering whether or not to change the shifts, one of the things I looked at is whether the likelihood of finding APs of a certain length as either k or the shift varied was different than the overall likelihood of finding APs in general. I did not see any consistent pattern indicating that the probability of finding length X APs would be any different than length Y if we vary the parameters. In other words, we'll find more (or less) APs, but it doesn't favor long APs vs short APs (or viceversa).
____________
My lucky number is 75898^{524288}+1  


Thanks was just wondering because the higher end AP's I was finding seem to have dropped off. I wasn't sure if it was because there's a lot more folks or units being run or what. No biggie just curious.  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13827 ID: 53948 Credit: 374,054,093 RAC: 399,789

Here's some raw data. Feel free to come to your own conclusions. AP20 through AP26 are percentages of total.
+++++++++++
 month  day  total  AP20  AP21  AP22  AP23  AP24  AP25  AP26 
+++++++++++
 10  20  232  81.0345  15.5172  2.5862  0.0000  0.8621  0.0000  0.0000 
 10  21  244  71.7213  19.6721  6.5574  1.2295  0.8197  0.0000  0.0000 
 10  22  256  78.1250  17.5781  3.5156  0.7813  0.0000  0.0000  0.0000 
 10  23  202  78.7129  14.8515  4.9505  0.9901  0.4950  0.0000  0.0000 
 10  24  161  72.0497  19.8758  6.2112  1.8634  0.0000  0.0000  0.0000 
 10  25  167  71.8563  19.1617  6.5868  2.3952  0.0000  0.0000  0.0000 
 10  26  239  76.5690  16.7364  5.4393  0.8368  0.0000  0.4184  0.0000 
 10  27  238  76.8908  17.2269  5.4622  0.0000  0.4202  0.0000  0.0000 
 10  28  205  77.0732  18.5366  3.9024  0.4878  0.0000  0.0000  0.0000 
 10  29  221  79.6380  15.3846  2.2624  2.7149  0.0000  0.0000  0.0000 
 10  30  200  75.0000  19.5000  4.5000  0.5000  0.5000  0.0000  0.0000 
 10  31  161  72.6708  18.0124  6.2112  2.4845  0.6211  0.0000  0.0000 
 11  1  184  77.1739  16.8478  5.9783  0.0000  0.0000  0.0000  0.0000 
 11  2  185  72.4324  20.0000  7.5676  0.0000  0.0000  0.0000  0.0000 
 11  3  212  78.3019  15.0943  5.6604  0.4717  0.4717  0.0000  0.0000 
 11  4  225  76.4444  19.5556  2.2222  1.3333  0.4444  0.0000  0.0000 
 11  5  262  76.7176  17.5573  4.5802  1.1450  0.0000  0.0000  0.0000 
 11  6  297  75.0842  21.2121  2.6936  1.0101  0.0000  0.0000  0.0000 
 11  7  393  79.6438  16.2850  3.3079  0.5089  0.2545  0.0000  0.0000 
 11  8  245  76.3265  18.7755  3.6735  0.8163  0.4082  0.0000  0.0000 
 11  9  140  76.4286  20.0000  2.8571  0.7143  0.0000  0.0000  0.0000 
+++++++++++
____________
My lucky number is 75898^{524288}+1  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13827 ID: 53948 Credit: 374,054,093 RAC: 399,789

In the AP27 version of the search, we search 10 shifts at once, effectively creating 640 bit shifts, so the shifts are 0, 640, 1280, 1920, etc.
Right now, both shift 0 and shift 640 are at k = ~74M. We're freezing shift 640 where it is, and continuing with shift 0 until it reaches k = 143 M. At that point we will resume shift 640 and we will also start shift 1280.
From then on we will follow this pattern:
* All the shifts that have been started (initially, 0, 640, and 1280) will run in parallel until the most recently started shift (1280 initially) reaches k = 70M. Every shift will be approximately 70M k's ahead of the next shift.
* When the most recent shift gets to k = 70M, another shift (the next will be 1920) is started at k=0.
* The process then repeats.
* When a shift reaches k = 318M, it is shut down (the AP27 program will overflow otherwise).
* Shift 9600 is the last shift where k can go up to 318M. Shifts beyond 9600 have lower K limits.
Shift 0 has reached 143M, and we have resumed shift 640 and started shift 1280.
In case anyone's wondering, extrapolating how long it too to do 70M on shift 0 to all 11 shifts, if the processing rate stayed the same we'd have 41 years worth of work.
____________
My lucky number is 75898^{524288}+1  

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 511 ID: 1241833 Credit: 411,008,852 RAC: 19,226

I don't really understand the paper posted by Michael in the earlier post.
Is there a simple explanation of the parameters of the AP search? I found this line in stderr:
"ap27_3.01_opencl_windows64.exe 196376536 196376656 0"
How will this relate to the AP tested? Or is it not as simple as that?
Thanks
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000  

Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 207 ID: 1108183 Credit: 12,607,611 RAC: 8,230

"ap27_3.01_opencl_windows64.exe 196376536 196376656 0"
How will this relate to the AP tested? Or is it not as simple as that?
The large numbers are lower and upper limits for k, and the 0 is a shift. We are searching for AP's of the form a_i = b*MOD + R + i*D, where:
i is the variable indexing the AP; in the best case (an AP28) it goes from 2 to 25.
b ranges over [0, 639] when shift = 0, or [640, 1279] when shift = 640, etc.
MOD = 2*3*5*29*31*37*41*43*47*53*59 = 258559632607830.
R is a number modulo MOD; for each k it ranges over 5489436680 "good" values, which are determined by the sieving step.
D = k*23# = k*223092870.
For example, if I'm reverseengineering things correctly, I think robish's AP27 was found with k = 81292139, b = 938, R = 191367151342301, and i running from 1 to 25.
But notice that each workunit tests a huge number of (k, b, R) triples, and sieves out a far huger number. In particular, the number of "good" R's is about 1/47000 of MOD. I think this is really the key to how Jarek made the app so efficient: it sieves out 46999 out of every 47000 candidates without even iterating over them.  

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 511 ID: 1241833 Credit: 411,008,852 RAC: 19,226

Thanks, that was very helpful.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000  

Post to thread
Message boards :
AP26  AP27 Search :
Change to AP27 search parameters 