2 7

**167** 29

(this and the same solution was gotten by **Giovanni
& Faride**)

41 **359** 317

23 2 7

233 167 29

89 1847 653 503

167 2 23 173

317 359 41 983

4583 **5417** 59 617

**Giovanni** sent the following solutions:

29 167 233

7 2 23

317 **359** 41

487 1277 2087 **2269**

89 167 29 647

1847 2 7 1289

857 439 137 1627 (sum=13120)

461 439 137 647

23 2 7 29

761 839 317 167

263 **4637** 1447 857 (larger maximal prime but smaller sum=11033 )

227 2909 1447 **6653** 743

29 7 317 4583 1193

167 2 359 5417 1307

233 23 41 59 137

2903 2281 3803 1097 347

347 1097 3803 **16361** 1063 10601

137 59 41 23 233 6823

1307 5417 359 2 167 7577

1193 4583 317 7 29 8807

743 6653 1447 2909 227 797

157 10247 4637 7907 10589 647

**Faride** found the following solutions:

137 7 29

**439** 2 167

461 23 233

887 137 7 29

2477 439 2 167

5623 461 23 233

**10253** 983 41 443

887 137 7 29 647

2477 439 2 167 509

5623 461 23 233 4391

10253 983 41 443 971753

35543 1321 24923 20873 829211

**Enoch** sent the following solution

7 - 2 - 23 - 13 - 131

29 - 167 - 233 - 2903 - 4493

547 - 8669 - 8231 - 43753 - 546071

1217 - 380707 - **10116893** - 1730471 - 893929

227 - 172829 - 839207 - 1581929 - 2769467

***

Evidently Giovanni got the more and smaller solutions.
On request he describes his method:

My approach is almost trivial. The program start
with N (the side of the square) and MAXP (the max prime to use).

Then it build a matrix Q[p,q] which contains 1 if
p+q is a square and 0 otherwise (this is used to speed up tests). It also
build a list (for every prime P up to #MAXP) of the numbers which added to
P gives a square. I order the N*N cells to be filled and I recorded the
neighbors of every cell, only when the index of the neighbor is larger.

For example, given the problem 3x3 I number the
cells:

0 1 2

3 4 5

6 7 8

and the neighbors are:

0 = NONE

1 = 0

2 = 1

3 = 0

4 = 1 3

5 = 4 2

6 = 3

7 = 4 6

8 = 5 7

This is the order in which I'll try to fill the
cells. Different orderings can produce faster algorithms. I maintain an
array which tells me which prime numbers I've already used.

Then I fill cell 0 with every number up to MAXP and
every time I call the recursive procedure Fill from cell 1. Fill(X) if
cell X is equal to N*N it means I've filled all and I have a solution.
otherwise:

I consider a neighbor of cell X, which contains a
number p. Now I use the list of numbers which added to p gives a square.

For each such number q I try to see if

1) is free,

2) added to every neighbor of X gives a square.

if the conditions are satisfied I put q on the
current solution on cell X, I record that q is used and I call the
procedure Fill on cell X+1. On return from Fill, I free q and try another
q. The there are other details, like to decrease MAXP every time I found a
better solution, or to impose that the first two cells have numbers in
decreasing order (to reduce the number of symmetric solutions discovered).

Then I trace the solutions in order to find the
minimal one. All in all, it took less than an hour of programming and
about

1 second for N = 4

12 seconds for N = 5 and

34 minutes for N = 6.

Other variants are possible, for example one can
substitute the "square sum condition" with other conditions. (I tried
palindromic sum and triangular sum), and only few lines of the program
have to be changed (the construction of precomputed arrays).

The "cube sum" condition is quite hard (few pairs
give cube sum. Even 2x2 is not so easy:

53 26947

11 5821

and the 3x3 should be quite large indeed...

***

Now I want to propose this follow-up to this puzzle:

**Find a magic square with the
asked property in this puzzle.**

***

**J. C. Rosa and Luke Pebody** found impossible the
above follow-up. Why? Both gave basically the same proof:

If n is odd , a nxn magic square with the asked
property in this puzzle can not exist.

Proof : If nxn is a magic square composed of prime
numbers then every prime is an odd prime. Even more if P and P' are two
adjacent (not diagonal) primes we must have: P+P'=a^2. P and P' are odd
numbers therefore: P+P'=0 mod 4, from where:

P= - P' mod 4 (1)

Let S the magic sum. If n is an odd number we have
S=P mod 4 (P is any prime in a row and in an odd column). Let P' the
prime below (or above ) P in the same column than P. Also we have S=P' mod
4 Thus we have:

P=P' mod 4 (2)

But it is impossible to have simultaneously (1) and
(2).

It seems that **J. C. Rosa** will try to get a 4x4
solution as the asked...

***