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$?
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.
