cp's OEIS Frontend

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

Counts the number of distinct winning positions of the game with exactly n frogs, each in a different place. Positions are considered the same if one can be obtained from the other by reversing it left-to-right.

Equivalently, a(n) is the number of unordered pairs {k, A030101(k)} with k odd such that the binary weight A000120(k) = n, and k occurs in A377232.

Since a stack of k frogs moves exactly k spaces in the Jumping Frogs game, the sum of the lengths of all moves starting from a position with n single frogs is at most A000217(n-1), the (n-1)st triangular number. Hence if it is a winning position, the length of the position (excluding unoccupied places to the left of the first occupied one, and unoccupied places to the right of the last occupied one) is at most one more than this triangular number. Therefore a(n) is finite for all n.

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.

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

Enumerate the primes in order, p_1 = 2, p_2 = 3, etc. Factor any natural number k > 1 as p_1^{x_1}p_2^{x_2}...p_i^{x_i}, where i is as small as possible and each x_j is nonnegative. Then when k is even and x_1, x_2, ..., x_i is a winning position for Jumping Frogs, k occurs as a term. We consider only even numbers to keep the positions distinct; leading zeros can never be used or affect the outcome of Jumping Frogs.

An even number k is a term if and only if A137502(k) is a term. - Pontus von Brömssen, Oct 24 2024

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

The least side length that is required to express n as the sum of two rectangular numbers.

The minimum height of an area-n generalized "L" polyomino (a union of two integer-side rectangles in portrait orientation).

The largest n such that a(n) = k is 2k^2 since that n can be written as k*k + k*k.

Construct a tree of rational numbers by starting with a root labeled 1/2. Then iteratively add children to each node as follows: to the node labeled p/q in lowest terms, add children labeled with any of p/(q+1) and (p+1)/q that are less than one and have not already appeared in the tree. Then a(n) is the number of nodes n-3 levels below the root (the offset 3 is chosen so that the level number corresponds to the sum of the numerator and denominator of most fractions at level n).

This construction is similar to the Farey tree except that the children of p/q are its mediants with 0/1 and 1/0 (if those mediants have not already occurred), rather than its mediants with its nearest neighbors among its ancestors.

It might appear at first glance that the sum of the numerator and denominator of all fractions at level n divides n. However, 7/10 and 8/9 first appear at level 33 (as children of 7/9 at level 32), but 17 does not divide 33.

Since 1/(n-1) always appears on level n, a(n) > 0. Bertrand's postulate implies that for all n > 5, a(n) > 1, since for each prime p with n/2 < p < n, (n+1-p)/p will also occur at level n.

For a proof that the tree described above includes all rational numbers between 0 and 1, see Gordon and Whitney.

Construct a tree of rational numbers by starting with a root labeled 1/2. Then iteratively add children to each node breadth-first as follows: to the node labeled p/q in lowest terms, add children labeled with any of p/(q+1) and (p+1)/q (in that order) that are less than one and have not already appeared in the tree. Then a(n) is the denominator of the n-th rational number (in lowest terms) added to the tree.

This construction is similar to the Farey tree except that the children of p/q are its mediants with 0/1 and 1/0 (if those mediants have not already occurred), rather than its mediants with its nearest neighbors among its ancestors.

For a proof that the tree described above includes all rational numbers between 0 and 1, see Gordon and Whitney.

Construct a tree of rational numbers by starting with a root labeled 1/2. Then iteratively add children to each node breadth-first as follows: to the node labeled p/q in lowest terms, add children labeled with any of p/(q+1) and (p+1)/q (in that order) that are less than one and have not already appeared in the tree. Then a(n) is the numerator of the n-th rational number (in lowest terms) added to the tree.

This construction is similar to the Farey tree except that the children of p/q are its mediants with 0/1 and 1/0 (if those mediants have not already occurred), rather than its mediants with its nearest neighbors among its ancestors.

For a proof that the tree described above includes all rational numbers between 0 and 1, see Gordon and Whitney.

A sequence 1=a_0 < a_1 < a_2 < ... < a_l = n is an addition chain (of length l) for n if for each i, 0 < i <= l, there are j_i and k_i such that a_i = a_j_i + a_k_i. Such a chain is called a star-chain or Brauer chain if in addition each j_i = i-1. A number is a Brauer number if among its shortest addition chains there is a Brauer chain, and non-Brauer otherwise.

The length of a shortest Brauer chain for n is often denoted l^*(n). A003313(n) gives the length of a shortest addition chain for n. Thus n is in this sequence if and only if A003313(n) < l^*(n).

For entries at least through 41506, these numbers satisfy l^*(n) = A003313(n) + 1. It seems likely that larger differences between l^*(n) and A003313(n) occur for later entries in this sequence, but it is unclear whether any n with a larger difference have been found.

These differences between l^*(n) and A003313(n) are highlighted by the following formulation: consider a machine which starts with a 1 in "cache" and can then at each step execute one of two operations: (1) Add any number that has ever been in cache to the current contents of cache, or (2) Restore any number that has previously been in cache to the cache, replacing its prior contents. Then n is in this sequence if and only if there is a shortest program that results in n in cache that includes a "Restore" step. Note further that if there is an entry in this sequence such that l^*(n) > A003313(n)+1, then all shortest programs producing n in cache would contain a "Restore" operation. The definition of A293771 is based on a similar machine with a separate "Store" operation that puts the cache value into "memory," and one could formulate an analogous conjecture here that the "Restore" operation is never necessary for a shortest program. The existence or not of an n in this sequence such that l^*(n) > A003313(n)+1 would settle this question and provide mild evidence one way or the other on the conjecture in A293771.