A377232 Odd numbers with binary representations corresponding to winning positions in Gordon Hamilton's Jumping Frogs game.

1, 3, 7, 11, 13, 15, 23, 27, 29, 31, 39, 47, 55, 57, 59, 61, 63, 75, 79, 95, 103, 105, 107, 111, 115, 119, 121, 123, 125, 127, 143, 155, 159, 183, 191, 203, 207, 211, 215, 217, 219, 223, 231, 235, 237, 239, 241, 243, 247, 249, 251, 253, 255

Offset: 1

Author

Glen Whitney, Oct 21 2024

Keywords

• nonn
• base

Comments

A position in the jumping frogs game is a finite sequence P of nonnegative integers. If P_i = k ("lily pad i has k frogs"), and P_{i+k} > 0 ("lily pad i+k has at least one frog"), then it is legal to move to position Q where Q_i = 0, Q_{i+k} = P_{i+k} + k, and all other Q_j = P_j ("k frogs may together jump k places"). Similarly, if P_{i-k} > 0 then it is legal to move to Q' where Q'i = 0, Q'{i-k} = P_{i-k} + k, and Q'_j = P_j for all other j. These are the only legal moves. A position is considered "winning" if there is a sequence of legal moves leading to a position with only one nonzero entry ("the frogs want to all party together"). Any number represents a position with at most one frog per lily pad via its binary representation considered as a sequence of ones and zeros. We only consider odd numbers in this sequence to keep the positions distinct; trailing zeros in a sequence can never be used or affect whether it is winning or not winning.

Every number of the form 2^k - 1 is a term: As shown in the Hamilton reference, the position consisting of k consecutive frogs can be won by starting in the middle and jumping 1, 2, ..., k-1 places outward, alternating left and right.

The example below for i=5 generalizes to show that every term (except the first) must be a term of A004780, i.e., have two consecutive ones in its binary representation.

Since arbitrary nonnegative numbers are allowed in positions of the jumping frogs game, one could generate an analogous sequence for any base b by interpreting a number as its sequence of digits in base b, and including only those numbers corresponding to winning positions with no trailing zeros.

An odd number k is a term if and only if A030101(k) (the binary reversal of k) is a term. - Pontus von Brömssen, Oct 23 2024

Examples

			Consider i = 5 with binary representation 101. There are no legal moves from the position 1,0,1 (since no "frog" is adjacent to another one, and single frogs may only jump one place). Therefore 5 is not a term.
Conversely, consider i = 11 with binary representation 1011. From 1, 0, 1, 1, it is legal to move to 1, 0, 2, 0, and then to 3, 0, 0, 0, with only one nonzero entry. Therefore, 1, 0, 1, 1 is a winning position, and 11 does appear as a(4).
The Numberphile video (see the Links) mentions a then-open problem as to whether any number of the form 2^k - 2^{k-2} - 2 - 1 (corresponding to a single frog, an empty place, k-4 consecutive frogs, an empty place, and then a final lone frog) is a term. In fact, 3069 corresponding to k=12 appears (as a(371), and no smaller number of this form occurs, although many larger ones do):
  1 0 1 1 1 1 1 1 1 1 0 1
  1 0 1 1 1 1 1 1 0 2 0 1
  1 0 1 1 1 1 1 1 0 0 0 3
  1 0 1 1 1 1 2 0 0 0 0 3
  1 0 1 0 2 1 2 0 0 0 0 3
  1 0 1 0 4 1 0 0 0 0 0 3
  5 0 1 0 0 1 0 0 0 0 0 3
  0 0 1 0 0 6 0 0 0 0 0 3
  0 0 1 0 0 0 0 0 0 0 0 9
  0 0 X 0 0 0 0 0 0 0 0 0
		

References

• Gordon Hamilton, The Infinite Pickle, Our Street Books, 2024, pp. 77-114.

Links

• Glen Whitney, Table of n, a(n) for n = 1..10000
• Gordon Hamilton, Jumping Frogs, Math Pickle, 2017.
• Gordon Hamilton and Brady Haran, Frog Jumping, Numberphile video, 2017.
• Glen Whitney, Python code to generate b-file

Crossrefs

Except for a(1), subsequence of A004780.

Cf. A030101.