Problems & Puzzles: Puzzles

Puzzle 120. Primal Squares

A Primal Square (*) is an nxn arrangement of numbers such that every two adjacent - horizontal & vertical, but not diagonal - numbers sum up to a prime number.

Example:

It's easy to verify that there is no solution for n=3 with consecutive numbers.

Question 2. Can you develop an algorithm to find at least one of these kind of solutions for any n>3?

Question 3. Using your own algorithm can you produce the solution for n = 10, 20 & 30

Question 3. Jean Charles Meyrignac asks if an (even) Magic Square can be also a Primal Square. In such a case can you produce & send the first example? 

A Primal Square is said to satisfy the 'full torus condition'  if is prime the sum of every two symmetric (not necessarily adjacent) cells out of the main diagonals. The mentioned symmetry is respect both the horizontal and the vertical symmetry axis of the square. Obviously the full torus condition can not be satisfied by odd nxn squares.

The 4x4 example sent by Jean-Charles is a Primal Square but does not satisfy the full torus condition because none of the following: 4+5, 7+14, 2+13, 11+16 is prime (of course, is enough only one failure to spoil the full torus condition). 

Question 4. Can you find a Primal Square that satisfy the full torus condition for n = 4, 6, 8 & 10?
_______
Note: According to Jean-Charles Meyrignac, these squares were first studied by Fred Schuh and made popular by the well known French puzzler reporter Pierre Berloquin.

Solution

Jud McCranie has solved the question 1 (23/12/2000):

"...for any 9 consecutive numbers to fill into a 3x3, you must have 5 even numbers and 4 odd ones, or 4 even numbers and 5 odd numbers. They must alternate odd/even in the square. The center cell plus each of the four cells touching it sum to four consecutive odd numbers, but one of those must be divisible by 3, so it can't be prime, unless it is 3. But if one of them is 3, those four numbers must be 3, 5, 7, and 9, and 9 isn't prime."

He has also sent a solution for the case 10x10:

His method "...is a brute force one - start filling in the first row, fill in a number that forms a prime when summed to the number to the left of it and the number above it (if they exist), and proceed. If you get to a location that you can't fill, back up and try another number.". His largest primal square sent is now 13x13.

***

I (C.R.) have gotten a solution to the 20x20 case with a method that (I think) should be easily improved in order to get solutions for any n value.

This is the method:

1. Use the value n^2 in the cell north-east.

2. Assign all the other values to each cell as the largest primal-valid & non-used number, proceeding by rows from up to down, and by columns from left to right.

3. If the complete assignation to the whole matrix is not possible then - while possible - decrease by one the value for the north-east cell and go to step 2; or halt when there are no more valid values for this cell.

Using the above procedure I got this solution for n=20:

This simple & mechanical procedure is successful without any other refinement for n = 7(39), 8(62), 13(111), 16(238), 17(165), 19(65), 20(226), 21(237), ... In parentheses is the north-east cell value (the largest or first in descending order) for the corresponding nxn square.

I guess that with a light refinement this strategy may work out solutions for all n values.

***
One day after (25/12/2000)I got the following solutions: 30(492), 40 (1336) . In order to get these examples my code used 37 minutes & 1hr.37minutes, respectively, running in a 400 Mhz PC.

***

Paul Jobling produced (29/12/2000) his own code and has sent solutions for the 45x45, 50x50, 100x100 & 150x150 primal square cases. If anybody wants the solutions I can send them on request. Regarding his method, he wrote:

My program works as follows. The order is to go across a line, then down a column. For example, for a 6x6 it would do them in the following order:

 

 1  2  3  4  5  6

 7 12 13 14 15 16

 8 17 21 22 23 24

 9 18 25 28 29 30

10 19 26 31 33 34

11 20 27 32 35 36

 

Note that this does not matter so much for simple squares, but when searching for one which has the full torus property, this allows you to check the torus conditions sooner.

 

I work from n^2 downwards, and place the largest unused value in each cell in turn (in the order outlined above). I then check that the number is valid by checking the sum with the number on the left and the number above. If either of these sums is not prime I decrement the number and test again. If I get to 0, I backtrack to the previously filled in square and decrement its value (in fact, rather than decrementing I subtract two, as the following paragraph will make clear).

 

The program only works for even values of n. To speed up the search I impose the following conditions: that the top left contains an even number, so the top row is even, odd, even, etc; the second row is odd, even, odd, etc; etc. Due to the symmetries I also constrain that the cell to the right of the top left must contain a higher value than the cell underneath the top left - this halves the search time.

 

My program can generate about 1 million partial valid positions per second on this 500 MHz PIII (where 'partial valid' means that all of the numbers that have been placed in the cells so far match the primality criteria with their neighbours). The inner loop, which find partial valid positions, is written in assembler. Outside this inner loop is just some code which writes out the current position to the screen every 2^20 iterations, and sees if a solution has been found and writes it out to a file if it has.

 

The main speed up is obtained by using pre-initialised arrays wherever possible - for example, the primality check is just a lookup into an array. This makes the assembly inner search loop just 35 instructions long.

***

He also says that no magical & primal square 4x4 was found.

***

Regarding the "full torus condition" definition he did it the following way, on my request:

"Each number in a cell is a distance y from an edge. The sum of this number with the number at the distance y in from the opposite edge must also be prime. Note that these are all four edges. For example, in the 8x8 square

 

  .  .  .  .  .  .  .  .

  .  .  a  .  .  b  .  .

  .  .  .  .  .  .  .  .

  .  .  .  .  .  .  .  .

  .  .  .  .  .  .  .  .

  .  .  .  .  .  .  .  .

  .  .  c  .  .  d  .  .

  .  .  .  .  .  .  .  .

 

a+b must be prime, as must a+c, b+d, and c+d."

 

***

This is an example of an 8x8 primal square that I (C.R.) have produced with a very primitive code mainly & just  to illustrate the full torus condition, but it is not a real solution because it uses numbers greater than 64 & non-consecutive. 

Hopefully soon Paul will provide a real solution of this kind of primal squares. He is working right now in the 6x6 case. By his way Jean Charles Meyrignac will attempt to make an exhaustive search for the magic 6x6 primal square.

***
The 3/1/2001 Paul Jobling announces "I have completed the search and found no 6x6 with the full torus property".

***