About the complexity of some operation involving integers There are two integers: $A, B$. Given the below four allowed operations (and only them):
$A+1$, $A-1$, $\sqrt{A}$, $A^2$
Also, it is only allowed to take the square root of $A$ when this square root yields a natural number.
How can one find the minimum amount of operations in order to get from $A$ to $B$?
 A: There is a simple algorithm because the minimal path from $A$ to $B$ using these operations must have a very constrained form.
First, an optimal sequence of $x+1$ and $x-1$ operations from $a$ to $b$ has clearly length $|a-b|$, i.e., it cannot mix operations of different signs.
Second, in an optimal path, no $x^2$ operation precedes any $\sqrt x$ operation. Indeed, if there were a subsequence $a,a^2,\dots,b^2,b$, where the $\dots$ are $x\pm1$ operations, we can replace it with just a sequence of $x\pm1$ operations. This shortens the sequence as
$$2+|a^2-b^2|\ge2+|a-b|>|a-b|.$$
Third, if the optimal path contains a sequence of $x\pm1$ operations followed by $\sqrt x$, say a subsequence $a,\dots,b^2,b$, then WLOG $b^2$ is the nearest square to $a$. Indeed, let $b'=\lfloor\sqrt a\rceil$, where $\lfloor x\rceil:=\lfloor x+\frac12\rfloor$, and replace the subsequence with $a,\dots,b'^2,b',\dots,b$. This does not increase the sequence, as
$$|a-b^2|\ge|a-b'^2|+|b-b'|:$$
if $a-b^2$ and $a-b'^2$ have the same sign, we have $|a-b^2|=|a-b'^2|+|b^2-b'^2|$. If, say, $b'^2<a<(b'+1)^2\le b^2$, we have
$$\begin{align*}
|a-b^2|&=|b^2-(b'+1)^2|+|(b'+1)^2-a|\\
&\ge|b-(b'+1)|+|b'^2-a|+1=|b-b'|+|b'^2-a|,
\end{align*}$$
as $|b'^2-a|<|(b'+1)^2-a|$.
Thus, the optimal path from $A$ to $B$ looks as
$$A_0,\dots,A_1^2,A_1,\dots,A_2^2,A_2,\dots,A_n,\dots,B_m,B_m^2,\dots,B_{m-1},B_{m-1}^2,\dots,B_0,$$
where $A_0=A$, $A_{i+1}=\lfloor\sqrt{A_i}\rceil$, $B_0=B$, $B_{j+1}=\lfloor\sqrt{B_j}\rceil$. The length $c_i$ of the subpath from $A$ to $A_i$ is given by $c_0=0$, $c_{i+1}=c_i+1+|A_i-A_{i+1}^2|$, and likewise, the length $d_i$ of the subpath from $B_i$ to $B$ is $d_0=0$, $d_{i+1}=d_i+1+|B_i-B_{i+1}^2|$, thus the total length is $l=c_n+d_m+|A_n-B_m|$.
We can compute the optimal length $l$ by calculating the sequences $A_i$ and $B_j$ as above, until reaching $A_N=1=B_M$, and then
$$l=\min\{c_n+d_m+|A_n-B_m|:n\le N,m\le M\}.$$
Note that $N=O(\log\log A)$ and $M=O(\log\log B)$. We can further simplify the expression by noting that we do not have to consider all pairs $(n,m)$, but only those where $A_n$ and $B_m$ are neighbours in the sequence obtained by sorting $\{A_n:n\le N\}\cup\{B_m:m\le M\}$. Indeed, if, say, $A_n<B_k<B_m$, then
$$B_m-A_n=(B_m-B_{k+1})+(B_{k+1}-B_k)+(B_k-A_n)\ge d_k-d_m+(B_k-A_n)$$
as $B_{k+1}-B_k>|B_{k+1}-B_k^2|$.
It follows that we can compute the optimal length with the following simple algorithm:
c := 0, l := |A - B|
while l > c do:
    if A < B then swap(A,B)
    A' := ⌊√A⌉
    c := c + 1 + |A-(A')^2|
    A := A'
    l := min (l, c + |A - B|)
output l

This computes the result with $O(\log\log A+\log\log B)$ arithmetic operations of total bit-complexity $O(M(\log A)+M(\log B))=O(\log A\log\log A+\log B\log\log B)$, where $M(n)=O(n\log n)$ is the complexity of $n$-bit multiplication.
