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:
Chris responded the same day:
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:
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
and the new prime as middle term:
Together they form an arithmetic progression with common difference (24094785*2^21880-272238423)*2^45453 + 1
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?
PrimeForm/GW is a faster version of PrimeForm (but runs in a command prompt only) and is currently limited to probable prime testing.