Odd Period Square Roots¶

SageMath can compute the periods of these continued fractions if you ask it nicely, but it's pretty slow since we have to construct a new quadratic field on every loop.

In [1]:
odd_period_sqrts = set()
for N in range(1, 10001):
    if is_square(N):
        continue
        
    K.<s> = QuadraticField(N)
    if continued_fraction(s).period_length() % 2 == 1:
        odd_period_sqrts.add(N)      
        
len(odd_period_sqrts)
Out[1]:
1322

We can speed it up if we apply an algorithm for computing the repetend of continued fractions of square roots.

In [2]:
def repetend_sqrt(S):
    m, d, a0 = 0, 1, isqrt(S)
    
    repetend = []
    a = a0
    while a != 2 * a0:
        m = d * a - m
        d = (S - m^2) / d
        a = floor((a0 + m) / d)
        repetend.append(a)
        
    return repetend

To gain an intuition for this algorithm (without getting too deep into the weeds), it's helpful to consider the more general problem of finding the continued fraction of a quadratic irrational. To do this, consider the equation $$\frac{m+\sqrt{S}}{d} = a_0 + \frac{1}{r_1}$$ The first term of the continued fraction, $a_0$, is simply the floor of the left hand side, and the following terms are just the terms of the continued fraction of $r_1$. We can then use some algebra to solve for $r_1$.

$$r_1 = \frac{d\left(da_0 - m + \sqrt{S}\right)}{S-(m-da_0)^2}$$

This shows that $r_1$ is also a quadratic irrational, so we can apply this process repeatedly to determine successive terms of the continued fraction.

It is also known that the last term in the period of the continued fraction of a square root is twice the initial term, which provides a stopping condition.

In [3]:
odd_period_sqrts = {N for N in range(1, 10001) if not is_square(N) and len(repetend_sqrt(N)) % 2 == 1}
len(odd_period_sqrts)
Out[3]:
1322

Relevant sequences¶

  • Periods of continued fractions of $\sqrt{n}$: A003285

Copyright (C) 2025 filifa¶

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.