Odd Period Square Roots

All square roots are periodic when written as continued fractions and can be written in the form:

$\displaystyle \quad \quad \sqrt{N}=a_0+\frac 1 {a_1+\frac 1 {a_2+ \frac 1 {a3+ \dots}}}$

For example, let us consider $\sqrt{23}:$
$\quad \quad \sqrt{23}=4+\sqrt{23}-4=4+\frac 1 {\frac 1 {\sqrt{23}-4}}=4+\frac 1 {1+\frac{\sqrt{23}-3}7}$

If we continue we would get the following expansion:

$\displaystyle \quad \quad \sqrt{23}=4+\frac 1 {1+\frac 1 {3+ \frac 1 {1+\frac 1 {8+ \dots}}}}$

The process can be summarised as follows:

$\quad \quad a_0=4, \frac 1 {\sqrt{23}-4}=\frac {\sqrt{23}+4} 7=1+\frac {\sqrt{23}-3} 7$
$\quad \quad a_1=1, \frac 7 {\sqrt{23}-3}=\frac {7(\sqrt{23}+3)} {14}=3+\frac {\sqrt{23}-3} 2$
$\quad \quad a_2=3, \frac 2 {\sqrt{23}-3}=\frac {2(\sqrt{23}+3)} {14}=1+\frac {\sqrt{23}-4} 7$
$\quad \quad a_3=1, \frac 7 {\sqrt{23}-4}=\frac {7(\sqrt{23}+4)} 7=8+\sqrt{23}-4$
$\quad \quad a_4=8, \frac 1 {\sqrt{23}-4}=\frac {\sqrt{23}+4} 7=1+\frac {\sqrt{23}-3} 7$
$\quad \quad a_5=1, \frac 7 {\sqrt{23}-3}=\frac {7 (\sqrt{23}+3)} {14}=3+\frac {\sqrt{23}-3} 2$

$\quad \quad a_6=3, \frac 2 {\sqrt{23}-3}=\frac {2(\sqrt{23}+3)} {14}=1+\frac {\sqrt{23}-4} 7$
$\quad \quad a_7=1, \frac 7 {\sqrt{23}-4}=\frac {7(\sqrt{23}+4)} {7}=8+\sqrt{23}-4$

It can be seen that the sequence is repeating. For conciseness, we use the notation $\sqrt{23}=[4;(1,3,1,8)]$, to indicate that the block (1,3,1,8) repeats indefinitely.
The first ten continued fraction representations of (irrational) square roots are:

$\quad \quad \sqrt{2}=[1;(2)]$, period=$1$
$\quad \quad \sqrt{3}=[1;(1,2)]$, period=$2$
$\quad \quad \sqrt{5}=[2;(4)]$, period=$1$
$\quad \quad \sqrt{6}=[2;(2,4)]$, period=$2$
$\quad \quad \sqrt{7}=[2;(1,1,1,4)]$, period=$4$
$\quad \quad \sqrt{8}=[2;(1,4)]$, period=$2$
$\quad \quad \sqrt{10}=[3;(6)]$, period=$1$
$\quad \quad \sqrt{11}=[3;(3,6)]$, period=$2$
$\quad \quad \sqrt{12}=[3;(2,6)]$, period=$2$
$\quad \quad \sqrt{13}=[3;(1,1,1,1,6)]$, period=$5$

Exactly four continued fractions, for $N \le 13$, have an odd period.
How many continued fractions for $N \le 10\,000$ have an odd period?

To find the number of continued fractions for $N \le 10,000$ that have an odd period, let’s use the following algorithmic approach:

We’re going to check for every number how many fractions have an odd period.

So let’s start:

1. Set up variables to keep track of your numbers and counts.
“`python
period = 0
odd_periods = 0
“`
2. Try to calculate the number of fractions for all numbers between 2 and 10000.
“`python
for N in range(2, 10001):
“`
3. Skip the perfect square numbers, because the square root of a perfect square is an integer, and the continued fraction representation doesn’t repeat.
“`python
if int(N**.5)**2 == N:
continue
“`
4. Otherwise, start the calculation according to the formula described above.
“`python
a0 = int(N**.5)
d = a0
m = 0
a = a0
“`
5. The calculation of a continues until we get back to the start. So, we should run a loop until we reach `2*a0`, which signifies the repeating phase.
“`python
while a != 2*a0:
m = d*a – m
d = (N – m**2) // d
a = (a0 + m) // d
period += 1
“`
6. Check if the period length for this number is odd. If it is, increase the count.
“`python
if period % 2 == 1:
odd_periods += 1
“`
7. Reset the period counter for the next number.
“`python
period = 0
“`
Once this loop completes, `odd_periods` will contain the total count of square roots with an odd period.

This algorithm is based on the mathematical formulation of continued fractions and takes advantage of several properties of square roots and the periodicity of their continued fraction representations. In particular, it relies on the fact that the continued fraction representation of a square root repeats after a certain length, called the period, and that the period is odd if the number of terms before the repetition begins is odd.

More Answers: