Recreational Mathematics – Optimal Strategy for Doubling and Reversing Game


Recently, i've been interested in a $1$-player game. Your goal is to reach the smallest number that can be reached by $n$ moves of applying either $x \rightarrow 2x$ or $x\rightarrow R(2x)$. ($R(x)$ is the digit reversal function, for example, $R(512) = 215$) The optimal final value with $n$ moves (i.e. the smallest number that can be reach with $n$ application of either $x \rightarrow 2x$ or $x\rightarrow R(2x)$, with initial value of $1$) can be found in (actually, the draft edits aren't accepted yet, as of April 15 2024, so the sequence and discussions about it can be found at The first few terms of the sequence are:
1, 2, 4, 8, 16, 23, 46, 29, 58, 71, 34, 68, 37, 47, 49, 89, 79, 59, 19, 38, 67, 35, 7, 14, 28, 56, 13…$$

Calculating the $n$-th term is actually very computationally expensive requiring $O(2^n)$ time. Sir Michael Branicky then came and calculated the optimal moves for $27≤n≤34$ and he found that $1$ can be reached again in $30$ moves and here is that combination that attain $1$ again:
$$1, 2, 4, 8, 61, 122, 442, 488, 976, 2591, 2815, 365, 37, 47, 49, 98, 196, 392, 487, 479, 859, 1718, 3436, 2786, 2755, 155, 13, 26, 25, 5, 1$$
Basically, Sir Branicky proved that $a(30k) = 1$ and $a(k) ≤ a(k \bmod 30) ≤ a(15) = 89$ for all $k \in \mathbb{N}$. ($a(n)$ is the smallest number that can be achieved in the game with you having $n$ moves)

Can anybody prove/disprove the claim that the sequence of optimal final values (with $(k+1)$-thmember corresponding with the optimal final value given $k$ moves) is periodic?

The number $2718$ is an interesting number as there's a path of length $2$ from $2718$ to itself (doubling move followed by a doubling+reversing move). If one can find an odd length and an even length paths from 1 to itself, that both goes through $2718$, then this would prove that the sequence would eventually be all $1$s. Proving the claim once and for all.

(UPDATE: Actually, there's another path from $2718$ to itself that contains $7$ moves. So actually, a single path from $1$ to $1$ containing $2718$ would suffice)

Best Answer

You have provided the data to show the values are eventually periodic. First look at the values of $k$ such that $a(k)=1$. These are at least all $k$ such that $k \equiv 0 \pmod {30}$. If there are any other values of $k$, take the $\gcd$ of all those values, which must be a factor of $30$. $1$ will eventually recur at this $\gcd$. Once the recurrences of $1$ are established, consider the sequence of values in a cycle between the $1$s. Each value is no higher than the corresponding value in the previous cycle. If any value is reduced, it must come from a $1$ before. That position in the cycle cannot increase. Eventually we must hit a minimum at each position and that cycle will repeat forever.