Recreational Mathematics – Optimal Strategy for Doubling and Reversing Game

recreational-mathematics

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)

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.