More generally: For an nxn square, the simplest solution is to use a simple zig-zag pattern (or a simple spiral pattern), with each even number appearing in the square (and the odd numbers appearing outside of the square): 0 2 6 4 or: 0 2 4 10 8 6 12 14 16 The sum for this pattern is n^4 - n^2. The only possible way to improve on this is for two consecutive numbers to appear in the square, which can only be done within the first n-1 moves. The simplest such pattern is to make the first move within the square, then continue with the previous pattern: 0 1 5 3 or: 0 1 3 9 7 5 11 13 15 The sum for this pattern is n^4 - 2*n^2 + 1. This is optimal for 2x2, but not for 3x3 and higher, since for those cases the first *two* (or more) moves can remain within the square. The trick to these cases is efficiently filling in the remaining squares once the distance has reached n. My solution relied on the fact that a simple 4-move spiral will move you diagonally by 2 in each direction. But as n increases, finding an optimal fill pattern becomes much more complex. I may look at the 4x4 case a bit, but even if I find a decent solution, there will probably be no guarantee that it's optimal. Tom Éric Angelini writes:
Waow! I had found the same 2 x 2 as yours, my idea was that the 3 x 3 built on that one was leading to 64 (insread of my 63). But your 59 is beautiful! Could you find the smallest 4 x 4 and submit to Neil's OEIS this (starting) sequence? I'm unable to find anything above the 2 x 2 square!-) à+ É. Catapulté de mon aPhone
Le 21 mai 2019 à 00:19, Tom Karzes <karzes@sonic.net> a écrit :
Ok, sure. For a 3x3 square:
R D L R D U R L R L U D D L U R
0 1 16 10 8 6 12 2 4
(sum = 59)
Tom
Éric Angelini writes:
Yes, well done, Tom! Next square? ;-) à+ É. Catapulté de mon aPhone
Le 20 mai 2019 à 23:31, Tom Karzes <karzes@sonic.net> a écrit :
Wouldn't the followiung work for a 2x2 square?
R U D R L
0.1 5.3
(sum = 9)
Tom
Éric Angelini writes:
Hello MathFun The aim of this challenge is to fill a square (that has a 0 --zero-- in its upper-left corner) with integers. The best square is the one with the lowest sum of the said integers.
Here is my personal best for the 2 x 2 square (sum = 11):
0.1 6.4
... my best 3 x 3 has sum 63:
0.1.20 6.8.10 4.2.12
In order to fill a square, you have to start on the zero cell and jump: a) over zero cell (you land on 1 of the 4 adjacent cells – diagonal jumps are forbidden) b) from there, over 1 cell (you always have the choice to jump up, right, down or left if the landing cell is empty) c) from there, over 2 cells (same rules as above) d) from there, over 3 cells (same rules – at every step the size of the jump is increased by 1). etc.
Here is my path two fill the 2 x 2 square, starting on 0 (R=right, D=down, U=up and L=left; the size of the jump is increased by 1 at every step, the 1st jump being of size zero):
R D D U R L
Here is my path to fill the 3 x 3 square -- same convention:
R D R L D U L R L R U D L R D U D U R L
Can you beat my personal records? And find records for bigger squares?
(forgive me if this is old hat) (some illustrations here, on my personal weblog): https://cinquantesignes.blogspot.com/2019/05/jump-and-fill-my-square.html
Best, É.