(No Ratings Yet)

Project Euler Problem 64 Solution

Problem Description

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

 √N = a0 + 1 a1 + 1 a2 + 1 a3 + …

For example, let us consider √23:

 √23 = 4 + √23 — 4 = 4 + 1 = 4 + 1 1√23—4 1 + √23 – 37

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:

 a0 = 4, 1√23—4 = √23+47 = 1 + √23—37 a1 = 1, 7√23—3 = 7(√23+3)14 = 3 + √23—32 a2 = 3, 2√23—3 = 2(√23+3)14 = 1 + √23—47 a3 = 1, 7√23—4 = 7(√23+4)7 = 8 + √23—4 a4 = 8, 1√23—4 = √23+47 = 1 + √23—37 a5 = 1, 7√23—3 = 7(√23+3)14 = 3 + √23—32 a6 = 3, 2√23—3 = 2(√23+3)14 = 1 + √23—47 a7 = 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?

Solution

Runs < 1 second in Python.

 from Euler import sqrt   odd_period = 0 L = 10000   for N in range(2, L+1): r = limit = int(sqrt(N)) if limit*limit == N: continue k, period = 1, 0 while k !=1 or period == 0: k = (N - r * r) / k r = ((limit + r) / k) * k - r period += 1 if period % 2 == 1: odd_period += 1   print "Answer to PE64 =", odd_period

Discussion

2 Responses to “Project Euler Problem 64 Solution”

1. There’s an infinite loop in your code somewhere.

Posted by anonymous coward | October 15, 2012, 8:41 PM
• Don’t see any problem. You can try to change the first line to:
from math import sqrt
See if that makes a difference, otherwise you may have a typo somewhere.

Cheers!

Posted by Mike | October 29, 2012, 2:24 AM