## Other

drummers-lowrise

Message boards : AP26 - AP27 Search : AP 27 Search

Author Message
Michael Goetz
Volunteer moderator
Project scientist

Joined: 21 Jan 10
Posts: 12669
ID: 53948
Credit: 184,159,862
RAC: 1

Message 98979 - Posted: 20 Sep 2016 | 16:20:34 UTC

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, AP-k 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 AP-3 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 AP-10 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.

AP-k is also sometimes notated PAP-k (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 2008-2010 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 29-59, 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

bcavnaugh

Joined: 8 Nov 13
Posts: 173
ID: 273570
Credit: 602,459,663
RAC: 0

Message 99079 - Posted: 23 Sep 2016 | 17:25:37 UTC - in response to Message 98979.

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 Goetz
Volunteer moderator
Project scientist

Joined: 21 Jan 10
Posts: 12669
ID: 53948
Credit: 184,159,862
RAC: 1

Message 99080 - Posted: 23 Sep 2016 | 17:41:02 UTC - in response to Message 99079.

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.

____________

My lucky number is 75898524288+1

bcavnaugh

Joined: 8 Nov 13
Posts: 173
ID: 273570
Credit: 602,459,663
RAC: 0

Message 99085 - Posted: 23 Sep 2016 | 21:45:03 UTC - in response to Message 99080.

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 Goetz
Volunteer moderator
Project scientist

Joined: 21 Jan 10
Posts: 12669
ID: 53948
Credit: 184,159,862
RAC: 1

Message 99089 - Posted: 24 Sep 2016 | 1:21:38 UTC - in response to Message 99085.

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, PPS-Sieve, 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.
____________

My lucky number is 75898524288+1

robertmiles

Joined: 26 Dec 09
Posts: 111
ID: 52682
Credit: 52,401,881
RAC: 0

Message 99116 - Posted: 24 Sep 2016 | 20:00:58 UTC

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 Goetz
Volunteer moderator
Project scientist

Joined: 21 Jan 10
Posts: 12669
ID: 53948
Credit: 184,159,862
RAC: 1

Message 99118 - Posted: 24 Sep 2016 | 20:13:15 UTC - in response to Message 99116.

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\prpclient-5.4.0-windows\prpclient-1>pfgw64 -V -t -q"146548848027836663" PFGW Version 3.7.10.64BIT.20150809.Win_Dev [GWNUM 28.6] Primality testing 146548848027836663 [N-1, Brillhart-Lehmer-Selfridge] Running N-1 test using base 5 Generic modular reduction using generic reduction FMA3 FFT length 32 on A 58-bit number Calling Brillhart-Lehmer-Selfridge 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.)
____________

My lucky number is 75898524288+1

Volunteer developer

Joined: 11 Sep 08
Posts: 580
ID: 28785
Credit: 187,195,056
RAC: 0

Message 99416 - Posted: 3 Oct 2016 | 20:08:11 UTC

So this is still the same app as for the AP26 search, CPU and GPU-wise?

Michael Goetz
Volunteer moderator
Project scientist

Joined: 21 Jan 10
Posts: 12669
ID: 53948
Credit: 184,159,862
RAC: 1

Message 99426 - Posted: 3 Oct 2016 | 20:58:48 UTC - in response to Message 99416.

So this is still the same app as for the AP26 search, CPU and GPU-wise?

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

My lucky number is 75898524288+1

Volunteer developer

Joined: 11 Sep 08
Posts: 580
ID: 28785
Credit: 187,195,056
RAC: 0

Message 99433 - Posted: 3 Oct 2016 | 21:23:50 UTC

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.0-327.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_64-pc-linux-gnu__OCL_cuda_AP27 366384 366384 0 Beginning a new search with parameters from the command line [roadrunner@rr030 tmp]\$ cat stderr.txt AP26 OpenCL 10-shift search version 1.3 by Bryan Little and Iain Bethune Compiled Aug 17 2016 with GCC 4.4.7 20120313 (Red Hat 4.4.7-17) Command line: ./primegrid_ap27_2.01_x86_64-pc-linux-gnu__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_64-pc-linux-gnu__OCL_cuda_AP27 linux-vdso.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/ld-linux-x86-64.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 kmod-nvida 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 Zimmerman
Volunteer moderator
Volunteer tester
Project scientist

Joined: 30 Aug 12
Posts: 1951
ID: 168418
Credit: 6,015,372,578
RAC: 0

Message 99434 - Posted: 3 Oct 2016 | 21:28:28 UTC

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

Michael Goetz
Volunteer moderator
Project scientist

Joined: 21 Jan 10
Posts: 12669
ID: 53948
Credit: 184,159,862
RAC: 1

Message 99441 - Posted: 3 Oct 2016 | 21:51:13 UTC - in response to Message 99433.

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

____________

My lucky number is 75898524288+1

Volunteer developer

Joined: 11 Sep 08
Posts: 580
ID: 28785
Credit: 187,195,056
RAC: 0

Message 99443 - Posted: 3 Oct 2016 | 21:54:25 UTC

Hm, even in standalone-mode 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 RAM-requirements, that is sad.

River~~

Joined: 17 Mar 07
Posts: 342
ID: 6533
Credit: 15,792,075
RAC: 0

Message 100273 - Posted: 25 Oct 2016 | 7:01:58 UTC

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~~

River~~

Joined: 17 Mar 07
Posts: 342
ID: 6533
Credit: 15,792,075
RAC: 0

Message 100274 - Posted: 25 Oct 2016 | 7:16:34 UTC - in response to Message 99116.

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 non-prime 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 cherry-pick 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 mega-prime. 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...

Jarek
Volunteer developer

Joined: 28 Dec 08
Posts: 57
ID: 33488
Credit: 10
RAC: 0

Message 100287 - Posted: 25 Oct 2016 | 14:05:09 UTC - in response to Message 100273.

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 CPAP-10 is known, finding CPAP-11 seems to be an impossible task for human race at the moment.

Jarek
Volunteer developer

Joined: 28 Dec 08
Posts: 57
ID: 33488
Credit: 10
RAC: 0

Message 100288 - Posted: 25 Oct 2016 | 14:14:13 UTC - in response to Message 100274.

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.

River~~

Joined: 17 Mar 07
Posts: 342
ID: 6533
Credit: 15,792,075
RAC: 0

Message 100313 - Posted: 25 Oct 2016 | 18:45:03 UTC - in response to Message 100288.

OK thanks Jarek
R~~

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 702
ID: 55391
Credit: 544,880,366
RAC: 0

Message 100322 - Posted: 25 Oct 2016 | 23:50:21 UTC - in response to Message 100288.

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.

JeppeSN

Joined: 5 Apr 14
Posts: 877
ID: 306875
Credit: 10,485,261
RAC: 0

Message 101051 - Posted: 18 Nov 2016 | 14:44:09 UTC - in response to Message 101017.

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 Goetz
Volunteer moderator
Project scientist

Joined: 21 Jan 10
Posts: 12669
ID: 53948
Credit: 184,159,862
RAC: 1

Message 101105 - Posted: 19 Nov 2016 | 15:30:31 UTC

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 (old-style) shift=0, 64, 128, and 192 continues.

Therefore, 60% of the numbers checked (6 of 10 old-style 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.
____________

My lucky number is 75898524288+1

mfl0p
Volunteer developer

Joined: 5 Apr 09
Posts: 191
ID: 38042
Credit: 607,884,344
RAC: 3

Message 111826 - Posted: 21 Nov 2017 | 23:29:07 UTC

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

dlawson

Joined: 7 Jun 17
Posts: 19
ID: 895562
Credit: 43,792,134
RAC: 0

Message 111878 - Posted: 24 Nov 2017 | 21:34:40 UTC - in response to Message 111826.

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.

mfl0p
Volunteer developer

Joined: 5 Apr 09
Posts: 191
ID: 38042
Credit: 607,884,344
RAC: 3

Message 111979 - Posted: 30 Nov 2017 | 0:22:29 UTC - in response to Message 111878.

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

Homefarm

Joined: 8 Apr 19
Posts: 3
ID: 1113211
Credit: 93,309,803
RAC: 0

Message 129651 - Posted: 20 May 2019 | 13:51:21 UTC

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

dthonon
Volunteer tester

Joined: 6 Dec 17
Posts: 294
ID: 957147
Credit: 1,036,179,830
RAC: 0

Message 129655 - Posted: 20 May 2019 | 16:05:05 UTC - in response to Message 129651.

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 Goetz
Volunteer moderator
Project scientist

Joined: 21 Jan 10
Posts: 12669
ID: 53948
Credit: 184,159,862
RAC: 1

Message 129658 - Posted: 20 May 2019 | 17:16:49 UTC - in response to Message 129651.

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.

____________

My lucky number is 75898524288+1

Message boards : AP26 - AP27 Search : AP 27 Search