Problems & Puzzles: Puzzles

Puzzle 681 Stanley Antimagic Squares Natalia Makarova sent the following difficult puzzle: An Antimagic* Stanley Square of d rows and d columns has an index S if any set of d elements of the square sum to S, supposed that for each set no two of such elements share row and column. See p. 618 of Stanley's Book pdf available in the web. Please notice that the quantity of sets (sums) is d! In this puzzle we will add the following two conditions: 1) The elements of the square must be distinct prime numbers 2) The index (sum) S must be minimal. Example: d=3; quantity of sets (sums) = 3!; S=53 (minimal) 3 11 17 5 13 19 23 31 37 because: 3+13+37=53 3+19+31=53 5+11+37=53 5+31+17=53 23+13+17=53 23+11+19=53 Natalia Makarova has sent the minimal index S solutions for d=2, 3, 4, 5 & 6. d=2; quantity of sets (sums) = 2!; S=16 (minimal) 3 5 11 13  d=4; quantity of sets (sums) = 4!; S=150 (minimal) 5 43 19 13 23 61 37 31 3 41 17 11 59 97 73 67  d=5; quantity of sets (sums) = 5!; S=395 (minimal, author V. Pavlovsky) 5 7 17 31 131 11 13 23 37 137 41 43 53 67 167 71 73 83 97 197 101 103 113 127 227 d=6; quantity of sets (sums) = 6! S=774 (minimal, Natalia Makarova) 13 19 43 109 139 223 31 37 61 127 157 241 41 47 71 137 167 251 53 59 83 149 179 263 67 73 97 163 193 277 101 107 131 197 227 311 See: http://oeis.org/A210710 She has also found solutions for d= 7, 8, 9, 10 & 11, but she can not guarantee that she got the minimal index for them: (d, S) = (7, 1597), (8,5000), (9, 9783), (10,44998), (11,198341) Q. Can you send you better solutions for d=7, 8, 9, 10 & 11? ______ * Please notice that this kind of "Antimagic" squares are totally distinct to the other "Antimagic" squares we have studied in our previous Puzzles 263 & 264. See also http://mathworld.wolfram.com/AntimagicSquare.html

---

Contributions came from Natalia Makarova, J. Wroblewski & J. K. Andersen.

***

Natalia sent the algebraic solutions for d=5 to 9, useful for those who want to work on this puzzle.

Please notice that if:

v= the quantity of total variables=d^2+1
V=the quantity of independent variables=2d-1
e=the quantity of dependent variables=the quantity of independent equations=
=v-V=d^2-2d+2

d	v	V	e
5	26	9	17
6	37	11	26
7	50	13	37
8	65	15	50
9	82	17	65
10	101	19	82

And the equations sent by Natalia are:

For d=5, X26=S, e=17

x1=-x10-x15-x20-x22-x23-x24+2 x25+x26
x2=-x10-x15-x20-x21-x23-x24+2 x25+x26
x3=-x10-x15-x20-x21-x22-x24+2 x25+x26
x4=-x10-x15-x20-x21-x22-x23+2 x25+x26
x5=-x10-x15-x20-x21-x22-x23-x24+3 x25+x26
x6=x10+x21-x25
x7=x10+x22-x25
x8=x10+x23-x25
x9=x10+x24-x25
x11=x15+x21-x25
x12=x15+x22-x25
x13=x15+x23-x25
x14=x15+x24-x25
x16=x20+x21-x25
x17=x20+x22-x25
x18=x20+x23-x25
x19=x20+x24-x25

For d=6, X37=S, e=26

x1 = - x12 - x18 - x24 - x30 - x32 - x33 - x34 - x35 + 3 x36 + x37
x2 = - x12 - x18 - x24 - x30 - x31 - x33 - x34 - x35 + 3 x36 + x37
x3 = - x12 - x18 - x24 - x30 - x31 - x32 - x34 - x35 + 3 x36 + x37
x4 = - x12 - x18 - x24 - x30 - x31 - x32 - x33 - x35 + 3 x36 + x37
x5 = - x12 - x18 - x24 - x30 - x31 - x32 - x33 - x34 + 3 x36 + x37
x6 = - x12 - x18 - x24 - x30 - x31 - x32 - x33 - x34 - x35 + 4 x36 + x37
x7 = x12 + x31 - x36
x8 = x12 + x32 - x36
x9 = x12 + x33 - x36
x10 = x12 + x34 - x36
x11 = x12 + x35 - x36
x13 = x18 + x31 - x36
x14 = x18 + x32 - x36
x15 = x18 + x33 - x36
x16 = x18 + x34 - x36
x17 = x18 + x35 - x36
x19 = x24 + x31 - x36
x20 = x24 + x32 - x36
x21 = x24 + x33 - x36
x22 = x24 + x34 - x36
x23 = x24 + x35 - x36
x25 = x30 + x31 - x36
x26 = x30 + x32 - x36
x27 = x30 + x33 - x36
x28 = x30 + x34 - x36
x29 = x30 + x35 - x36

d=7, X50=S, e=37

x1 = - x14 - x21 - x28 - x35 - x42 - x44 - x45 - x46 - x47 - x48 + 4 x49 + x50
x2 = - x14 - x21 - x28 - x35 - x42 - x43 - x45 - x46 - x47 - x48 + 4 x49 + x50
x3 = - x14 - x21 - x28 - x35 - x42 - x43 - x44 - x46 - x47 - x48 + 4 x49 + x50
x4 = - x14 - x21 - x28 - x35 - x42 - x43 - x44 - x45 - x47 - x48 + 4 x49 + x50
x5 = - x14 - x21 - x28 - x35 - x42 - x43 - x44 - x45 - x46 - x48 + 4 x49 + x50
x6 = - x14 - x21 - x28 - x35 - x42 - x43 - x44 - x45 - x46 - x47 + 4 x49 + x50
x7 = - x14 - x21 - x28 - x35 - x42 - x43 - x44 - x45 - x46 - x47 - x48 + 5 x49 + x50
x8 = x14 + x43 - x49
x9 = x14 + x44 - x49
x10 = x14 + x45 - x49
x11 = x14 + x46 - x49
x12 = x14 + x47 - x49
x13 = x14 + x48 - x49
x15 = x21 + x43 - x49
x16 = x21 + x44 - x49
x17 = x21 + x45 - x49
x18 = x21 + x46 - x49
x19 = x21 + x47 - x49
x20 = x21 + x48 - x49
x22 = x28 + x43 - x49
x23 = x28 + x44 - x49
x24 = x28 + x45 - x49
x25 = x28 + x46 - x49
x26 = x28 + x47 - x49
x27 = x28 + x48 - x49
x29 = x35 + x43 - x49
x30 = x35 + x44 - x49
x31 = x35 + x45 - x49
x32 = x35 + x46 - x49
x33 = x35 + x47 - x49
x34 = x35 + x48 - x49
x36 = x42 + x43 - x49
x37 = x42 + x44 - x49
x38 = x42 + x45 - x49
x39 = x42 + x46 - x49
x40 = x42 + x47 - x49
x41 = x42 + x48 - x49

d=8, X65=S, e=50

x1 = - x16 - x24 - x32 - x40 - x48 - x56 - x58 - x59 - x60 - x61 - x62 - x63 + 5 x64 + x65
x2 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x59 - x60 - x61 - x62 - x63 + 5 x64 + x65
x3 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x58 - x60 - x61 - x62 - x63 + 5 x64 + x65
x4 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x58 - x59 - x61 - x62 - x63 + 5 x64 + x65
x5 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x58 - x59 - x60 - x62 - x63 + 5 x64 + x65
x6 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x58 - x59 - x60 - x61 - x63 + 5 x64 + x65
x7 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x58 - x59 - x60 - x61 - x62 + 5 x64 + x65
x8 = - x16 - x24 - x32 - x40 - x48 - x56 - x57 - x58 - x59 - x60 - x61 - x62 - x63 + 6 x64 + x65
x9 = x16 + x57 - x64
x10 = x16 + x58 - x64
x11 = x16 + x59 - x64
x12 = x16 + x60 - x64
x13 = x16 + x61 - x64
x14 = x16 + x62 - x64
x15 = x16 + x63 - x64
x17 = x24 + x57 - x64
x18 = x24 + x58 - x64
x19 = x24 + x59 - x64
x20 = x24 + x60 - x64
x21 = x24 + x61 - x64
x22 = x24 + x62 - x64
x23 = x24 + x63 - x64
x25 = x32 + x57 - x64
x26 = x32 + x58 - x64
x27 = x32 + x59 - x64
x28 = x32 + x60 - x64
x29 = x32 + x61 - x64
x30 = x32 + x62 - x64
x31 = x32 + x63 - x64
x33 = x40 + x57 - x64
x34 = x40 + x58 - x64
x35 = x40 + x59 - x64
x36 = x40 + x60 - x64
x37 = x40 + x61 - x64
x38 = x40 + x62 - x64
x39 = x40 + x63 - x64
x41 = x48 + x57 - x64
x42 = x48 + x58 - x64
x43 = x48 + x59 - x64
x44 = x48 + x60 - x64
x45 = x48 + x61 - x64
x46 = x48 + x62 - x64
x47 = x48 + x63 - x64
x49 = x56 + x57 - x64
x50 = x56 + x58 - x64
x51 = x56 + x59 - x64
x52 = x56 + x60 - x64
x53 = x56 + x61 - x64
x54 = x56 + x62 - x64
x55 = x56 + x63 - x64

d=9, X82=S, e=65

x1 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x74 - x75 - x76 - x77 - x78 - x79 - x80 + 6 x81 + x82
x2 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x75 - x76 - x77 - x78 - x79 - x80 + 6 x81 + x82
x3 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x76 - x77 - x78 - x79 - x80 + 6 x81 + x82
x4 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x75 - x77 - x78 - x79 - x80 + 6 x81 + x82
x5 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x75 - x76 - x78 - x79 - x80 + 6 x81 + x82
x6 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x75 - x76 - x77 - x79 - x80 + 6 x81 + x82
x7 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x75 - x76 - x77 - x78 - x80 + 6 x81 + x82
x8 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x75 - x76 - x77 - x78 - x79 + 6 x81 + x82
x9 = - x18 - x27 - x36 - x45 - x54 - x63 - x72 - x73 - x74 - x75 - x76 - x77 - x78 - x79 - x80 + 7 x81 + x82
x10 = x18 + x73 - x81
x11 = x18 + x74 - x81
x12 = x18 + x75 - x81
x13 = x18 + x76 - x81
x14 = x18 + x77 - x81
x15 = x18 + x78 - x81
x16 = x18 + x79 - x81
x17 = x18 + x80 - x81
x19 = x27 + x73 - x81
x20 = x27 + x74 - x81
x21 = x27 + x75 - x81
x22 = x27 + x76 - x81
x23 = x27 + x77 - x81
x24 = x27 + x78 - x81
x25 = x27 + x79 - x81
x26 = x27 + x80 - x81
x28 = x36 + x73 - x81
x29 = x36 + x74 - x81
x30 = x36 + x75 - x81
x31 = x36 + x76 - x81
x32 = x36 + x77 - x81
x33 = x36 + x78 - x81
x34 = x36 + x79 - x81
x35 = x36 + x80 - x81
x37 = x45 + x73 - x81
x38 = x45 + x74 - x81
x39 = x45 + x75 - x81
x40 = x45 + x76 - x81
x41 = x45 + x77 - x81
x42 = x45 + x78 - x81
x43 = x45 + x79 - x81
x44 = x45 + x80 - x81
x46 = x54 + x73 - x81
x47 = x54 + x74 - x81
x48 = x54 + x75 - x81
x49 = x54 + x76 - x81
x50 = x54 + x77 - x81
x51 = x54 + x78 - x81
x52 = x54 + x79 - x81
x53 = x54 + x80 - x81
x55 = x63 + x73 - x81
x56 = x63 + x74 - x81
x57 = x63 + x75 - x81
x58 = x63 + x76 - x81
x59 = x63 + x77 - x81
x60 = x63 + x78 - x81
x61 = x63 + x79 - x81
x62 = x63 + x80 - x81
x64 = x72 + x73 - x81
x65 = x72 + x74 - x81
x66 = x72 + x75 - x81
x67 = x72 + x76 - x81
x68 = x72 + x77 - x81
x69 = x72 + x78 - x81
x70 = x72 + x79 - x81
x71 = x72 + x80 - x81

***

J. Wroblewski sent a solution for d=20, not minimal, based on primes in AP.

Regarding puzzle 681, where we ignore the requirement of the
minimality of the index, it can be reformulated as finding d disjoint
configurations of d primes each. By a configuration I mean a set of d
primes with predefined differences, i.e. p, p+r2, p+r3, ..., p+rd with
r2,...,rd fixed.

In my old post (Dec 1, 2008):
http://tech.groups.yahoo.com/group/primenumbers/message/19733
you can find 22 prime arithmetic progressions of length at least 20
with the common difference of 43#.

Known AP20+ with difference 43#
First terms of progressions are given

1 9372688136871853
2 11735227242889999
3 76240762416222539 AP21
4 93490858594661729 AP22 !!!!!
5 114146343711853721
6 135651360264848653
7 195625258610971297 AP21
8 202860934798777373
9 223789213311833843
10 224957853888083671 AP21
11 251672116721153519
12 325435306756257757
13 333012166298058323
14 338275337330536643
15 381336957506808803
16 485191591159166291
17 493052729074838717 AP21
18 630202728690264047
19 1006137974832655813
20 1296572696606684143
21 1351906725737537399 AP22 !!!!!
22 1376274082220856487

Any matrix obtained by taking 20 such AP20's [each in one row] is an
antimagic square of primes, hence we see an example for d=20.
Certainly there is no reason to believe that the index is anywhere
near minimal.

I believe that 20 is pretty close to what one could hope for, when
searching for an example of an antimagic square of primes with as
large size d as possible. Quite likely, with a big programming and
computational effort, one could hope for a slightly larger d, taking a
more frequent configuration of primes instead an arithmetic
progression, but I strongly believe that finding an example for d=30
or perhaps even d=25 will be out of reach in our lifetime.

I conjecture that examples exist for each d, since I strongly believe
that any configuration of primes, not forbidden by simple divisibility
arguments, appears infinitely many times.

Unfortunately, currently I do not have enough time to investigate the
problem, neither the question of finding minimal index for small d,
nor trying to push d with a known example a little higher, although I
find the last question extremely interesting - I am always being
excited by various configurations containing as many primes as
possible.

***

Andersen wrote:

Many of the below squares are shown in full in the attached file.
Let's represent a d x d Stanley antimagic square as
M = b + c, where b and c are d-tuples, and we define their addition as
M_ij = b_i + c_j, for i, j = 1..d.
If we choose c_1 = 0 then the representation is unique with b being
the left column, and c being the differences to the other columns.
I have confirmed the minimal index for d = 2 to 6 given in the puzzle.
(7,1597) is also minimal. In my notation:
(2,16): (3,11) + (0,2)
(3,53): (3,5,23) + (0,8,14)
(4,150): (5,23,3,59) + (0,38,14,8)
(5,395): (5,11,41,71,101) + (0,2,12,26,126)
(6,774): (13,31,41,53,67,101) + (0,6,30,96,126,210)
(7,1597): (7,43,79,97,163,307,379) + (0,4,10,30,60,184,234)

Natalia's d = 8 to 11 are not minimal. The minimal index for 8 to 10:
(8,3036): (13,31,37,43,127,163,241,421) + (0,10,66,70,226,336,556,696)
(9,5837): (11,23,47,131,173,557,593,641,1607)
         + (0,6,20,50,60,216,270,326,1106)
(10,10080): (11,23,47,131,557,593,641,971,1103,1607)
           + (0,6,20,60,216,326,456,476,1190,1646)

This is probably minimal for 11 but has not been fully proven:
(11,18191): (23,89,163,179,331,569,613,859,1153,2063,2531)
           + (0,18,48,78,270,378,1128,1140,1698,2220,2640)

A210710 becomes:
16, 53, 150, 395, 774, 1597, 3036, 5837, 10080, and probably 18191.
So far it appears to roughly double each time.

Below is the smallest index I found in limited searches for d = 12 to 16.
12 is probably not minimal. The rest are highly unlikely to be minimal.
(12,58610): (0,30,360,750,1140,1980,2400,2730,3570,4440,4710,5880)
           + (23,73,233,479,569,947,1627,1949,2417,4721,8263,9319)

(13,37058897):
(0,30030,150150,180180,210210,570570,600600,690690,720720,750750,1081080,1171170,1591590)
              +
(147863,180097,467507,624313,739549,833659,1091807,1507007,1763477,2121241,4115263,4961741,10757633)

(14,902199784):
(0,510510,1021020,1531530,2552550,3063060,5615610,6636630,7147140,10720710,12762750,17357340,19399380,48498450)
               +
(1389667,3950563,8231567,8785313,13775719,26105347,27310417,29388449,43374139,56734339,76406807,127046653,138183217,204700907)

(15,8435439410583):
(65545446539,69328695041,133981508819,192952370887,434565237347,443008464007,519191999257,550008525769,619619421997,667351013311,701564136599,718736048143,832415530801,892395405667,915457817249)
                   + c, where c_i = (i-1)*29# for i = 1..15

(16,105154464112806):
(156880881679,331918828097,1226459069699,1443600858199,2013788383601,2445953898757,2454991118639,2777239193789,3779207051509,6074125108229,6529427542871,6973712218169,7303731078629,11825169388163,12768198698287,12982801978889)
                     + c, where c_i = (i-1)*31# for i = 1..16

d=15 consists of the first 15 non-overlapping AP15 (15 primes in
arithmetic progression) with common difference 29#.
d=16 is the first 16 non-overlapping AP16 with difference 31#.

In 2006-08 Jaroslaw Wroblewski computed many AP19 and AP20 with
difference 29#, shown at
http://users.cybercity.dk/~dsl522332/math/simultprime.htm#history19 and
posts linked there. 19 of them can be used to make this:
(19,141348217827994408989):
(206063865762371,19645711679859961,21167397384723757,501714771980131771,843882398917750139,1328375096905084031,1464072733127278531,2357208768504754823,5143741939709191337,5466691893658775639,6619756800771371627,8463643902010505569,11512568504244030089,11794878875045456989,12167225693277514633,14275160661224928539,17196286091474921689,19316011345882272017,22855978072012553147)
                           + c, where c_i = (i-1)*29# for i = 1..19


http://dxdy.ru/topic58862.html (in Russian) shows that Natalia is also
interested in squares of Smith numbers. The squares with minimal index for
2 to 6 are shown at http://dxdy.ru/topic58862-75.html. In my notation:
(2,143): (22,85) + (0,36)
(3,669): (22,85,346) + (0,36,180)
(4,2088): (85,346,526,654) + (0,9,36,432)
(5,8318): (58,202,454,1858,3802) + (0,63,324,504,1053)
(6,30885): (319,535,1255,3595,4279,13639) + (0,27,1323,1359,1647,2907)

It appears from a Google translation that (6,30885) wasn't known to be
minimal. The minimal d=7 for Smith numbers is
(7,87643): (454,1642,2038,5674,5935,20362,24214)
           + (0,180,1404,2160,3600,3960,16020)

The smallest d=8 I found is
(8,264200): (778,2038,4918,18274,19498,22054,42754,45238)
           + (0,180,2268,4464,7740,16308,22464,55224)
I don't know whether it's minimal.

...

Ben Green and Terence Tao proved in 2004 that the primes contain arbitrarily
long arithmetic progressions. An arithmetic progression of at least d^2 primes
can be split into d arithmetic progressions of d primes with the same common
difference. This means that infinitely many antimagic squares of primes exist
for any d. Known AP25 and AP26 at
http://users.cybercity.dk/~dsl522332/math/aprecords.htm#ap24 can give d=5,
but it is a hopelessly inefficient method to actually search for large
antimagic squares.

***

One day after (30/3/13) Natalia added:

I found a square Stanley order d = 13
(see article http://www.natalimak1.narod.ru/pannetr6.htm):

(13,5441577)

I'm not sure of the minimal of the index.

I want to offer a universal formula square Stanley.
Square Stanley will be denoted as a square matrix A (i, j), i, j = 1, 2, 3, ..., d.
Index square Stanley denoted S.

Then the independent variables:
A (1,1), A (1,2), A (1,3), ..., A (1, d), A (2,1), A (3,1), A (4,1) , ..., A (d,1).

All dependent elements of the square is given by:

A (i,j) = A (i,j-1) + A (i-1,j) - A (i-1,j-1)     (i, j> 1)

The index of the square S is given by:
S = A (1,1) + A (2,2) + A (3,3) + ... + A (d, d)

I want to thank Andresen for interesting solutions!
 

***

One more day after, J. K. Andersen wrote:

Update:
(11,18191) has been proved minimal for d=11. This means the original puzzle is completely solved.

 

A lower but still not minimal index for d=13:
(13,1394767):
(991,1301,2477,4007,4783,6581,7547,35797,71777,78593,115249,389357,587057)
     + (0,210,2940,3570,4830,5460,5670,7980,8190,9870,10710,12600,17220)

***

On April 5, Andersen wrote again:

An updated file is attached. No errors have been found in the previous version
and you don't have to update if it's non-trivial. The new version just adds
some squares from the below post.
I haven't worked on puzzle 682.


A lower but not minimal index for d=14:
(14, 82315120):
(6983,16069,169177,630043,1415231,1719239,2786681,3626099,4475407,6148661,7303297,10455857,11421167,12351439)
    +
(0,30030,60060,120120,150150,330330,480480,810810,1591590,2072070,2192190,2342340,3873870,5735730)


Instead of the minimal index we could also consider the minimal interval,
i.e. the least possible difference between the smallest and largest
prime in a square.
For d=2 it is a prime quadruplet with difference 8. The first occurrence:
5  7
11 13

For d=3 it is the same square as the minimal index. The difference is 34.

For d=4 the square with minimal index has primes from 3 to 97, giving
difference 94. The minimal difference is 82 but it requires much larger
primes. The first occurrence of such a square is the following pattern
with 4164532312868707261 added to each of the 16 numbers:
0  6 18 30
10 16 28 40
42 48 60 72
52 58 70 82

The second occurrence is 6856521413120052187 added to another pattern:
0 10 42 52
12 22 54 64
24 34 66 76
30 40 72 82

The 16 primes are consecutive for both above occurrences, although
other primes in the interval would have been possible.

For d=5 the square with minimal index has difference 222.
Here is a square with the smaller difference 180:

13 19 43 109 139
 

31 37 61 127 157
 

41 47 71 137 167
 

53 59 83 149 179
 

67 73 97 163 193

 

However, the minimal difference for an admissible pattern is 156,
for example for this pattern:
 0  10  24  40  54
12  22  36  52  66
60  70 84 100 114
96 106 120 136 150
102 112 126 142 156

The k-tuple conjecture predicts infinitely many occurrences but
finding one is infeasible

***