For any two natural numbers, we can apply the Euclidean algorithm to get a sequence of quotients and remainders: $$ a = q_1b + r_1 \\ b = q_2r_1 + r_2 \\ \vdots \\ r_{k-2} = q_{k}r_{k-1}+r_{k} \\ \vdots \\ r_{n-1} = q_{n+1} r_{n} + 0 $$
I am interested in particular about the sequence $q_{i}$, and when all but the final entry in this sequence is 1. For example when $a=69$ and $b=45$ the Euclidean algorithm proceeds as:
$$ 69 = 1 \times 45 + 24 \\ 45 = 1 \times 24 + 21 \\ 24 = 1 \times 21 +3 \\ 21 = 7 \times 3 + 0 $$
I define the function $Q(a)$ as the number of $b$ with $0 < b \leq a$ such that this property of the $q_{i}$ holds.
I've computed some values of this function, and it doesn't seem to appear as a sequence on OEIS (nor do any related sequences like $a - Q(a)$). I've also proven that $Q(a) \geq 4$ for all $a \geq 4$. Beyond that though, this function is a mystery to me. I conjecture that there are infinitely $a$ such that $Q(a) = n$ for some particular $n \geq 4$, but I have no idea how to go about proving something like that. I notice that it also seems to grow approxmately logarithmically (at least for small $a$), but I don't know how to make that rigorous or prove anything in that regard here either, or indeed if that relationship is even true as $a$ gets large.
Any ideas are welcome.
Reverse the sequence of equation. The bottom equation is just $r_{n-1} = qr_n$, so backing up from there we get $$\begin{align}r_{n-1} &= qr_n\\ r_{n-2} &= r_{n-1} + r_n = (q + 1)r_n\\ r_{n-3} &= r_{n-2} + r_{n-1} = (2q + 1)r_n\\ r_{n-4} &= r_{n_3} + r_{n-2} = (2q + 1)r_n + (q + 1)r_n = (3q + 2)r_n\\ r_{n-5} &= r_{n_4} + r_{n-3} = (3q + 2)r_n + (2q + 1)r_n = (5q + 3)r_n \end{align}$$ At which point the pattern is obvious: $$r_{n-k} = (F_kq + F_{k-1})r_n$$ Where the $F_k$ are the Fibonacci sequence.
So $a$ must be of the form $$a = (F_{n+1}q + F_n)r$$ for some $r$ and $n$, in which case $b = (F_nq + F_{n-1})r$.
So for for each divisor $d$ of $a$, starting with $n=1$, subtract $F_n$ from $d$ and check if the result is divisible by $F_{n+1}$. This cannot be true if $F_n \ge\frac d2$ since the smallest $q$ can be is $1$, so you can stop checking at that point. when $F_{n+1}\mid d - F_n$, calculate $$b = \left(F_n\frac{d-F_n}{F_{n+1}} + F_{n-1}\right)\frac ad$$