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...
***
