A377307 Minimum number of consecutive pieces that must be added to the pattern given by the binary representation of n to produce a winning position in Gordon Hamilton's Jumping Frogs game, or -1 if there is no such position.

1, 2, 3, 1, 4, 8, 3, 1, 5, 2, 10, 3, 4, 2, 1, 1, 6, 3, 8, 2, 6, 12, 6, 3, 5, 2, 1, 2, 4, 2, 1, 1, 7, 4, 3, 3, 9, 13, 10, 2, 7, 11, 12, 6, 7, 2, 3, 3, 6, 3, 3, 2, 4, 8, 1, 2, 5, 2, 2, 1, 1, 2, 1, 1, 8, 5, 4, 3, 10, 14, 3, 3, 8, 12, 13, 7, 8, 3, 5, 2, 8, 11, 10, 6

Offset: 0

Author

Glen Whitney, Oct 23 2024

Keywords

• nonn

Comments

For the rules of the Jumping Frogs game, see A377232.

Given the result that any block of consecutive single frogs is a winning position, the "interesting" positions are those that have an empty place, or gap, in them. The value a(n) measures "how difficult" the n-th such position is, as follows: Starting from a nonnegative integer n, interpret its binary representation as a Jumping Frogs position consisting of empty and/or singly-filled places. Add one more empty place (one more 0) at the end, to ensure that there is at least one gap. The value a(n) is then the minimum positive number of additional singly-filled places that must be added thereafter to create a winning position, or -1 if no winning position can be so constructed.

Equivalently, a(n) is the least k such that n*2^{k+1} + 2^k - 1 is a term of A377232, should such a k exist, and -1 otherwise.

Gordon Hamilton conjectures in his reference below that a(n) is positive for all n.

Examples

			Consider n=5, with binary representation 101. We append another 0, to get 1010, and then consider the Jumping Frogs positions 10101, 101011, 1010111, etc. Of these, the first one that is solvable turns out to be 101011111111, with eight ones. Therefore, a(5) = 8. (Here is the solution for this case, specified by the place number where each jump starts and its direction, R or L; the places are numbered right-to-left from 0: 5R, 3L, 4L, 7L, 11R, 6R, 1L, 2R, 0L and all ten frogs end up in place 9, the one flanked by zeros in the binary representation.)
		

References

• Gordon Hamilton, The Infinite Pickle, Our Street Books, 2024, p. 106.

Links

• Pontus von Brömssen, Table of n, a(n) for n = 0..276

Crossrefs

Cf. A377232, winning binary jumping frogs positions.