Problems & Puzzles: Problems

Problem 54.  AP22 with the difference 43#

J. Wroblewski sent the following problem:

Each of the following 2x2 and 3x3 squares

3  5
11 13 

5  11 23
13 19 31
41 47 59 

has the following properties:

* The square contains distinct primes.
* Let p(i,j) be the prime in i-th row and j-th column. Then p(i,j) + p(k,l) = p(k,j) + p(i,l) for any i,j,k,l not exceeding the size of the square.

Or equivalently:

The square NxN is generated by nonnegative integers a1,...,aN, b1,...,bN such that the N^2 sums ai+bj give distinct primes.

Q1. Prove that such a square NxN exists for any N.

Q2. Give a numerical example for as large N as you can.

Q3. Construct a cube like that by finding the largest N and nonnegative integers a1,...,aN, b1,...,bN, c1,...,cN such that the N^3 sums ai+bj+ck give distinct primes.

Q4. Find the largest N and nonnegative integers a1,...,aN, b1,...,bN, c1,...,cN, d1,...,dN such that the N^4 sums ai+bj+ck+dl give distinct primes. 

Jarek indicates the origin of this problem:

The motivation for the puzzle is as follows. Recently I have found AP22 with the difference 43#, which was assumed before the search. This was a very lucky discovery. In general I cannot specify a progression difference and then honestly expect to find AP22 with that difference.

Suppose you are free to specify arbitrary pattern of primes to be searched, by giving 0<r2<r3<...<rN and searching for p,p+r2,p+r3,...,p+rN, all prime. How can you prove you selected the pattern honestly before the search, rather than fit the pattern in a few known examples?

If you specify a pattern with 4 terms and find 1000 examples, you could write them in a matrix row by row and then read columns claiming: "See? I can find patterns of length 1000, I just have 4 examples!" 

At the moment I believe that for a pattern of N primes, giving a set of N disjoint numerical examples would constitute sort a proof that the pattern was not completely faked and there is some relatively efficient way of producing numerical examples for that pattern. At least I do not see a way of constructing a square NxN without being able, perhaps with some luck, to find a predefined pattern of N primes. The real question is: what kind of patterns are most convenient for the search? We do know, for example, that arithmetic progressions with a well chosen progression difference are much easier to find than tuplets.

J. K. Andersen wrote:

Ben Green & Terence Tao proved in 2004 that there are arbitrarily
long arithmetic progressions of primes. Any case of N*N primes in
arithmetic progression can fill a NxN square.

The longest known progression is length 25 by Raanan Chermoni &
Jaroslaw Wroblewski: 6171054912832631 + 366384*23#*n, for n = 0..24.
This can fill a 5x5 square. Other methods can give much larger squares.

Here is a copy of my contribution to puzzle 367:

Jörg Waldvogel and Peter Leikauf currently list 77 occurrences of a pattern
with 17 primes in
This gives two sets with 17 and 77 numbers where each sum is a distinct
prime. I used their data in a small search which found an 18th number that gives
a prime sum with 27 of the 77 numbers. This gives sets with 18 and 27 numbers having distinct prime sums.

Set 1: {0, 2, 6, 8, 12, 20, 26, 30, 36, 38, 42, 48, 50, 56, 62, 66, 68, 9126650}

Set 2: {71542018620258822095351, 127372818047327460718001,
472773823866578374260011, 668134176357714775428611,
842902600507150788234521, 1448301799940226082771811,
2638263731291524361295161, 2965402830695807653891631,
4184454523805320162938431, 5188248562214464094307851,
6462943397426544261913571, 6515331587478752597979311,
6732639026163593595722561, 7068848143689559074537581,
7106614823259270051322481, 8394208478031243473535821,
8796828522725933171551961, 8941097330542117721700611,
9867358577329746770637251, 9980642183707047492649901,
10508599120346583663997481, 11836184125186489787548721,
11985312529091443124703011, 12314036812755277924784351,
13114239319848333922324961, 15307029480404445010527191,
(End of copy from puzzle 367)

This enables a 18x18 solution where a1 to a18 can be any 18 numbers
from set 2, and b1 to b18 are the 18 numbers in set 1.

Note that this was based on 77 occurrences of a predefined
pattern of 17 and not 18 primes, followed by an easy final search
for b18 = 9126650. Set 2 has 27 numbers where only 18 are needed,
and 18 could have been reached with significantly less than
77 occurrences of the 17-pattern. The required effort to find a
usable b18 depends on the number of occurrences (and on luck).

This strategy is a partial counter example to the speculation by
Wroblewski. A rectangle of size M*(N-1) with M significantly larger
than N was used to find a NxN square. But I don't see a practical
way to find a NxN square for large N without a predefined pattern of
size either N-1 or N. If a pattern of size N-2 was used with a similar
strategy then an impractical number of occurrences would probably be
needed to reach a NxN square. I think it would be easier to use a
much smaller number of occurrences of a predefined pattern of size N-1.

Later he added:

After my first mail Wroblewski published 22 AP20 or longer with the
same common difference 43#:
This enables 20x20 solutions where a1 to a20 are 20 primes starting
non-overlapping AP20 with difference 43#, and bi = (i-1)*43# for i=1..20.
There are not enough AP20 to find an extension to 21x21 with the method
used earlier to find 18x18 from many occurrences of a pattern with 17 primes.

Consider four non-overlapping cases of 16 primes in arithmetic
progression with the same common difference d:
a1 + d*n, a2 + d*n, a3 + d*n, a4 + n*d, for n = 0..15.
Then there is a solution for N=4 with (b1, b2, b3, b4) = (0, d, 2d, 3d),
and (c1, c2, c3, c4) = (0, 4d, 8d, 12d).

Wroblewski's AP's can for example be used. Or to use own results for a
change, a few years ago Gennady Gusev and I found many AP16 and longer
with d = 17# = 510510.
Four of them start at (a1, a2, a3, a4) =
(259268961766921, 2864061296768713, 6245929920682013, 1027994118833642281).

A 5x5x5 cube looks hard. 5 of Wroblewski's AP20 could be used to get 5x5x4,
but it would have required 5 AP25 with the same common difference to reach
5x5x5 with that approach.

2^4 is easy. For example, let p+n*d for n=0..15 be any AP16.
Then let (a1, a2, b1, b2, c1, c2, d1, d2) = (p, p+8d, 0, 4d, 0, 2d, 0, d).
Finding an AP16 is relatively easy, and there are other much easier ways to
get 2^4. 3^4 looks hard.

N^5 was not requested but 2^5 can be reached with known patterns, for
example from two non-overlapping AP16 with same common difference:
p+d*n and q+d*n, for n = 0..15. Just let
(a1, a2, b1, b2, c1, c2, d1, d2, e1, e2) =
(p, q, 0, 8d, 0, 4d, 0, 2d, 0, d).

A variant of Problem 54 is in Puzzle 407 where each of a1..aN, b1..bN, ...
had to be an arithmetic progression. Some links about this harder variant:



Records   |  Conjectures  |  Problems  |  Puzzles