Project Euler

제곱근을 연분수로 나타날 때 반복 주기가 홀수인 경우 세기

모든 제곱근은 아래와 같이 연분수로 나타낼 수 있는데, 이 때 반복되는 부분이 나타납니다.

\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

네 개의 소수 3, 7, 109, 673은 상당히 특이한 성질이 있습니다. 넷 중에 아무것이나 두 개를 골라서 어떤 쪽으로 이어붙이던지 그 결과도 소수가 됩니다. 예를 들어 7과 109를 고르면 1097, 7109 모두 소수입니다. 2, 7, 109, 673은 이런 성질을 가진 네 소수 중에서 그 합이 792로 가장 작습니다. 다섯 소수 중에 어떤 두 개를 골라 이어붙여도 소수가 되는 수들을 찾아서 그 합의 최소값을 구하세요.

구골(googol)은 10¹⁰⁰을 일컫는 말로, 1뒤에 0이 백개나 붙는 어마어마한 수입니다. 100¹⁰⁰은 1뒤에 0이 2백개나 붙으니 상상을 초월할만큼 크다 하겠습니다. 하지만 이 숫자들이 얼마나 크건간에, 각 자리수를 모두 합하면 둘 다 겨우 1밖에 되지 않습니다. a, b가 100보다 작은 자연수일 때, a^b에 대해서, 자릿수의 합이 최대인 경우, 그 값은 얼마입니까?

http://euler.synap.co.kr/prob_detail.php?id=55