Project Euler #64 - Odd period square roots

프로젝트 오일러 64번 - 제곱근을 분수로 풀었을 때 주기가 홀수인 경우는?

모든 수는 무한분수(continued fraction을 뭐라고 번역하는지 모르겠다)로 표현할 수 있다. 자연수의 제곱근은 continued fraction에서 일정한 주기를 갖는데, 이 주기가 짝수일 수도 있고 홀수일 수도 있다. 10000 이하 자연수 중 주기가 홀수인 경우는 몇 번?

continued fraction은 57번에서 처음 나왔다. 이 때는 대충 넘어갈 수 있었는데, 64번과 그 이후 문제들을 풀려면 continued fraction만드는 법을 제대로 알아야 한다.
문제에서 예로 든 sqrt(23)의 전개가 바로 이해가 되면 good, 그렇지 않으면 아래의 과정을 차근차근 따라가 보는 걸로..
(열심히 타이핑하다가 너무 번거로워서 연습장에 쓰는 걸로.. )

분자, 분모를 뒤집고, 자기보다 작은 가장 큰 수를 찾고, 켤레수를 곱하고, 약분하는 과정을 반복하다가 앞에서 나왔던 것과 같은 패턴을 찾으면 끝.
한가지.. 언제나 약분이 되니까 소인수 분해 과정 거치지 않고 나누어 버렸다.(왜 그런지는 모르겠다)

이걸 코드로 구현하면 이렇게 된다.

from math import sqrt

# (sqrt(a)-b)/c
def findnext(a,b,c):
    h = int(c/(sqrt(a)-b))
    return h, a, h*(a-b*b)/c - b, (a-b*b)/c

def period(n):
    if sqrt(n) == int(sqrt(n)): return 0
    rs = 0
    first = int(sqrt(n))
    a,b,c = (n,first,1)
    while (a,b,c)!=(n,first,1) or rs == 0:
        h,a,b,c = findnext(a,b,c)
        rs+= 1
    return rs%2

result = 0
for i in range(2,10001):
    result += period(i)

print result

실행 시간은 0.35초