Project Euler 64 – Finding periodic fractions of square roots

by Rob on December 17, 2011

in Code Samples,Project Euler,programming

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 }

Project Euler 80 : Calculating the digital sum of the decimals of irrational square roots
December 28, 2011 at 7:22 pm

{ 0 comments… add one now }

Leave a Comment

Previous post:

Next post: