http://projecteuler.net/problem=64
This site has a good background on continued fractions, which I used as a blueprint to code my solution.
# Euler 64
import math
def cfRoot(n):
answer = []
#step 1: find nearest square root
first = int(math.sqrt(n))
if n == first * first:
return [first]
else:
m = first
answer.append(m)
#step 2 - reduce to new numerator and denom
last = answer[-1]
denom = n - last*last
numRem = last
while denom != 1:
coef = (first + numRem) / denom
answer.append(coef)
tempNum = denom
tempRem = coef * denom - numRem
tempDenom = n - int(math.pow((tempRem),2))
tempDenom /= tempNum
denom = tempDenom
numRem = tempRem
final = numRem + answer[0]
answer.append(final)
return answer
numberOddPeriod = 0
for i in range(2,10001):
temp = cfRoot(i)
tlen = len(temp)
if tlen > 1:
period= tlen - 1
if period % 2 == 1:
numberOddPeriod += 1
## print i, temp, numberOddPeriod
print "the answer is ", numberOddPeriod
{ 1 trackback }
{ 0 comments… add one now }