Welcome to the AP26 Search (Arithmetic Progression of 26 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. The current record is an AP-25 discovered May 17, 2008, by Raanan Chermoni & Jaroslaw Wroblewski. 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 AP's can be found at The Prime Pages: The Top 20

Jaroslaw Wroblewski's AP26 code will be used for the search. Geoff Reynolds adapted the program for use with BOINC and for compiling without GMP.

Additional information can be found here:

How to search for 26 primes in arithmetic progression? by Jaroslaw Wroblewski
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 AP26.

Credit is currently set at 13.61 cobblestones per WU..

WU expectations
Current WU's test 3 K's.
EDIT: WU's now test 6 K's and credit has been doubled.

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
The arguments for AP26 are Kmin Kmax shift. It correlates with the WU name of ap26_Kmin_Kmax_shift_WU iteration. For example, ap26_1603_1605_0_0 is Kmin=1603, Kmax=1605, shift=0, and initial result.

The WU's will progress linearly up to K=10,000,000. Once 10M has been reached, a new shift will be introduced and included with the previous shift. Then a new shift will be introduced every k=7,000,000 afterwards. For example, after K=10M shift0=, K=1 shift=64 will be started. When shift=64 reaches K=7M, shift=128 will be introduced. At this point there will be 3 different types of WU's, shift 0, 64, and 128.

shift=0 will be at K=17M
shift=64 will be at K=7M and
shift=128 will be at K=1

This goes for another K=7M to produce 4 different WU's.

shift=0 will be at K=24M
shift=64 will be at K=14M
shift=128 will be at K=7M and
shift=192 will be at K=1

and so on until an AP26 is found. :)
____________

First impressions:

10-15 minutes on Q9300@2.7GHz, Ubuntu64
320K RAM per WU

Good stuff for impatient crunchers ;)
____________
There are only 10 kinds of people - those who understand binary and those who don't

8-12 minutes on Q6600@3.2GHz Ubuntu64 8.04

Just had a shortie of 5 minutes. So the range is 5-15min on my machine. Where does this range come from - anything to be seen from the WU name?
____________
There are only 10 kinds of people - those who understand binary and those who don't

Just had a shortie of 5 minutes. So the range is 5-15min on my machine. Where does this range come from - anything to be seen from the WU name?

I had a couple of wu's with compute errors as soon as they started and they have done this on more than one pc.

http://www.primegrid.com/workunit.php?wuid=54671223
http://www.primegrid.com/workunit.php?wuid=54671223

All of the k's in each of these wus are divisible by one of the primes in the range 29-59. So there isn't a valid result from these wu's?

I had a couple of wu's with compute errors as soon as they started and they have done this on more than one pc.

http://www.primegrid.com/workunit.php?wuid=54671223
http://www.primegrid.com/workunit.php?wuid=54671223

All of the k's in each of these wus are divisible by one of the primes in the range 29-59, so there isn't a valid results from these wu's.

All of the k's in each of these wus are divisible by one of the primes in the range 29-59, so there isn't a valid results from these wu's.

Currently 13.61 cobblestones are being granted per WU.
____________

I'm happy with that and it'll keep me crunching AP26.
____________

About the introduction message: The app uses Jaroslaw's implementation of his own algorithm, the code I added is mainly to do with adapting the program for use with BOINC and for compiling without GMP.

About the introduction message: The app uses Jaroslaw's implementation of his own algorithm, the code I added is mainly to do with adapting the program for use with BOINC and for compiling without GMP.

I think this WU needs to be deleted...

http://www.primegrid.com/orig/workunit.php?wuid=54671728

____________

35 x 2^3587843+1 is prime!

The WU's that were reported in previous posts as causing errors are those which contain 3 k's divisible by a prime in the range 29-59. They constitute over 0.4% of all WU's, assuming that triples of consecutive k's are grouped to form WU's without any check on the divisibilities.

Also a couple of users on forum BOINC@Poland reported that their computers had problems with receiving new WU's despite a few thousand of WU's available according to the PrimeGrid page.

Can we start counting an AP listed on http://www.primegrid.com/stats_ap26.php as a hit, like we do with primes and factors please?

Especially since this is me! :-)

We have decided that we are not going to count APs as "hits" because of nature of the finds - each workunit actually finds several APs, but they are ignored because they are small, but nevertheless, they are finds. Now, what size is "too small"? That's too hard to decide, so that's the base of our reasoning of NOT to count.
____________

I concur - if there are finds interesting enough to have a stats page for, they are interesting enough to count as a hit. If AP19s and shorter aren't interesting enough to hold stats for, don't count them as a hit either.
____________

The search is only a few weeks old but I was wondering if the results are as expected with the number of work units completed?

So who found the AP25?

Congrats to you!
____________

35 x 2^3587843+1 is prime!

So who found the AP25?

Congrats to you!

I assumed it was the rediscovery but was still pleased to see it's appearance.


____________

35 x 2^3587843+1 is prime!

So we're up to 4 AP24 and a single AP25 - how close are we to hitting untested territory?
____________

The teritory searched in AP24/AP25 search was a bit irregular and also the search program was set up a bit differently so it was almost impossible to skip the teritory already searched. From the point of view of the whole AP26 search, this teritory is very small and taking it into account was not worth messing up the whole search program and the search schedule. Also it would be almost impossible to isolate a reasonable piece of already searched area which could be taken into account in the current search.

From the beginning we were searching both new and old teritories. At the start the old search area (really impossible to isolate precisely due to prgram setup somewhat incompatible with search ranges in the previos search) was probably around 30% of the current search. However the old search teritory is the best one - containing smaller numbers and having larger density of primes and prime progressions - hence by watching the progressions found, one could get a false impression that we were searching mainly what has already been searched.

Currently we are around K=1,000,000.

The completely uncharted teritory starts at K=5,500,000.

Just before we reach it, we will be searching about 10% of the old area and about 90% of new, but with the old area offering a larger density of AP's.

That makes sense - Thanks for the info!
____________

It looks like we have the first new AP24. This should be announced and reported to Jens Kruse Andersen, who is maintaining the list of all known AP24 and AP25 at
http://users.cybercity.dk/~dsl522332/math/aprecords.htm#ap24

Any update on when we might see some record of these on our account pages (e.g., a count of workunits completed, even without "hits" listed)?


____________
141941*2^4299438-1 is prime!

Any update on when we might see some record of these on our account pages (e.g., a count of workunits completed, even without "hits" listed)?

Any update on when we might see some record of these on our account pages (e.g., a count of workunits completed, even without "hits" listed)?

With this last insert of WU's we have reached K=10,000,000 for shift=0. We will now be alternating inserts between shift=0 and shift=64.

shift=0 will progress from K=10,000,000 to 17,000,000
shift=64 will progress from K=1 to 7,000,000

If we reach those limits without finding the AP26, we'll then advance to shift=128.
____________

Excellent progress!

When we find an AP26, I assume we will continue searching for more and hopefully an AP27 will pop out of the woodwork?

____________

It's not a big deal but when you find something from the AP26 search is it viewable somewhere? I just wanted to see what it was.

Have plans calculations on the GPU?

Yes, I hope soon I will release first public version.

that's really nice, do you have some stats about speed gains?

Yes 2 times longer and 2* credit :)

Lennart

When you stated that "... 32 bit has such a huge disadvantage in processing time that we are reviewing whether it will be implemented." were you concerned for legacy systems still using 32-bit, or 32-bit systems in general?

For any k there are infinitely may AP-k - this is Green-Tao theorem (2004).

The particular search program we are using for the AP26 search, assumes progression difference nondivisible by 29. Hence any progression found by the program has every 29th term divisible by 29. In particular any progression of 29 terms has a term divisible by 29, which is not prime except for highly unlikely case, where this term is equal to 29.

For any positive integers n, k there exist AP-(n*k) (arithmetic progression of k*n primes). This progression contains n instances of disjoint AP-k. Hence for any n, k there exist at least n AP-k, namely e.g. those contained in some AP-(n*k).
Since n is arbitrary here, there exist arbitrarily many AP-k.

That's how existence of arbitrarily long progressions implies existence of infinitely many progressions of any fixed length.

Note that for example any AP25 contains two AP24, so AP-k in Tao-Green theorem may be a part of a longer prime arithmetic progression. Green-Tao theorem doesn't say that there exist at least one AP-k, which is not a part of AP-(k+1).

As for 29, any existing AP29, which doesn't start with term 29, must have difference divisible by 29. However, the AP26-search program is constructed in such a way, that it assumes progression difference to be NON-divisible by 29 - this is done for simplicity of the code.

Any arithmetic progression of integers must have exactly one of the following two properties:
* progression difference is divisible by 29
* every 29 consecutive terms include exactly one term divisible by 29

Reading up on the Tao-Green Theorem, it seems to state that there is at least one AP-k for any given k, but from what I read it doesn't explicitly say anything about there being infinitely many. Maybe the Wikipedia article is not quite clear, or is there something else that lets us assume "if there is at least one, there must be infinitely many"?

Also, if it isn't too much trouble, could you elaborate a little more on the AP29 issue? I haven't been able to figure out for myself why any progression of 29 terms must have a term divisible by 29, unless I misread and you were just talking about within the context of our AP26 search program.

Sorry for all the questions; this stuff is just really interesting to me. I just wish I had a better background in math and could figure some of it out by myself.

* progression difference is divisible by 29
* every 29 consecutive terms include exactly one term divisible by 29

For these conditions, you could substitute any number, correct? 29 just happens to be a number used by the search program in a way which makes AP29 "invisible" to it.

Thanks Jarek, I as well understand now about the Ap29 issue, I admit I had to read it twice to fully understand it but it truly is fascinating :)

Edit: As I hit enter on my first post about the ap29 issue you had just hit enter explaining it lol luck of the fast response I guess :) thanks again my friend.
____________


John M. Johnson "Novex"

AP 26 Update

We have finally reached the 3rd shift. Actually, we are about 3M behind on this insertion. With our attention on the Challenge, we went right through the "scheduled" insertion point. Currently we have the following 3 shifts:

shift=0; k<19.91M
shift=64; k<9.98M
shift=128; k<733K

The next several inserts will be from shift=128 until we reach k=3M. Afterwards inserts will rotate through all 3 shifts.
____________

AP 26 Update

We have entered the 5th shift. The status of all 5 shifts are as follows:

shift=0; k<33.11M
shift=64; k<23.73M
shift=128; k<16.14M
shift=192; k<9.13M
shift=256; k<1.10M
____________

AP 26 Update

Success since the last update: AP 26 Found!!! Congratulations to Benoãt Perichon of France.

The project was extended for 7 days to allow those who were on the cusp of their next badge level the chance to achieve it. On 19 April 2010 at 20:00 UTC, the work buffer was no longer refilled.

The queue is slowly making its way down. Currently, there are 10191 outstanding WU's. The project will be officially closed once these WU's are returned and credited.

Good progress is being made on developing another GPU application using ppsieve which can be implemented in the PPS sieve. As for the PS3, currently the only work available at PrimeGrid is in the PSA using PRPNet. For more information, please read the previous links as well as: Servers recommended for my PS3

As for those who wish to continue on their own to seek a 2nd AP26 (or more AP25's and shorter), the following were the limits reached in PrimeGrid's AP26 search.

shift=0; k<43902416
shift=64; k<33973721
shift=128; k<25165464
shift=192; k<16288724
shift=256; k<9354514
shift=320; k<2751343

AP26 has been removed from the front page "Available" work section as well as the current projects section. Eventually, this Subproject forum will be moved to the Completed subprojects section.

Thanks again to everyone who helped with this effort. It was an excellent success.
____________

Might be nice to remove it from the preferences then so nobody selects it as their single project.

If all work is completed, the mark of supported platforms, PS3 and Solaris, is off from PrimeGrid main page?

109.
____________

AP 26 Update

The last remaining tasks have been completed, returned, and validated. There are currently 0 outstanding tasks! Congratulations everyone!!!

Over the next few days, this project will be closed up and the thread will be moved to the "Completed subprojects" section.

[EDIT]
3807 outstanding tasks as of 2010-04-27 01:56:09 UTC
2081 outstanding tasks as of 2010-04-27 21:52:52 UTC
1482 outstanding tasks as of 2010-04-28 18:22:44 UTC
847 outstanding tasks as of 2010-05-01 04:28:16 UTC
655 outstanding tasks as of 2010-05-02 12:43:24 UTC
390 outstanding tasks as of 2010-05-03 14:19:19 UTC
109 outstanding tasks as of 2010-05-07 16:27:46 UTC
48 outstanding tasks as of 2010-05-10 03:25:50 UTC
9 outstanding tasks as of 2010-05-12 14:24:01 UTC
0 outstanding tasks as of 2010-05-13 22:08:00 UTC
____________

I feel the same way. I was just a little too late.
____________