제곱근을 연분수로 나타날 때 반복 주기가 홀수인 경우 세기
모든 제곱근은 아래와 같이 연분수로 나타낼 수 있는데, 이 때 반복되는 부분이 나타납니다.
\sqrt{N} = a_0 + \frac{1}{ a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}}예를 들어서 √23을 풀어 보면,
\sqrt{23} = 4 + (\sqrt{23} - 4) = 4 + \frac{1}{(\frac{1}{\sqrt{23} - 4})} = 4 + \frac{1}{\frac{\sqrt{23} + 4}{7}} = 4 + \frac{1}{1 + \frac{\sqrt{23} - 3}{7}}같은 식으로 계속하면 아래와 같은 모양이 됩니다.
\sqrt{23} = 4 + \frac{1}{1 + \frac{1}{3 + \frac{1}{1 + \frac{1}{8 + \cdots}}}}이 과정을 상세히보면 다음과 같습니다.
\begin{array}{llll} a_0 = 4, & \frac{1}{\sqrt{23} - 4} = \frac{\sqrt{23} + 4}{7} = 1 + \frac{\sqrt{23} - 3}{7} \\ a_1 = 1, & \frac{7}{\sqrt{23} - 3} = \frac{7(\sqrt{23} + 3)}{14} = 3 + \frac{\sqrt{23} - 3}{2} \\ a_2 = 3, & \frac{2}{\sqrt{23} - 3} = \frac{2(\sqrt{23} + 3)}{14} = 1 + \frac{\sqrt{23} - 4}{7} \\ a_3 = 1, & \frac{7}{\sqrt{23} - 4} = \frac{7(\sqrt{23} + 4)}{7} = 8 + \sqrt{23} - 4 \\ a_4 = 8, & \frac{1}{\sqrt{23} - 4} = \frac{2(\sqrt{23} + 4)}{7} = 1 + \frac{\sqrt{23} - 3}{7} \\ a_5 = 1, & \frac{7}{\sqrt{23} - 3} = \frac{7(\sqrt{23} + 3)}{14} = 3 + \frac{\sqrt{23} - 3}{2} \\ a_6 = 3, & \frac{2}{\sqrt{23} - 3} = \frac{2(\sqrt{23} + 3)}{14} = 1 + \frac{\sqrt{23} - 4}{7} \\ a_7 = 1, & \frac{7}{\sqrt{23} - 4} = \frac{7(\sqrt{23} + 4)}{7} = 8 + \sqrt{23} - 4 \\ \end{array}위에서 보듯이 4라는 정수부 다음에 1, 3, 1, 8 이라는 숫자가 무한히 반복되는데, 이것을 을 √23 = [4;(1,3,1,8)] 과 같이 표시하기로 합니다. 이런식으로 해서 무리수인 제곱근들을 연분수로 나타내면 다음과 같이 됩니다.
√2=[1;(2)], 주기=1 √3=[1;(1,2)], 주기=2 √5=[2;(4)], 주기=1 √6=[2;(2,4)], 주기=2 √7=[2;(1,1,1,4)], 주기=4 √8=[2;(1,4)], 주기=2 √10=[3;(6)], 주기=1 √11=[3;(3,6)], 주기=2 √12=[3;(2,6)], 주기=2 √13=[3;(1,1,1,1,6)], 주기=5반복주기가 홀수인 경우는 N ≤ 13 일 때 모든 4번 있음을 볼 수 있습니다. 그러면 N ≤ 10000 일 때 반복 주기가 홀수인 경우는 모두 몇 번이나 있습니까?
https://euler.synap.co.kr/problem=64
모든 자연수의 제곱근은 연분수로 나타낼 수 있음이 알려져 있고, 일정한 마디가 반복적으로 나타난다. 이 문제는 1만 이하의 모든 수의 제곱근을 연분수로 표현하고, 반복주기가 홀수인 것의 개수를 세는 문제이다. 따라서 어떤 자연수의 제곱근을 연분수로 표현하는 함수를 작성하는 것이 목표가 되겠다.
반복되는 패턴을 찾기 위한 것이니, 연분수 전개에 사용되는 파라미터들의 점화식을 찾는 것이 핵심이다. 그러면 어떤 패턴이 있는지 살펴보자. 친절하게도 (왜냐하면 √2 같은 경우는 [1; ( 2 )] 로 반복주기가 1 밖에 안되기 때문이다.) 23의 제곱근을 연분수로 전개하는 방법을 문제에서 알려주고 있다.
먼저 23의 제곱근은 4와 5 사이에 있다. ( 42 < 23 < 52 ) 따라서 23의 제곱근보다 작은 최대의 정수는 4이다. 이 값을 M이라고 편의상 둔다.
\sqrt{23} = 4 + (\sqrt{23} - 4)이 식은 4를 더했다 빼는 간단한 식처럼 보이지만 정확히는 23의 제곱근을 정수부와 실수부로 구분한 것을 알 수 있다. 연분수 전개는 이런 식으로 정수부와 실수부를 구분한 후에 실수부를 분자가 1인 분수로 표시하는 것을 목표로 한다. 분자가 1인 분수로 표시해야 하기 때문에, 분모에는 괄호 부분의 역수가 들어가게 된다.
\frac{1}{\frac{1}{\sqrt{23} - 4}} = \frac{1}{\frac{\sqrt{23} + 4}{7}} \\
= \frac{1}{1 + \frac{\sqrt{23}-3}{7}}분모로 들어간 실수부의 역수에 대해서 다시 정수부와 실수부로 분리한다. 즉 연분수 전개의 과정은 다음과 같다.
- 제곱근 값을 정수부와 실수부로 분리한다.
- 실수부의 역수를 다시 정수부와 실수부로 분리하고, 이를 분자가 1인 분수의 분모로 둔다.
- 분모를 정수부와 실수부로 분리하고, 분자가 1인 분수의 분모로 둔다.
- 3의 과정을 반복한다.
k 번째 반복주기를 아래 식과 같이 나타낸다고 할 때, 실수부의 역수를 연분수로 전개해 보자.
\begin{array}{llll}
A_k & + & \frac{\sqrt{n} + B_k}{C_k} \\
\\
\frac{C_k}{\sqrt{n} + B_k} & = & A_{k+1} + \frac{\sqrt{n} + B_{k+1}}{C_{k+1}} \\
\frac{C_k}{\sqrt{n} + B_k} & = & A_{k+1} + \frac{C_k(\sqrt{n} - B_k}{n - B^2_k}- A_{k+1} \\
& = & A_{k+1} + \frac{\sqrt{n} - B_k - (A_{k+1}(n - B^2_k) / C_k)}{(n - B^2_k) / C_k}
\end{array}그리고 앞에서 예시로 보였던 23의 경우에서 이 점화식의 첫항은 어떻게 정의해야할지도 알 수 있다. 다음과 같은 점화식들을 얻을 수 있다. 점화식이 모두 나왔기 때문에 코드로 확인해보면 된다.
\begin{array}{llll}
& M & = & \lfloor \sqrt{n} \rfloor \\
& A_0 & = & M \\
& B_0 & = & -M \\
& C_0 & = & 1\\
& A_{k+1} & = & \lfloor C_{k}(M - B_k) / (n - B^2_k) \rfloor \\
& B_{k+1} & = & -B_k - (A_{k + 1}(n - B^2_k) / C_k) \\
& C_{k+1} & = & (n - B^2_k) / C_k
\end{array}반복주기를 판단하기 위해서는 (a, b, c) 의 튜플을 집합에 매번 추가하면서, 다음번 파라미터인 (A, B, C)가 집합에 포함되어 있는지를 검사하면 된다.
def sqrt(n: int) -> tuple[int, list[int]]:
M = int(n ** .5)
a, b, c = M, -M, 1
res, cache = [M], {(a, b, c)}
while b * b != n:
A = (c * (M - b) // (n - b * b))
B = -b - (A * (n - b * b) // c)
C = (n - b * b) // c
if (A, B, C) in cache:
break
a, b, c = A, B, C
cache.add((a, b, c))
res.append(a)
return res
print(sqrt(23))
# [4, 1, 3, 1, 8]
print(sqrt(4))
# [2]
print(sqrt(2))
# [1, 2]이제 1~1,000 숫자들에 대해서 반복주기를 구하고, 홀수(리턴된 리스트의 길이가 짝수) 인 것만 골라내면 된다.
%%time
xs = [len(sqrt(n + 1)) for n in range(10000)]
print(sum(1 for x in xs if x % 2 == 0))
# 1322
# 141 ms