자연수 n의 제곱근은 연분수 형태로 나타낼 수 있다. 정수부와 실수부를 각각 나눈다고 생각하고 n의 제곱근을 넘지 않는 정수와 실수부의 합으로 나눈 후, 실수부를 분자가 1이 되는 분수의 형태로 바꾼다. 즉 실수부의 역수를 다시 정수부와 실수부로 나누는 작업을 반복하면서 연분수로 전개한다. 그 과정은 아래와 같이 단계를 일반화 할 수 있다.
위 계산 과정으로부터 초기값 및 점화식을 아래와 같이 얻을 수 있다.
위 점화식을 사용하여, A, B, C의 다음 항을 각각 구해나간다. 이 때 완전 제곱인 형태이거나, 이전의 a, b, c 값의 조합이 다시 반복되면 순환마디를 발견한 것이라고 보면 된다.
def sqrt(n: int) -> list[int]:
M = int(n ** .5)
if M * M == n:
return [M]
cache = set()
res, a, b, c = [], M, -M, 1
while not ((a, b, c) in cache or b * b == n):
res.append(a)
cache.add((a, b, c))
A = (c * (M - b)) // (n - b**2)
B = -b - (A * (n - b**2) // c)
C = (n - b**2) // c
a, b, c = A, B, C
return res
sqrt(23)
# [4, 1, 8, 1, 3] --> [4; (1 8 1 3)]# e064 : 연분수 전개의 주기가 홀수인 수의 개수
%%time
xs = map(lambda x: len(sqrt(x + 1)), range(10000))
sum(1 for x in xs if x % 2 == 0)
# 1322
# 266ms