Coprime Grid Puzzle

Start with an n-by-n grid. Place n^2 positive integers into the grid such that: Each integer is greater than the integer placed previously. Each integer is left of, right of, below, or above the integer placed immediately previously into the grid. Every integer is coprime to every other integer in its column and row, and the integers in both main diagonals are all coprime with each other.

Your goal is to have the final integer be as low as possible.

For example,for n = 4, we can have:

1 2 3 29 17 19 22 23 7 5 4 27 13 2 3 25 8 13 17 25 and 11 1 5 26 9 11 19 23 10 9 7 29

But can we do better than 29 for n=4?

Yes. I found by-hand a solution for n=4 that ends in a 23. (I leave finding a last-integer-is-23 solution for rec.puzzles and sci.math readers as a puzzle.)

Is it possible to end on even a lower integer with n=4?

(We can always have a solution for any n, just fill the grid with increasing primes. Finding the best solution, however, is trickier.)

thanks, Leroy Quet

No, 23 is optimal. You cannot exceed 1 even number per column, so the remaining 12 numbers must be odd. 23 is the 12th odd number.

There are 4 odd multiples of 3 you have to use, so forget about using any multiples of 6. I don't know if you're forced to drop any other particular even numbers out of the 7 remaining.

Clarification of 'the integers in both main diagonals are all coprime with each other': I mean the integers in any main diagonal are all coprime with the other integers in *that particular* diagonal.

Anyone have any luck finding a 23 case?

thanks, Leroy Quet

Come on. Finding a 23-equals-highest-integer solution is easy. *I* found a solution!

In any case, I give my answer below the copied message.

Solution:

3 1 23 22 4 11 13 21 5 9 14 19 7 8 15 17

Are there any other 23-solutions (except for rotations and reflections)?

thanks, Leroy Quet

(See my other recent reply for my 23-equals-highest-integer solution.)

I wonder which n, if any, is such that the lowest possible highest integer is greater than 2*n*(n-1)-1.

thanks, Leroy Quet

I notice that the path in your solution is a cycle (end adjacent to beginning).

n=2 has a lowest ending number of 5.

The 3 factor becomes a real problem for n>7. At n=8 you have 7 odd numbers in each row but if you use all of the odd numbers, 1/6 of them will be multiples of 3.

Yes there is:

Exchanging both of 1) top and bottom rows, and 2) leftmost and rightmost columns, will preserve all rows columns and diagonals without it being a reflection or a rotation.

- Risto -

Found by Ruben in the mailing list 'Snark'

7 - 5 - 3 - 2 9 - 22 - 23 - 1 10 - 21 - 19 - 17 11 - 13 - 14 - 15

If I understand you right, then exchanging the top and bottom rows and/or exchanging the left and right column does *not* get a solution, because the integers in ascending order would not form a continuous path. (The 1 and 3 would not be next to each other, for example.)

thanks, Leroy Quet

I have been unable by-hand to find a solution to the 4-by-4 grid which ends in an integer < 29 but > 23. (And except for rotations/reflections of my 23-solution, I cannot find another 23-solution either.)

How would the sequence start where the n_th term is the lowest possible high-integer for the n-by-n grid? (Maybe someone could submit this sequence to the On-line Encyclopedia of Integer Sequences, if it is not already there.)

thanks, Leroy Quet