概要
埋め込みとか、$\sqrt{N}$ 単位の計算量を仮定した解説しかなかったので、一応書きます。
たとえば制約が、$N\leqq 10^{18}$ でもすぐに答が出ます。
解法
次の計算を行う関数を考えます。
$f(a,b,c)$：「$n$ に居るときに、$\mathrm{popcount}(n) + a$ だけ進む」という新しいゲームを考える。$n=b$ から始めて、$n\geqq 2^c$ になるまで進むときの、手数と終着地点をかえす。
たとえば、$f(2,1,4)$ を計算すると、$1$ → $4$ → $7$ → $12$ → $16$ より、$(4,16)$ が返るという要領です。
$c$ が小さな場合は愚直に計算して、$c$ が大きな場合には次の要領で再帰的に計算できます。
たとえば、$f(0,1,10)$ を計算したいとします。$2^{10}=1024$ 以上になるまでの計算を返すことが目標です。まず、$2^9$ を超えるまでの計算をします。$c$ が小さな場合が計算されているとすると、 $f(0,1,9) = (125, 515)$ より $126$ 歩で $n = 515$ に到達することが分かります。
そこから $1024$ に到達するまでの過程は、最上位の「1」のおかげで、下 $9$ 桁だけ見たときのゲームよりも $1$ だけ余分に進みながら行うことと等価です。$f(1,3,9) = (98,519)$ を元に、$n=515$ から $98$ 手先に、$n=512+519=1031$ に到達できることが分かります。
さて、$f(a,b,c)$ がすべて計算できると、元の問題（$N$ 以上に到達するまでシミュレート）も簡単です。距離が $2^c$ より大きいうちは、$n = 2^cq + r$ として、$f(\mathrm{popcount}(q), r, c)$ により次の $2^c$ の倍数以上になるまで進む計算を行えます。
計算量は、厳密なことは検討していませんが、$b,c < \lg N$ かつ $a < \lg N – c$ に対する $f(a,b,c)$ を全部計算してしまうことが、1 件あたり $\Theta(1)$ で行えます。したがって、$O(\lg N^3)$ で解くことが可能です。
全部の $(a,b,c)$ を計算する必要はないような気がしますが…結局定数倍くらいで $\Omega(\lg N^3)$ になるかもしれません。私はメモ化再帰の形で実装しました。
