@@ -0,0 +1,1283 @@
+#!/usr/bin/env python%0A#-*-coding:utf-8-*-%0A%0A'''%0AThe first ten continued fraction representations of (irrational) square roots are:%0A%0A%E2%88%9A2=%5B1;(2)%5D, period=1%0A%E2%88%9A3=%5B1;(1,2)%5D, period=2%0A%E2%88%9A5=%5B2;(4)%5D, period=1%0A%E2%88%9A6=%5B2;(2,4)%5D, period=2%0A%E2%88%9A7=%5B2;(1,1,1,4)%5D, period=4%0A%E2%88%9A8=%5B2;(1,4)%5D, period=2%0A%E2%88%9A10=%5B3;(6)%5D, period=1%0A%E2%88%9A11=%5B3;(3,6)%5D, period=2%0A%E2%88%9A12= %5B3;(2,6)%5D, period=2%0A%E2%88%9A13=%5B3;(1,1,1,1,6)%5D, period=5%0A%0AExactly four continued fractions, for N %E2%89%A4 13, have an odd period.%0A%0AHow many continued fractions for N %E2%89%A4 10000 have an odd period?%0A'''%0A%0Aimport math%0Aimport timeit%0A%0A%0Adef make_proper(x, m, n):%0A    a = int(math.sqrt(x)+m)/n%0A    m -= a*n%0A    return a, m%0A%0A%0Adef inverse_rationalize(x, m, n):%0A    n = (x-m**2)/n%0A    return n, -m%0A%0A%0Adef calc(x, m, n):%0A    pairs = %5B%5D%0A    while True:%0A        a, m = make_proper(x, m, n)%0A        n, m = inverse_rationalize(x, m, n)%0A        if %5Ba, n, m%5D in pairs:%0A            return pairs%5B1:%5D%0A        else:%0A            pairs.append(%5Ba, n, m%5D)%0A%0A%0Adef loop(n):%0A    odd_period = 0%0A    for i in range(1, n+1):%0A        if math.sqrt(i) == int(math.sqrt(i)):%0A            continue%0A        if len(calc(i, 0, 1))%252 == 1:%0A            odd_period += 1%0A    return odd_period%0A%0A%0Aif __name__ == '__main__':%0A    print loop(10000)%0A    print timeit.Timer('problem_064.loop(10000)', 'import problem_064').timeit(1)%0A

add problem 064