The LoL number game

Question

Tim and Tom are fictional characters (cats, I believe) who like to play the LoL number game.

In this game, Tim chooses two distinct integers A and B, both ≥ 2, and shows them to Tom. Tom's goal is to find a succession of translolmations that can be applied to A in order to obtain B. There are only two types of translolmations, denoted by the letters $\bf L$ and $\bf o$, in the order as they are applied, from left to right: $\bf L$ replaces the current integer with its square, and $\bf o$ replaces the current integer with the number of digits in its binary representation.

For example, if Tim chooses A = 7 and B = 11, a valid solution for Tom would be $\bf LoLLo$:

$7\buildrel\bf L\over\longrightarrow 49\buildrel\bf o\over\longrightarrow 6\buildrel\bf L\over\longrightarrow 36\buildrel\bf L\over\longrightarrow 1296\buildrel\bf o\over\longrightarrow 11$

For A = 10 and B = 9, valid solutions are $\bf ooL$ and $\bf oLLo$:

$10\buildrel\bf o\over\longrightarrow 4\buildrel\bf o\over\longrightarrow 3\buildrel\bf L\over\longrightarrow 9$

$10\buildrel\bf o\over\longrightarrow 4\buildrel\bf L\over\longrightarrow 16\buildrel\bf L\over\longrightarrow 256\buildrel\bf o\over\longrightarrow 9$

Tom is confident he will always be able to win the game, given a sufficient number of translolmations, no matter what integers Tim chooses. Can you explain how?

Answer 1

First of all, notice that by repeatedly applying $\bf o$, we can always reduce a number to 2. This should be readily apparent, but here's a non-rigorous proof of the fact:

2 has a binary representation requiring 2 digits (10), as does 3 (11). The length of the binary representation of a number grows slower than $n$, so $n\ge 3$ implies that $n \buildrel\bf o\over \longrightarrow m$ with $n \gt m$. Therefore, if $n\ge 3$, applying $\bf o$ will always reduce it by at least 1, allowing us through repeated applications to reduce the number to 2.

Now let's consider $\bf o$ in reverse. In order to get to B, we need to apply $\bf o$ to a number whose binary representation has B digits: $2^{B-1} \le n \lt 2^B$. If we square a number, it can jump that range - for example if $B=5$ then $2^{5-1}=16$ and $2^{5}=32$, but $15^2=225$.

However, if we apply $\bf o$ twice, then the range becomes far wider - $2^{2^{B-1}}\le n\lt 2^{2^{B}}$. At this point, there's no way to jump the range:

$$(2^{2^{B-1}}-1)^2=(2^{2^{B-1}})^2-2*2^{2^{B-1}}+1=2^{2^B}-2^{2^{B-1}+1}+1$$

Because $B\ge 2$, $2^{2^{B-1}+1}\ge 2^{2^{1}+1}=2^3=8$, so $2^{2^B}-2^{2^{B-1}+1}+1<2^{2^B}-7<2^{2^B}$.

So to summarize, apply $\bf o$ until it is less than $2^{2^B}$, then apply $\bf L$ until $2^{2^{B-1}}\le n\lt 2^{2^{B}}$, and then apply $\bf o$ twice. Of course, this is horribly inefficient, but it proves that it is always possible. For example, with B=197, $2^{2^B}$ is somewhere around $10^{10^{58}}$.

Answer 2

Whenever $x>2$, we have $o(x)<x$, so applying $o$ enough (for example, $A$ times) obtains $$2$$ Applying $L$ to this a total of $B-1$ times gets $$2^{2^{B-1}}$$ This is a one followed by $2^{B-1}$ zeros, so applying $o$ to this gets $$2^{B-1}+1$$ This number is a 1, followed by $B-2$ zeroes, followed by a $1$, so applying o this gets $$ B $$ Thus, a recipe to get from $A$ to $B$ is given by $$ o^2(L^{B-1}(o^A(A)))=B $$ where $o^n$ denote repeated function application.