Easy Sequence Problem

Suppose $(A_N,A_{N+1})=(P,Q)$. If $P<Q$, the last binary bit of $N$ is $0$ and the previous pair is $(P,Q-P)$. If $P>Q$, the last bit is $1$ and the previous pair is $(P-Q,Q)$.

Repeated subtraction can be too slow. When $P<Q$, let $t=\left\lfloor\frac{Q-1}{P}\right\rfloor$ and subtract at once; this removes trailing zero bits. The case is symmetric. Since and are coprime, the process ends at .

Reattach the removed bit runs in reverse order. Appending $t$ zeros changes $X$ to $X2^t$, while appending $t$ ones changes it to $X2^t+(2^t-1)$. Work modulo . The number of quotient steps is logarithmic, so the time complexity is .