프로젝트 오일러 140번

Consider the infinite polynomial series \({\rm A_G}(x) = x{\rm G_1} + x^2 {\rm G_2} + x^3 {\rm G_3} + \cdots \), where \({\rm G}_k\) is the \(k\)th term of the second order recurrence relation \({\rm G}_k = {\rm G}_{k-1} + {\rm G}_{k-2}\), \({\rm G_1}=1\), and \({\rm G}_2=4\); that is, \(1,\; 4,\; 5,\; 9,\; 14,\; 23, \; \cdots\).

For this problem we shall be concerned with values of \(x\) for which \({\rm A_G}(x)\) is a positive integer.

The corresponding values of \(x\) for the first five natural numbers are shown below.

\(x\)	\({\rm A_G}(x)\)
\(\dfrac{\sqrt{5}-1}{4}\)	\(1\)
\(\dfrac{2}{5}\)	\(2\)
\(\dfrac{\sqrt{22}-2}{6}\)	\(3\)
\(\dfrac{\sqrt{137}-5}{14}\)	\(4\)
\(\dfrac{1}{2}\)	\(5\)

We shall call \({\rm A_G}(x)\) a golden nugget if \(x\) is rational, because they become increasingly rarer; for example, the \(20\)th golden nugget is \(211345365\).

Find the sum of the first thirty golden nuggets.

---

\(x\) 에 대한 다항함수 \({\rm A_G}(x) = x{\rm G_1} + x^2 {\rm G_2} + x^3 {\rm G_3} + \cdots \) 에서 \({\rm G}_k\) 는 다음의 점화식을 만족시키는 수열의 제 \(k\) 번째 항이다. \[{\rm G}_k = {\rm G}_{k-1} + {\rm G}_{k-2}, \; {\rm G_1}=1,\; {\rm G_2} = 4\] 즉, 수열 \({\rm G}_k\) 는 \(1,\; 4,\; 5,\; 9,\; 14,\; 23, \; \cdots\) 과 같은 수열이다.

이 문제에서 우리는 \({\rm A_G}(x)\) 의 값이 자연수가 되게하는 \(x\) 의 값에 관심이 있다.  다음의 표는 \({\rm A_G}(x)\) 의 값이 \(1, \; 2, \; 3, \;4,\; 5\) 가 되게 하는 \(x\) 값들을 나타내고 있다.

이때, \(x\) 가 유리수이고 \({\rm A_G}(x)\) 가 자연수가 되는 경우의 \({\rm A_G}(x)\) 를 우리는 금괴라고 부를 것이다. 금괴라고 부르는 이유는 가면 갈수록 \(x\) 의 값이 유리수가 되는 경우가 드물게 등장하기 때문이다. 예로, \(20\) 번째 금괴값은 무려 \(211345365\) 가 된다.

처음 \(30\) 개 금괴값의 합을 구하시오.

이 문제는 137번 문제와 완전 흡사하다. 풀이법 역시 완전 똑같다.

\[{\rm A_G}(x)=x{\rm G}_1 + x^2 {\rm G}_2 + x^3 {\rm G}_3 + x^4 {\rm G}_4 + \cdots\]

양변에 \(x\) 를 곱하면

\[x{\rm A_G}(x)=x^2{\rm G}_1 + x^3 {\rm G}_2 + x^4 {\rm G}_3 + x^5 {\rm G}_4 + \cdots\]

\({\rm A_G}(x) - x {\rm A_G}(x)\) 를 하면

\[(1-x) {\rm A_G}(x) = {\rm G}_1 x + ({\rm G_2 - G_1})x^2 + ({\rm G_3 - G_2})x^3 + ({\rm G_4 - G_3})x^4 + \cdots \]

이때, \(\rm G_1 = 1, \; G_2 - G_1 = 3 \), \({\rm G}_k - {\rm G}_{k-1} = {\rm G}_{k-2}\) 이므로 \[(1-x){\rm A_G}(x) = x + 3 x^2 + {\rm G_1}x^3 + {\rm G_2}x^ 4 \cdots \]

\(x \ne 0\) 이라면 양변을 \(x^2\) 으로 나눌 수 있고, 양변을 \(x^2\) 으로 나누면

\[\dfrac{1-x}{x^2}{\rm A_G}(x) = \dfrac{1}{x} + 3 + {\rm G_1}x + {\rm G_2}x^2 + + {\rm G_3}x^3 + \cdots\]

우변에서 \({\rm G_1}x+{\rm G_2}x^2+{\rm G_3}x^3 + {\rm F_4}x^4 + \cdots = {\rm A_G}(x)\) 이므로 

\[\dfrac{1-x}{x^2}{\rm A_G}(x) = \dfrac{3x+1}{x} + {\rm A_G}(x)\]

정리하면 \[{\rm A_G}(x) = \dfrac{3x^2+x}{1-x-x^2}\] 이 된다. 이 \({\rm A_G}(x)\) 의 값이 자연수가 되어야 하므로 그 값을 \(t\) 라고 하면 \[\dfrac{3x^2+x}{1-x-x^2} = t\]

이것을 다시 정리하면 이차방정식 \[(t+3)x^2+(t+1)x-t=0\] 을 얻는다. 근의 공식을 이용하여 \(x\) 의 값을 구해내면 \[x=\dfrac{-(t+1) \pm \sqrt{5t^2 +14t+1}}{2(t+3)}\] 가 된다. 이 \(x\) 의 값이 유리수가 되려면 \(\sqrt{5t^2+14t+1}\) 이 정수가 되면 된다. 즉, \(5t^2 +14t+1\) 이 어떤 정수의 제곱이 되면 되는 것이다.

따라서 \(t\) 의 값을 \(1\) 에서 하나씩 증가시켜 가면 \(5t^2+14t+1\) 이 완전제곱수가 되는 \(30\)번째까지의 \(t\) 를 찾아내어 다 더하면 되는 것이다.

따라서 \[5t^2 +14t +1 = m^2,\;\; (단, \;m\; 은\; 자연수)\] 라고 하고 양변에 \(5\) 를 곱해주면 \[25 t^2 + 70t +5 = 5m^2\] \[(5t+7)^2-44=5m^2\] \[(5t+7)^2 - 5m^2 = 44\] 를 얻게 된다. 여기서 \(p=5t+7\) 이라고 한다면 \[p^2 - 5m^2 = 44\]가 된다. 당연히 \(p\) 는 \(5\) 로 나누어 \(2\) 남는 수가 되어야 하므로 \(p\) 의 값을 \(2, \; 7,\; 12,\; 17,\; \cdots\) 로 변화시키면서 \(p^2 - 5 m^2 = 44\) 를 만족시키는 \((p,\;m)\) 의 순서쌍을 찾으면 \[ (17, \;7), \; (32, \; 14),\; (112, \;50),\; (217, \; 97),\; (767, \;343),\; (1487, \; 665),\; \cdots \label{a}\tag{1} \] 를 찾을 수 있다. 또한 mathworld 의 설명에 의하면 펠방정식 \(x^2 - 5y^2=1\) 에 대하여 \[\left (p^2 - 5m^2 \right ) \left ( x^2 - 5y^2 \right ) = (px \pm 5my)^2 - 5(py \pm mx)^2 = 44\] 이므로 \[(px \pm 5 my, \; py \pm mx) \label{b}\tag{2}\] 도 또 하나의 근이 된다는 것을 알 수 있다. 따라서 펠방정식 \(x^2 - 5y^2=1\) 의 근을 66번 에서 봤던 연분수 전개를 이용하여 풀게되면 \[(9, \;4), \; (161, \;72), \;(2889, \;1292),\; (51841, \;23184),\; \cdots \label{c}\tag{3}\] 를 얻을 수 있다. 

이제 \((\ref{a})\) 과 \((\ref{c})\) 을 \((\ref{b})\) 에 대입하여 새로운 근들을 얻어낸다. (단, \(p\) 가 \(5\) 로 나누어 \(1\) 남는 자연수가 될 때만 새로운 근으로 인정한다.) 이렇게 얻어낸 근들을 오름차순으로 정렬하여 \(30\) 번째까지의 \(p\) 값을 찾아내고, \(t= \dfrac{p-7}{5}\) 을 이용하여 \(t\) 를 구하여 모두 더하면 우리가 찾는 답이 된다.