# Euler Solution 64

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.
if a[n] == 2*a:
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+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
```