Euler #64

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

Method for calculation of square root continued fraction is taken from  http://web.math.princeton.edu/mathlab/jr02fall/Periodicity/mariusjp.pdf

	#!/usr/bin/env python
	def period(n):
	a_0 = int(n ** 0.5)
	if a_0 * a_0 == n:
	return 0
	b, b_0 = a_0, a_0
	c, c_0 = n - a_0*a_0, n - a_0*a_0
	res = 0
	while True:
	a = (a_0 + b) / c
	b = a * c - b
	c = (n - b * b) / c
	res += 1
	if b == b_0 and c == c_0:
	break
	return res
	if __name__ == '__main__':
	print sum(
	map(lambda n: period(n) % 2,
	xrange(2, 10001)))

view raw 64.py hosted with ❤ by GitHub