A342431 Solution to Von Neumann stepping stone puzzle (see Comments).

1, 2, 5, 8, 13, 18, 21, 24, 29, 31, 34, 38, 42, 46

Offset: 1

Author

Jeremy Rebenstock, Thomas Ladouceur Mar 12 2021

Keywords

• nonn
• more
• hard

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.

Examples

			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.

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

+----+----+----+----+----+----+----+

Extensions

a(13)-a(14) from Bert Dobbelaere, Mar 19 2021