login
A342431
Solution to Von Neumann stepping stone puzzle (see Comments).
1
1, 2, 5, 8, 13, 18, 21, 24, 29, 31, 34, 38, 42, 46
OFFSET
1,2
COMMENTS
This is a variant of the stepping stone sequence (A337663), where any cell has just 4 neighbors (Von Neumann neighborhood). The game works as follows:
Start with an infinite square grid. Each cell has four neighbors. Place n 1's anywhere. Now place the numbers 2, 3, ..., m in order, subject to the rule that when you place k, the sum of its neighbors must equal k. Then a(n) is the maximum m that can be achieved.
FORMULA
a(n) >= 3n - 4 (found by Thomas Ladouceur).
The proof follows by this construction:
+----+----+----+----+----+----+----+
| 1 | 4 | 5 | 6 | 1 | 10 | 11 |
+----+----+----+----+----+----+----+
| 2 | 3 | 1 | 7 | 8 | 9 | 1 |
+----+----+----+----+----+----+----+
| 1 | | | | | | |
+----+----+----+----+----+----+----+
EXAMPLE
From code compiled by Hugo van der Sanden and Thomas Ladouceur.
a(3) = 5, with 3 1's:
+----+----+----+
| 1 | 2 | 1 |
+----+----+----+
| 4 | 3 | |
+----+----+----+
| 5 | 1 | |
+----+----+----+
and
a(10) = 31, with 10 1's:
+----+----+----+----+----+----+----+----+----+----+
| | 9 | 8 | 1 | 11 | | | | | |
+----+----+----+----+----+----+----+----+----+----+
| | 1 | 7 | 6 | 10 | | | | | |
+----+----+----+----+----+----+----+----+----+----+
| 28 | 27 | 12 | 5 | 4 | 1 | | | | |
+----+----+----+----+----+----+----+----+----+----+
| 1 | 14 | 13 | 1 | 3 | 2 | 1 | | | |
+----+----+----+----+----+----+----+----+----+----+
| 16 | 15 | | | 26 | 29 | 30 | | | |
+----+----+----+----+----+----+----+----+----+----+
| 17 | 1 | 21 | 22 | 23 | 1 | 31 | | | |
+----+----+----+----+----+----+----+----+----+----+
| 18 | 19 | 20 | 1 | 24 | 25 | | | | |
+----+----+----+----+----+----+----+----+----+----+
| 1 | | | | | | | | | |
+----+----+----+----+----+----+----+----+----+----+
CROSSREFS
Cf. A337663.
Sequence in context: A076145 A332774 A256829 * A049617 A375996 A054074
KEYWORD
nonn,more,hard
AUTHOR
EXTENSIONS
a(13)-a(14) from Bert Dobbelaere, Mar 19 2021
STATUS
approved