Problems & Puzzles: Puzzles

Puzzle 113. Provable primes in Arithmetic progression

Three weeks ago I was prone to erase from the hard disk of my PC 347 primes of the form k*2^45454+1 that I got using Proth.exe and accumulated during almost 3 years (December 97 to July 2000) trying to get a record for the Twin primes category (I suspended the search a few months ago, no far from the day that Indlekofer et alia announced the two twin records with n = 60000)

But in those very moments I had the sudden (desperate?) idea of using them trying to get a triplet in A.P., that is to say to find 3 k-values of them in A.P.

After analyzing the 347 k-values with the help of a small code made in Ubasic, I got the sad result that no one of the 347*346*345/3! triplets formed with the  347-k values fitted in an A. P. relation.

Then I wrote (18/10/2000) to Chris Nash the following:

"...This week I analyzed these 347 k values and unfortunately no three of them are in A.P. What else can I do with these 347 k values? Well another chance of getting something interesting is that one of these k values is such that k*2^45455-1 is prime. If that happens with only one k value, let's say K, then as for sure you know then 3, K*2^45454+1 & K*2^45455-1 is a triplet of primes in A.P...."

Chris responded the same day:

"...Note that for a number of this size, though the probability of finding an odd prime of this size is about 1 in 15000...I am sure you can use Proth to test those... in File mode, Proth can take values of k and n from a file, and then you can switch to k.2^45455-1 mode. But since 347/15000 is not such good odds, perhaps we can somehow improve our chances!... There are other forms, for instance:

A.2^m+1
(A.2^m+B.2^n)/2+1
B.2^n+1

can all be proven if n>m/3.So you could take your 347 primes, and 50 other smaller Proth primes, and test that middle term with a good change of success"

Against the odds I made the corresponding search for the k*2^45455 model and as a matter of fact I got noting, again...

So we decided to test the model proposed by Nash using certain quantity of the primes published in the Caldwell's database but trying to beat the current 3-AP record by Yves Gallot (this means that we should use some primes larger than the 357 of mine) and IF we succeeded we agreed to make a puzzle (this is that puzzle!) around this subject encouraging other people to follow the experience/method/tools and improve them, of course!

Written by Chris Nash, here is the complete & rest of the story of the search and the arisen questions:

***

"...I analyzed 20 files and the record became with the 21 one. Using two PC's (300 & 400 Mhz) I used the Friday, Saturday & Sunday; the Monday (October 30) morning it was done!..." said Carlos Rivera, after discovering a new record arithmetic progression of primes.

Previously CR had asked Chris Nash what he could possibly do with 347 Proth primes discovered during an extended twin prime search, but now too small to enter the database at http://www.utm.edu/research/primes 

The previous arithmetic progression record was discovered by Arlin Anderson, using the following method. Suppose two primes k1.2^n+1 and k2.2^n+1 are known. Write k=(k1+k2)/2, then k.2^n+1 would complete an arithmetic progression and may be tested for primality. After trying enough pairs, Arlin was successful, but his value of k was even, and unknown to him, the third entry was already in the database in the form with k odd and a different power of n. (Nevertheless, he is credited at http://www.utm.edu/research/primes/lists/top20/ArithmeticProg2.html with the discovery that the three primes were in arithmetic progression).

CN suggested the following method. Take two large sets of primes X and Y. Then for every pair, one prime x from X, and one prime y from Y, test (x+y)/2. This not only provides a lot of possibilities, but if the sets X and Y are sets of Proth primes k.2^n+1, even with different values of n, such primes are provable by classical methods. It is only necessary for the smallest value of n to be a little more than 1/3 the larger.

CR provided the 347 primes in set X, and CN chose the set Y to be those Proth primes with over 20,000 digits. For each member of Y, CN generated a file with 347 numbers to test. CR used PrimeForm/GW to test the numbers for probable primality, and PrimeForm for Windows to prove the result. The new record is 

largest:
24094785*2^67334+1 (20277 digits), previously discovered by Michael Hannigan. (BTW, this - the largest - is the only prime of the triplet that is shown in the Caldwell's page corresponding to these kind of records, according to his rules)

smallest:
272238423*2^45454+1 (13692 digits), from Carlos' list.

and the new prime as middle term:
(24094785*2^21880+272238423)*2^45453 + 1 (20277 digits)

Together they form an arithmetic progression with common difference (24094785*2^21880-272238423)*2^45453 + 1

Questions:

1) Using this method, can you find (and prove!) a new, higher, arithmetic progression record? It seems since our search did not take very long, this should not be difficult.

2) Is there a better method, that will produce larger A.P.'s, or discover new A.P.'s more quickly? Of course, the records discovered *must* be provable!

3) What about arithmetic progressions of length greater than 3?

HINTS
____________
PrimeForm for Windows can test arbitrary expressions for probable primality, and prove primes where 33% of N-1 or N+1 is factored.

PrimeForm/GW is a faster version of PrimeForm (but runs in a command prompt only) and is currently limited to probable prime testing.

Solution

 
Records   |  Conjectures  |  Problems  |  Puzzles