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)]\)
\(\quad \quad \sqrt{3}=[1;(1,2)]\)
\(\quad \quad \sqrt{5}=[2;(4)]\)
\(\quad \quad \sqrt{6}=[2;(2,4)]\)
\(\quad \quad \sqrt{7}=[2;(1,1,1,4)]\)
\(\quad \quad \sqrt{8}=[2;(1,4)]\)
\(\quad \quad \sqrt{10}=[3;(6)]\)
\(\quad \quad \sqrt{11}=[3;(3,6)]\)
\(\quad \quad \sqrt{12}=[3;(2,6)]\)
\(\quad \quad \sqrt{13}=[3;(1,1,1,1,6)]\)
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?
Solution
The key to solve this problem is a function that quickly calculates the continued fraction of a certain number. As we can see from the examples, the remainders of the continued fraction expansion of \(\sqrt{N}\) always takes the form
\[x_k = \frac{\sqrt{N} + n_k}{d_k}\]
Every continued new element of this sequence is the largest integer \(a_k \leq x_k\) and since \(\left\lfloor\frac{x}{m}\right\rfloor = \left\lfloor\frac{\lfloor x\rfloor}{m}\right\rfloor\) for \(x\in\mathbb{R}, m\in\mathbb{Z}\), we can say
\[a_{k} = \lfloor x_k\rfloor = \left\lfloor\frac{\sqrt{N} + n_k}{d_k}\right\rfloor = \left\lfloor\frac{\lfloor\sqrt{N} + n_k\rfloor}{d_k}\right\rfloor = \left\lfloor\frac{a_0 + n_k}{d_k}\right\rfloor\]
It's obvious that this sequence starts with \(a_0 = \lfloor\sqrt{N}\rfloor\) and thus \(n_0=0\) and \(d_0=1\).
When we now take again the remainder, we can say
\[\begin{array}{rl} x_k &= \frac{\sqrt{N} + n_k}{d_k}\\ &= a_k + \frac{1}{x_{k+1}}\\ &= a_k + \frac{d_{k+1}}{\sqrt{N} + n_{k+1}}\\ &= \frac{a_k\sqrt{N} + a_kn_{k+1} + d_{k+1}}{\sqrt{N} + n_{k+1}} \end{array} \]
From which follows that
\[\begin{array}{rrl} & \frac{\sqrt{N} + n_k}{d_k} &= \frac{a_k\sqrt{N} + a_kn_{k+1} + d_{k+1}}{\sqrt{N} + n_{k+1}}\\ \Leftrightarrow & (\sqrt{N} + n_k)(\sqrt{N} + n_{k+1}) &= d_k(a_k\sqrt{N} + a_k n_{k+1} + d_{k+1})\\ \Leftrightarrow & N + \sqrt{N}n_{k+1} + \sqrt{N}n_{k} + n_kn_{k+1} &= d_ka_k\sqrt{N} + d_ka_k n_{k+1} + d_kd_{k+1} \end{array}\]
When ignoring the \(\sqrt{N}\) terms, since they are irrational we get
\[\begin{array}{rrl} \Leftrightarrow & N + n_kn_{k+1} &= d_ka_k n_{k+1} + d_kd_{k+1}\\ \Leftrightarrow & N - n^2_{k+1} &= d_kd_{k+1}\\ \Leftrightarrow & d_{k+1} &= \frac{N - n^2_{k+1}}{d_{k}} \end{array}\]
Analogously we also get
\[\begin{array}{rrl} & \frac{n_k}{d_k} & = \frac{a_kn_{k+1} + d_{k+1}}{n_{k+1}}\\ \Leftrightarrow & n_{k+1} &= a_k d_k - n_k \end{array}\]
To make the equations a bit prettier, we re-index them with \(k+1:= k\):
\[d_k = \frac{N - n^2_{k}}{d_{k-1}}\]
\[n_{k} = a_{k-1}\cdot d_{k-1} - n_{k-1}\]
and can therefore implement the recursive algorithm quite easily. Since we don't need the actual continued fraction coefficients, but only need the period length, a helper function to calculate the length is
function periodLength(N) {
let nk = 0;
let dk = 1;
let ak = Math.floor(Math.sqrt(N));
let a0 = ak;
let length = 0;
if (a0 * a0 !== N) do {
nk = ak * dk - nk;
dk = (N - nk * nk) / dk;
ak = Math.floor((a0 + nk) / dk);
length++;
} while (2 * a0 !== ak);
return length;
}To get to the final solution, we simply loop from 2 to 10,000 and count the odd numbers, which is summing the period length modulo two:
function solution(limit) {
let c = 0;
for (let i = 2; i <= limit; i++) {
c+= periodLength(i) % 2;
}
return c;
}
solution(10000);