Problem 64

Resources

Wolfram MathWorld was incredibly helpful for this problem. I used their articles on “Continued Fractions” and “Periodic Continued Fractions”.

Comments

This problem was giving me troubles for a long time. I understood the math behind it, and knew how to go about getting the answer; but for some reason, it just never worked. Finally, I had the program test the first half of the continued fraction against the second half. When they were equal (and the last term being twice the very first), I knew I’d found the period.

That worked until I ran across issues with rounding irrational numbers repeatedly. I pulled in the decimal module and had to set the precision really high in order to compensate. This meant it took a little longer to run that I’d have liked, but it gave me the correct answer nonetheless.

Code

from math import *
from decimal import *
getcontext().prec = 1000
bound = 10000

def periodlength(sqrt):
	r = []
	a = []
	r.append(sqrt)
	a.append(Decimal(floor(r[0])))
	while True:
		for i in range(2):
			r.append(1/Decimal(r[-1]-a[-1]))
			a.append(int(floor(r[-1])))
			del r[0]
		Lh = (len(a)-1)/2
		if a[1:1+Lh] == a[1+Lh:] and a[-1] == 2*a[0]:
			r = []
			a = []
			return Lh


count = 0
for n in range(bound+1):
	sqrt_n = n**Decimal(0.5)
	if sqrt_n%1 == 0:
		continue
	else:
		period = periodlength(sqrt_n)
		if period%2 == 1:
			print n, period
			count += 1

print count