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 ith row and jth 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:
Q1
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.
Q2
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
http://www.sam.math.ethz.ch/~waldvoge/Projects/clprimes05.pdf
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,
15722057448876967802383661}
(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 17pattern. 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*(N1) 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 N1 or N. If a pattern of size N2 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 N1.
Later he added:
After my first mail Wroblewski published 22 AP20 or
longer with the
same common difference 43#:
http://tech.groups.yahoo.com/group/primenumbers/message/19733
This enables 20x20 solutions where a1 to a20 are 20 primes starting
nonoverlapping AP20 with difference 43#, and bi = (i1)*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.
Q3
Consider four nonoverlapping 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.
Q4
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 nonoverlapping 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:
http://www.primenumbers.net/Henri/us/PrimesResUs.htm
http://mersenneforum.org/showthread.php?t=8044
http://mersenneforum.org/showthread.php?t=8049
http://www.primepuzzles.net/puzzles/puzz_407.htm
http://www.dms.umontreal.ca/~andrew/PDF/PrimePatterns.pdf
***
***
