A better recurrence?

With a bit of algebra, we can explain the recurrence relation in a more elegant way:

$$\begin{align} x_n &= 1 + \frac{a_n}{b_n}\\ x_{n+1} &= 1 + \frac{1}{2 + \frac{a_n}{b_n}}\\ \end{align}$$

It should be clear than $2 + \frac{a_n}{b_n} = 1 + x_n$, so we can rewrite the second equation as:

$$\begin{align} x_{n+1} &= 1 + \frac{1}{1 + x_n}\\ x_{n+1} &= \frac{2 + x_n}{1 + x_n}\\ \end{align}$$

We are not actually interested in $x_{n}$, but in the numerator and denominator of $x_{n}$, thus if we have $x_n = \frac{p_n}{q_n}$, we can rewrite the last equation as:

$$x_{n+1} = \frac{p_{n+1}}{q_{n+1}} = \frac{2 + \frac{p_n}{q_n}}{1 + \frac{p_n}{q_n}} = \frac{\frac{2q_n + p_n}{q_n}}{\frac{q_n + p_n}{q_n}} = \frac{2q_n + p_n}{q_n + p_n}\\ $$

This recurrence is better than the one used in the previous solution, because it explicitly gives the numerator and denominator of $x_{n}$.

From solution2.py:

def square_root_convergents():
    pn = 1
    qn = 1
    count = 0
    for _ in range(1000):
        pn, qn = 2 * qn + pn, qn + pn
        if len(str(pn)) > len(str(qn)):
            count += 1
    return count