cp's OEIS Frontend

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

%I A342431 #28 Mar 27 2021 03:58:54
%S A342431 1,2,5,8,13,18,21,24,29,31,34,38,42,46
%N A342431 Solution to Von Neumann stepping stone puzzle (see Comments).
%C A342431 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:
%C A342431 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.
%F A342431 a(n) >= 3n - 4 (found by _Thomas Ladouceur_).
%F A342431 The proof follows by this construction:
%F A342431   +----+----+----+----+----+----+----+
%F A342431   |  1 |  4 |  5 |  6 |  1 | 10 | 11 |
%F A342431   +----+----+----+----+----+----+----+
%F A342431   |  2 |  3 |  1 |  7 |  8 |  9 |  1 |
%F A342431   +----+----+----+----+----+----+----+
%F A342431   |  1 |    |    |    |    |    |    |
%F A342431   +----+----+----+----+----+----+----+
%e A342431 From code compiled by _Hugo van der Sanden_ and _Thomas Ladouceur_.
%e A342431 a(3) = 5, with 3 1's:
%e A342431   +----+----+----+
%e A342431   |  1 |  2 |  1 |
%e A342431   +----+----+----+
%e A342431   |  4 |  3 |    |
%e A342431   +----+----+----+
%e A342431   |  5 |  1 |    |
%e A342431   +----+----+----+
%e A342431 and
%e A342431 a(10) = 31, with 10 1's:
%e A342431   +----+----+----+----+----+----+----+----+----+----+
%e A342431   |    |  9 |  8 |  1 | 11 |    |    |    |    |    |
%e A342431   +----+----+----+----+----+----+----+----+----+----+
%e A342431   |    |  1 |  7 |  6 | 10 |    |    |    |    |    |
%e A342431   +----+----+----+----+----+----+----+----+----+----+
%e A342431   | 28 | 27 | 12 |  5 |  4 |  1 |    |    |    |    |
%e A342431   +----+----+----+----+----+----+----+----+----+----+
%e A342431   |  1 | 14 | 13 |  1 |  3 |  2 |  1 |    |    |    |
%e A342431   +----+----+----+----+----+----+----+----+----+----+
%e A342431   | 16 | 15 |    |    | 26 | 29 | 30 |    |    |    |
%e A342431   +----+----+----+----+----+----+----+----+----+----+
%e A342431   | 17 |  1 | 21 | 22 | 23 |  1 | 31 |    |    |    |
%e A342431   +----+----+----+----+----+----+----+----+----+----+
%e A342431   | 18 | 19 | 20 |  1 | 24 | 25 |    |    |    |    |
%e A342431   +----+----+----+----+----+----+----+----+----+----+
%e A342431   |  1 |    |    |    |    |    |    |    |    |    |
%e A342431   +----+----+----+----+----+----+----+----+----+----+
%Y A342431 Cf. A337663.
%K A342431 nonn,more,hard
%O A342431 1,2
%A A342431 _Jeremy Rebenstock_, _Thomas Ladouceur_ Mar 12 2021
%E A342431 a(13)-a(14) from _Bert Dobbelaere_, Mar 19 2021