Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
AP26  AP27 Search :
AP 27 Search
Author 
Message 
Michael GoetzVolunteer moderator Project administrator Project scientist
Send message
Joined: 21 Jan 10 Posts: 12680 ID: 53948 Credit: 184,755,448 RAC: 174,504

Welcome to the AP27 Search (Arithmetic Progression of 27 primes)
An arithmetic progression is a sequence of numbers with a common difference between any two successive numbers in the sequence. For instance, the sequence 3, 5, 7, 9, 11, 13, 15, ... is an arithmetic progression with a common difference of 2.
Therefore, an arithmetic progression of primes is a sequence of primes with a common difference between any two successive numbers in the sequence. For example 3, 7, 11 is an arithmetic progression of 3 primes with a common difference of 4.
For an arithmetic progression (AP) of primes, APk is k primes of the form p + d*n for some d (the common difference between the primes) and k consecutive values of n. The above AP3 is 3 + 4*n for n=0,1,2.
n=0; 3 + 4*0 = 3 + 0 = 3
n=1; 3 + 4*1 = 3 + 4 = 7
n=2; 3 + 4*2 = 3 + 8 = 11
Another example is the AP10 of the form 199 + 210*n for n=0..9. This produces the following sequence: 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089.
APk is also sometimes notated PAPk (Primes in Arithmetic Progression).
We are searching for the longest AP, not the largest. Currently the longest known AP is of length 26. The first known AP26 was discovered on April 12th, 2010 here at PrimeGrid by Benoãt Perichon ([AF>HFR>RR] Jim PROFIT) of France. Since then, three additional AP26s have been found, one by James Fry, and two of them by Bryan Little (mfl0p). For a complete list of records including longest and largest AP's, please see Jens Kruse Andersen's Primes in Arithmetic Progression Records. Also, a list of the top 20 largest (not longest) AP's can be found at The Prime Pages: The Top 20.
New AP discoveries will be announced in the New APs forum thread.
Jaroslaw Wróblewski's AP26 algorithm will be used for the search. The AP26 algorithm is capable of finding AP27 and AP28 progressions as well as the shorter progressions.
The original AP26 program was written by Jaroslaw Wróblewski and adapted to BOINC by Geoff Reynolds.
The 2016 CPU and OpenCL versions of AP26 were updated by Bryan Little and Iain Bethune.
All builds by Brian Little and Iain Bethune
Additional information can be found here:
How to search for 26 primes in arithmetic progression? by Jaroslaw Wróblewski
Primes in arithmetic progression  Wikipedia
Prime Arithmetic Progression  Wolfram MathWorld
arithmetic sequence  The Prime Glossary at the Prime Pages
How to Participate?
Go to your PrimeGrid preferences page and select AP27.
Credit is currently set at 4043 cobblestones per WU.
WU expectations
Current WU's test 100 K's at 10 shifts each. The 20082010 AP26 tasks, at the end, tested 9 K's at 1 shift, so these tasks are about 111 times larger.
If K is divisible by one of the primes in the range 2959, this K is ignored, i.e. AP26 quits instantly. Those are just over 18% of all K's.
If K is divisible by 61, the time is increased by some 20% over an "ordinary" K and if a few next primes (67, 71, ...) divide K it can be even longer.
Progression of WU's
We are initially sending out work at both shift=0 and shift=640. No decision has been made about when to start searching additional shifts.
The tasks with shift=0 overlap somewhat with the original AP26 search and serves as a double check in case anything was missed. The original AP26 project searched six shifts to the following levels. Remember that each AP26 shift was 64 bits wide, whereas an AP27 shift is 640 bits wide. Our current shift therefore covered all six of the original AP26 shifts.
AP26 (2008) progress:
shift=0; k<43902416
shift=64; k<33973721
shift=128; k<25165464
shift=192; k<16288724
shift=256; k<9354514
shift=320; k<2751343
Initial AP27 progress: (24 August 2016 to 20 Sep 2016)
shift=0; k<2538946
shift=640; k<2538946  


For the app name do we use ap26 or ap27?
It seems that ap26 is still active. Thanks
Also the link on the Preferences Page takes you to AP26 not This Thread.
____________
Crunching@EVGA The Number One Team in the BOINC Community. Folding@EVGA The Number One Team in the Folding@Home Community.  

Michael GoetzVolunteer moderator Project administrator Project scientist
Send message
Joined: 21 Jan 10 Posts: 12680 ID: 53948 Credit: 184,755,448 RAC: 174,504

For the app name do we use ap26 or ap27?
It seems that ap26 is still active. Thanks
Also the link on the Preferences Page takes you to AP26 not This Thread.
Thanks for the link. I'll fix that momentarily.
The internal app name is ap26, if you're using app_info or other config files that need the app name. My apologies for the ambiguity between ap26 and ap27, but it's necessary that the internal app name be ap26 rather than being the same "ap27" that's being used in most other places.
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!
My lucky number is 75898^{524288}+1  


No Biggie on the app name ap26 works fine.
One more question on this Project, as far as the GTX Titan Graphics Cards would enabling Double Precision floating point that this card has?
I know very little BOINC Projects can use this setting and even slows down GPU Projects other then MilkyWay@home that is.
Thanks
____________
Crunching@EVGA The Number One Team in the BOINC Community. Folding@EVGA The Number One Team in the Folding@Home Community.  

Michael GoetzVolunteer moderator Project administrator Project scientist
Send message
Joined: 21 Jan 10 Posts: 12680 ID: 53948 Credit: 184,755,448 RAC: 174,504

No Biggie on the app name ap26 works fine.
One more question on this Project, as far as the GTX Titan Graphics Cards would enabling Double Precision floating point that this card has?
I know very little BOINC Projects can use this setting and even slows down GPU Projects other then MilkyWay@home that is.
Thanks
Double precision should NOT be enabled for most of our GPU apps. That includes AP27, PPSSieve, and GFN15 through GFN20.
With GFN 21 and 22, it's a bit more complicated. With those two, try it with Double Precision mode enabled and look in the stderr.txt file to see which transform it used. If it used OCL, then leave Double Precision mode on. If it instead used OCL4, turn Double Precision mode off. Or, more simply, try it both ways and see which runs faster.
I suspect that with older Titans, it will be faster with Double Precision mode on. With newer Titans, it may be faster with it off.
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!
My lucky number is 75898^{524288}+1  


Have you already tried a shortcut for possibly finding AP27s  use the same starting points as all known AP26s, to see if any of them are actually the first part of an AP27?  

Michael GoetzVolunteer moderator Project administrator Project scientist
Send message
Joined: 21 Jan 10 Posts: 12680 ID: 53948 Credit: 184,755,448 RAC: 174,504

Have you already tried a shortcut for possibly finding AP27s  use the same starting points as all known AP26s, to see if any of them are actually the first part of an AP27?
The ap26 program will find any sequences up to length 28. So, in effect, the answer is yes because we've been doing that since 2008. It's possible that an AP28 could have been found before the first AP26, but it's very unlikely.
Edit: Checking these numbers for primality is trivially easy because they're so short. That GFN in my signature is about 2.5 million digits long. The numbers we're looking at in the AP27 search are only about 15 to 20 digits long.
For kicks, here's PFGW checking one of the primes in an AP23 I found in 2010:
C:\PRPNet\prpclient5.4.0windows\prpclient1>pfgw64 V t q"146548848027836663"
PFGW Version 3.7.10.64BIT.20150809.Win_Dev [GWNUM 28.6]
Primality testing 146548848027836663 [N1, BrillhartLehmerSelfridge]
Running N1 test using base 5
Generic modular reduction using generic reduction FMA3 FFT length 32 on A 58bit number
Calling BrillhartLehmerSelfridge with factored part 56.14%
146548848027836663 is prime! (0.0153s+0.0018s)
15 thousandths of a second to test that number for primality. (There's probably faster methods of checking numbers so small.)
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!
My lucky number is 75898^{524288}+1  


So this is still the same app as for the AP26 search, CPU and GPUwise?  

Michael GoetzVolunteer moderator Project administrator Project scientist
Send message
Joined: 21 Jan 10 Posts: 12680 ID: 53948 Credit: 184,755,448 RAC: 174,504

So this is still the same app as for the AP26 search, CPU and GPUwise?
Same algorithm. New app.
The apps themselves were rewritten for newer hardware architectures, and are faster than the old apps. One obvious example is that the new CPU app can make use of AVX and AVX2.
We did investigate modifying the internals (changing the primes used in the internal sieve) to be better optimized for searching for AP27, but after some testing decided that the gain in searching for AP27s wasn't worth the penalty we saw in finding shorter sequences. In the end we stayed with the original algorithm.
It's not really a change in the algorithm, but the new app also checks the first 10 shifts simultaneously.
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!
My lucky number is 75898^{524288}+1  


Won't get work for AP26 ocl
Mo 03 Okt 2016 23:10:43 CEST   CUDA: NVIDIA GPU 0: GeForce GTX 460 (driver version unknown, CUDA version 8.0, compute capability 2.1, 708MB, 557MB available, 907 GFLOPS peak)
Mo 03 Okt 2016 23:10:43 CEST   OpenCL: NVIDIA GPU 0: GeForce GTX 460 (driver version 367.44, device version OpenCL 1.1 CUDA, 708MB, 557MB available, 907 GFLOPS peak)
Mo 03 Okt 2016 23:10:43 CEST   Host name: rr030
Mo 03 Okt 2016 23:10:43 CEST   Processor: 12 GenuineIntel Intel(R) Xeon(R) CPU X5650 @ 2.67GHz [Family 6 Model 44 Stepping 2]
Mo 03 Okt 2016 23:10:43 CEST   Processor features: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 popcnt aes lahf_lm ida arat epb dtherm tpr_shadow vnmi flexpriority ept vpid
Mo 03 Okt 2016 23:10:43 CEST   OS: Linux: 3.10.0327.28.3.el7.x86_64
Mo 03 Okt 2016 23:10:43 CEST   Memory: 5.66 GB physical, 5.89 GB virtual
Mo 03 Okt 2016 23:10:43 CEST   Disk: 49.98 GB total, 15.94 GB free
(...)
Mo 03 Okt 2016 23:10:44 CEST  PrimeGrid  Sending scheduler request: To fetch work.
Mo 03 Okt 2016 23:10:44 CEST  PrimeGrid  Requesting new tasks for NVIDIA
Mo 03 Okt 2016 23:10:46 CEST  PrimeGrid  Scheduler request completed: got 0 new tasks
[roadrunner@rr030 tmp]$ ./primegrid_ap27_2.01_x86_64pclinuxgnu__OCL_cuda_AP27 366384 366384 0
Beginning a new search with parameters from the command line
[roadrunner@rr030 tmp]$ cat stderr.txt
AP26 OpenCL 10shift search version 1.3 by Bryan Little and Iain Bethune
Compiled Aug 17 2016 with GCC 4.4.7 20120313 (Red Hat 4.4.717)
Command line: ./primegrid_ap27_2.01_x86_64pclinuxgnu__OCL_cuda_AP27 366384 366384 0
23:20:03 (24658): Can't open init data file  running in standalone mode
Error: boinc_get_opencl_ids() failed with error 108
[roadrunner@rr030 tmp]$ ldd /tmp/primegrid_ap27_2.01_x86_64pclinuxgnu__OCL_cuda_AP27
linuxvdso.so.1 => (0x00007fff93fef000)
libOpenCL.so.1 => /usr/lib64/nvidia/libOpenCL.so.1 (0x00007f0a4f8de000)
libpthread.so.0 => /lib64/libpthread.so.0 (0x00007f0a4f6c2000)
libm.so.6 => /lib64/libm.so.6 (0x00007f0a4f3bf000)
libc.so.6 => /lib64/libc.so.6 (0x00007f0a4effe000)
/lib64/ldlinuxx8664.so.2 (0x00007f0a4fb01000)
librt.so.1 => /lib64/librt.so.1 (0x00007f0a4edf6000)
libdl.so.2 => /lib64/libdl.so.2 (0x00007f0a4ebf1000)
"Use GPU when computer is in use" is enabled.
This is a Scientific Linux 7.2 with kmodnvida installed.
What have i missed?
(old app is working on the command line, though, gives me the AP25 for 366384 366384 0 in 39 seconds )  

Van ZimmermanVolunteer moderator Project administrator Volunteer tester Project scientist Send message
Joined: 30 Aug 12 Posts: 1951 ID: 168418 Credit: 6,015,702,526 RAC: 47,035

Not enough memory on the card. You need 1.5G, and it won't fetch tasks if BOINC detects less than that.  

Michael GoetzVolunteer moderator Project administrator Project scientist
Send message
Joined: 21 Jan 10 Posts: 12680 ID: 53948 Credit: 184,755,448 RAC: 174,504

What have i missed?
Besides the 1.5 MB requirement, this is the part you're missing when trying to run it manually: http://www.primegrid.com/forum_thread.php?id=6891&nowrap=true#98124
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!
My lucky number is 75898^{524288}+1  


Hm, even in standalonemode via the console i do need 1.5 GB of RAM and the app checks for it?
I know i started the old app on a Nvidia Quadro FX 580 with only 512 MB RAM way back in late 2009.
Anyways i got no spare card that satisfies the RAMrequirements, that is sad.  


hi,
is there also a record kept for largest *consecutive* AP? for example3, 7, 11 is a Prime AP but not a consecutive one as there is a prime between 3 and 7. Of course, this would be much harder to look for...
River~~
 


Have you already tried a shortcut for possibly finding AP27s  use the same starting points as all known AP26s, to see if any of them are actually the first part of an AP27?
Yes it would be sensible that as soon as a new longest Prime AP is found, we then extend that until we find the first nonprime number in the AP? Presumably that is why the app looks for 26, 27, or 28? But if we found the full 28. it would be easy to extend it: just be a primality test in a series of numbers, not a grid job but one that any one person could do and potentially get a new, even longer, record.
Seems to me the extended test would be ridiculously cheap to run (in fact is likely to stop almost instantly), so would not be a grid project but a one person effort. Of course it would come with a correspondingly very low chance of success.
It feels such an easy idea that my guess is that it has already been done without success,otherwise the extensions to them would already have been found and published. If my guess is right, that means we will not strike lucky by trying to extend the current record holder.
Such an extended test would be ridiculously cheap to run (in fact is likely to stop almost instantly), so would not be a grid project but a one person effort. Of course it would come with a correspondingly very low chance of success.
No doubt that is the motivation for looking for APs of length 26, 27, and 28 at the same time. If we get exactly 27 we already know the series ends with no 28.
But what happens in the unlikely event that we find 28? That leaves an easy cherrypick for anyone with a primality checker to test no 29 like the PG admins who sanity check the results beofre publication  it is just one number and a short one compared to a megaprime. I assume that you would do this, and in the doubly unlikely event that you do successfully extend the range, maybe still give the credit to the person with the lucky app?
I am not going to lose sleep over it, as the odds are around the same as winning a national lottery twice running...  

JarekVolunteer developer Send message
Joined: 28 Dec 08 Posts: 57 ID: 33488 Credit: 10 RAC: 0

hi,
is there also a record kept for largest *consecutive* AP? for example3, 7, 11 is a Prime AP but not a consecutive one as there is a prime between 3 and 7. Of course, this would be much harder to look for...
River~~
Yes:
http://primerecords.dk/cpap.htm
However the problem of finding an example of the longest known CPAP is dead in my opinion: While CPAP10 is known, finding CPAP11 seems to be an impossible task for human race at the moment.
 

JarekVolunteer developer Send message
Joined: 28 Dec 08 Posts: 57 ID: 33488 Credit: 10 RAC: 0

Regarding extending AP: The search program extends AP found back and forth, so the reported length is the maximal one. For example if the program reports AP25 found, we are sure this is not a part of an AP26.  


OK thanks Jarek
R~~  

compositeVolunteer tester Send message
Joined: 16 Feb 10 Posts: 702 ID: 55391 Credit: 546,453,210 RAC: 216,524

There is an easy extension that maybe has not been checked.
For each known AP, p + d*n, check the primality of numbers in the extensions
p + 2*d*(n + a),
p + 3*d*(n + a),
p + 4*d*(n + a),
p + k*d*(n + a),
etc
In other words, starting from some offset "a" into a known AP, select every k'th number in the AP to form a new AP with larger differences (which are a multiple of "d"), and test the forward and backward extensions of each such new AP. These APs start much shorter but at least the pump is "primed".
What about all those shorter APs that have been rejected? They are valid starting points for this strategy.
Edit. Added the general form.  


The progression is written as 299460668118437929+9026994*23#*n for n=0..24.
While locating such a progression clearly requires a lot of computational power, verifying that it is indeed real is extremely fast. For example, with PARI/GP, the full check:
prod(n=0,24,isprime(299460668118437929+9026994*23*19*17*13*11*7*5*3*2*n))
takes less than 1 millisecond to complete.
/JeppeSN  

Michael GoetzVolunteer moderator Project administrator Project scientist
Send message
Joined: 21 Jan 10 Posts: 12680 ID: 53948 Credit: 184,755,448 RAC: 174,504

Search Status:
We are currently up to approximately k=10.6M on both shift=0 and shift=640. Shift=0 encompasses all of the original 6 shifts done 6 years ago. We have now surpassed the original search limits for shift=320 and shift=256, so all tests done at those two shifts (as part of shift=0 tasks) are new work. Double checking on (oldstyle) shift=0, 64, 128, and 192 continues.
Therefore, 60% of the numbers checked (6 of 10 oldstyle shifts) in each shift=0 task are new, and of course 100% of the numbers checked in shift=640 tasks are new.
The original search limits can be found in the first post in this thread.
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!
My lucky number is 75898^{524288}+1  

mfl0pVolunteer developer Send message
Joined: 5 Apr 09 Posts: 193 ID: 38042 Credit: 611,010,742 RAC: 438,733

we are approaching k = 43902416 which is where the original Primegrid AP26 search stopped in 2010
____________
 


we are approaching k = 43902416 which is where the original Primegrid AP26 search stopped in 2010
Does that make a big find any more likely?
Notice we are now in the k = 44m range.
 

mfl0pVolunteer developer Send message
Joined: 5 Apr 09 Posts: 193 ID: 38042 Credit: 611,010,742 RAC: 438,733

Does that make a big find any more likely?
Notice we are now in the k = 44m range.
Not yet. Once we reach about 57,000,000 we will be in completely uncharted territory. This means 100% of the searching is new work that's never been tested.
Why 57,000,000 and not now you may be wondering? Well, after PrimeGrid's AP26 search ended in 2010, I continued the search on my own . I had multiple GPUs running, but I wasn't searching linearly so there are some spots skipped between where we are now and 57,000,000. So it's possible I missed something.
Keep in mind this is only for SHIFT=0 work units. All SHIFT=640 work units have been in uncharted territory since the start of AP27 search.
____________
 


Hi, I joined PG about 1 month ago, (April 2019), and have found about 150 AP. As the list grows it's more difficult to identify the individual records. As a member of CSF, I report each find with a screenshot record. Any chance of a mre friendly search sequence in the list. Thanks.
____________
 

dthononVolunteer tester Send message
Joined: 6 Dec 17 Posts: 295 ID: 957147 Credit: 1,041,256,900 RAC: 1,473,583

Hi, I joined PG about 1 month ago, (April 2019), and have found about 150 AP. As the list grows it's more difficult to identify the individual records. As a member of CSF, I report each find with a screenshot record. Any chance of a mre friendly search sequence in the list. Thanks.
In preferences, select reporting of AP23 and above only and print the notification ?  

Michael GoetzVolunteer moderator Project administrator Project scientist
Send message
Joined: 21 Jan 10 Posts: 12680 ID: 53948 Credit: 184,755,448 RAC: 174,504

Hi, I joined PG about 1 month ago, (April 2019), and have found about 150 AP. As the list grows it's more difficult to identify the individual records. As a member of CSF, I report each find with a screenshot record. Any chance of a mre friendly search sequence in the list. Thanks.
The lower limit on what the system shows you is rather arbitrary. For every AP20 you find, there's about 4 AP19's the system doesn't bother showing you. And about 16 AP18's, and so on.
If the number of AP20's you're seeing is too many to be manageable, ignore them and only be concerned with the AP21's, or even the AP22's.
Regardless of what you choose to see, using the notifications for reporting the results elsewhere is a good idea.
At this time, I don't plan on making any changes to the AP27 reporting, although it can't hurt to give me suggestions for how you might like to see it work.
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!
My lucky number is 75898^{524288}+1  

Post to thread
Message boards :
AP26  AP27 Search :
AP 27 Search 