cp's OEIS Frontend

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

%I A377232 #26 Oct 24 2024 10:28:13
%S A377232 1,3,7,11,13,15,23,27,29,31,39,47,55,57,59,61,63,75,79,95,103,105,107,
%T A377232 111,115,119,121,123,125,127,143,155,159,183,191,203,207,211,215,217,
%U A377232 219,223,231,235,237,239,241,243,247,249,251,253,255
%N A377232 Odd numbers with binary representations corresponding to winning positions in Gordon Hamilton's Jumping Frogs game.
%C A377232 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.
%C A377232 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.
%C A377232 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.
%C A377232 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.
%C A377232 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
%D A377232 Gordon Hamilton, The Infinite Pickle, Our Street Books, 2024, pp. 77-114.
%H A377232 Glen Whitney, <a href="/A377232/b377232.txt">Table of n, a(n) for n = 1..10000</a>
%H A377232 Gordon Hamilton, <a href="https://mathpickle.com/project/jumping-frogs/">Jumping Frogs</a>, Math Pickle, 2017.
%H A377232 Gordon Hamilton and Brady Haran, <a href="https://www.numberphile.com/videos/frog-jumping">Frog Jumping</a>, Numberphile video, 2017.
%H A377232 Glen Whitney, <a href="/A377232/a377232.py.txt">Python code to generate b-file</a>
%e A377232 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.
%e A377232 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).
%e A377232 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):
%e A377232   1 0 1 1 1 1 1 1 1 1 0 1
%e A377232   1 0 1 1 1 1 1 1 0 2 0 1
%e A377232   1 0 1 1 1 1 1 1 0 0 0 3
%e A377232   1 0 1 1 1 1 2 0 0 0 0 3
%e A377232   1 0 1 0 2 1 2 0 0 0 0 3
%e A377232   1 0 1 0 4 1 0 0 0 0 0 3
%e A377232   5 0 1 0 0 1 0 0 0 0 0 3
%e A377232   0 0 1 0 0 6 0 0 0 0 0 3
%e A377232   0 0 1 0 0 0 0 0 0 0 0 9
%e A377232   0 0 X 0 0 0 0 0 0 0 0 0
%Y A377232 Except for a(1), subsequence of A004780.
%Y A377232 Cf. A030101.
%K A377232 nonn,base
%O A377232 1,2
%A A377232 _Glen Whitney_, Oct 21 2024