Project Euler 64: Find the continued fractions for N ≤ 10000 have an odd period
Problem Description
All square roots are periodic when written as continued fractions and can be written in the form:
√N = a_{0} + 
1


a_{1} + 
1


a_{2} + 
1


a_{3} + … 
For example, let us consider √23:
√23 = 4 + √23 — 4 = 4 + 
1

= 4 + 
1


1
√23—4 
1 + 
√23 – 3
7 
If we continue we would get the following expansion:
√23 = 4 + 
1


1 + 
1


3 + 
1


1 + 
1


8 + … 
The process can be summarised as follows:
a_{0} = 4, 
1
√23—4 
= 
√23+4
7 
= 1 + 
√23—3
7 

a_{1} = 1, 
7
√23—3 
= 
7(√23+3)
14 
= 3 + 
√23—3
2 

a_{2} = 3, 
2
√23—3 
= 
2(√23+3)
14 
= 1 + 
√23—4
7 

a_{3} = 1, 
7
√23—4 
= 
7(√23+4)
7 
= 8 +  √23—4  
a_{4} = 8, 
1
√23—4 
= 
√23+4
7 
= 1 + 
√23—3
7 

a_{5} = 1, 
7
√23—3 
= 
7(√23+3)
14 
= 3 + 
√23—3
2 

a_{6} = 3, 
2
√23—3 
= 
2(√23+3)
14 
= 1 + 
√23—4
7 

a_{7} = 1, 
7
√23—4 
= 
7(√23+4)
7 
= 8 +  √23—4 
It can be seen that the sequence is repeating. For conciseness, we use the notation √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=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?
Analysis
This one appeared easier than it was. It wasn’t until I read this article on computing square roots using a continued fraction expansion that I could code it for finding a solution.
Project Euler 64 Solution
Runs < 0.150 seconds in Python 2.7.Use this link to get the Project Euler 64 Solution Python 2.7 source.
Afterthoughts

No afterthoughts yet.
Discussion
No comments yet.