Project Euler Problem 64 Solution

Question

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

N=a0+1a1+1a2+1a3+...\sqrt{N} = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + ...}}}

For example, let us consider 23\sqrt{23}:

23=4+234=4+11234=4+11+2337\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:

23=4+11+13+11+18+...\sqrt{23} = 4 + \frac{1}{1 + \frac{1}{3 + \frac{1}{1 + \frac{1}{8 + ...}}}}

The sequence is repeating. For conciseness, we use the notation 23=[4;(1,3,1,8)]\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:

2=[1;(2)],period=13=[1;(1,2)],period=25=[2;(4)],period=16=[2;(2,4)],period=27=[2;(1,1,1,4)],period=48=[2;(1,4)],period=210=[3;(6)],period=111=[3;(3,6)],period=212=[3;(2,6)],period=213=[3;(1,1,1,1,6)],period=5 \begin{aligned} \sqrt{2} &= [1;(2)], \, \mathrm{period}=1 \\ \sqrt{3} &= [1;(1,2)], \, \mathrm{period}=2 \\ \sqrt{5} &= [2;(4)], \, \mathrm{period}=1 \\ \sqrt{6} &= [2;(2,4)], \, \mathrm{period}=2 \\ \sqrt{7} &= [2;(1,1,1,4)], \, \mathrm{period}=4 \\ \sqrt{8} &= [2;(1,4)], \, \mathrm{period}=2 \\ \sqrt{10} &= [3;(6)], \, \mathrm{period}=1 \\ \sqrt{11} &= [3;(3,6)], \, \mathrm{period}=2 \\ \sqrt{12} &= [3;(2,6)], \, \mathrm{period}=2 \\ \sqrt{13} &= [3;(1,1,1,1,6)], \, \mathrm{period}=5 \\ \end{aligned}

Exactly four continued fractions, for N13N \leq 13, have an odd period.

How many continued fractions for N10000N \leq 10000 have an odd period?

Haskell