Odd period square roots
Problem 64
All square roots are periodic when written as continued fractions and can be written in the form:
For example, let us consider
If we continue we would get the following expansion:
The process can be summarised as follows:
It can be seen that the sequence is repeating. For conciseness, we use the notation , to indicate that the block (1,3,1,8) repeats indefinitely.
The first ten continued fraction representations of (irrational) square roots are:
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
Exactly four continued fractions, for , have an odd period.
How many continued fractions for have an odd period?
import math, itertools
def cf_period(r):
p = int(math.sqrt(r)) # floor of sqrt(r)
if p * p == r:
return 0 # Square number
q = 1
remainders = {}
for pos in itertools.count(1):
q = (r - (p * p)) / q
floor = int((math.sqrt(r) + p) / float(q))
p = -1 * (p - (floor * q))
if (p, q) in remainders:
return pos - remainders[p, q]
remainders[p, q] = pos
def run():
return len([x for x in range(2, 10001) if cf_period(x) % 2 == 1])