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 https://oeis.org/A371880 (actually, the draft edits aren't accepted yet, as of April 15 2024, so the sequence and discussions about it can be found at https://oeis.org/draft/A371880). 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.