# Euler Solution 64

### From ProgSoc Wiki

All square roots are periodic when written as continued fractions

The first ten continued fraction representations of (irrational) square roots are:

- √2=[1;(2)], period=1
- √3=[1;(1,2)], period=2
- √5=[2;(4)], period=1
- √6=[2;(2,4)], period=2
- √7=[2;(1,1,1,4)], period=4
- √8=[2;(1,4)], period=2
- √10=[3;(6)], period=1
- √11=[3;(3,6)], period=2
- √12= [3;(2,6)], period=2
- √13=[3;(1,1,1,1,6)], period=5

Exactly four continued fractions, for N ≤ 13, have an odd period.

How many continued fractions for N ≤ 10000 have an odd period?

# Solutions

## Python by Althalus

Runtime: 1.511s

from math import floor def cf(D): m = [0,] d = [1,] a = [floor(D**0.5),] for n in xrange(0,10000): # a is one of the digits in the period. (Now how can we identify a pattern in a?) # http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html # It looks like we can find the END of the sequence when a[n] = 2*a[0]. if a[n] == 2*a[0]: return len(a[0:n]) m.append(int( (d[n]*a[n]) - m[n] )) d.append(int( (D - (m[n+1])**2)/d[n] )) a.append(int( floor((a[0]+m[n+1])/d[n+1]) )) count = 0 for x in range (2,10001): if not (x**0.5 == int(x**0.5)): period = cf(x) if period & 1: count += 1 print count