프로젝트 오일러 137번

Consider the infinite polynomial series \({\rm A_F}(x)=x{\rm F}_1 + x^2 {\rm F}_2 + x^3 {\rm F}_3 + \cdots\), where \({\rm F}_k\) is the \(k\)th term in the Fibonacci sequence: \(1, \;1, \;3, \;5, \; 8,\; \cdots\); that is, \({\rm F}_k = {\rm F}_{k-1} + {\rm F}_{k-2},\;\; {\rm F}_1 = 1,\) and \({\rm F}_2=1\).

For this problem we shall be interested in values of \(x\) for which \({\rm A_F}(x)\) is a positive integer.

Surprisingly \(\begin{split} {\rm A_F} \left (\dfrac{1}{2} \right ) &= \left (\dfrac{1}{2} \right ) \times 1 + \left ( \dfrac{1}{2} \right )^2 \times 1 + \left ( \dfrac{1}{2} \right )^3 \times 2 + \left ( \dfrac{1}{2} \right ) ^4 \times 3 + \left ( \dfrac{1}{2} \right ) ^5 \times 5 + \cdots \\ &= \dfrac{1}{2} + \dfrac{1}{4} + \dfrac{2}{4} + \dfrac{3}{16} + \dfrac{5}{32} + \cdots \\ &= 2 \end{split}\)

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

\(x\)	\({\rm A_F}(x)\)
\(\sqrt{2} -1\)	\(1\)
\(\dfrac{1}{2}\)	\(2\)
\(\dfrac{\sqrt{13}-2}{3}\)	\(3\)
\(\dfrac{\sqrt{89}-5}{8}\)	\(4\)
\(\dfrac{\sqrt{34}-3}{5}\)	\(5\)

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

Find the \(15\)th golden nugget.

---

\(x\) 에 대한 함수 \({\rm A_F}(x)=x{\rm F}_1 + x^2 {\rm F}_2 + x^3 {\rm F}_3 + \cdots\) 에서 \({\rm F}_k\) 는 \(1, \;1, \;3, \;5, \; 8,\; \cdots\) 로 전개되는 피보나치 수열의 제 \(k\) 번째 항과 같다. 

이 문제에서 우리는 함수 \({\rm A_F}(x)\) 의 값이 자연수가 되게 하는 \(x\) 값들에 관심을 둘 것이다.

예를 들면, \(x= \dfrac{1}{2}\) 일 때, \({\rm A_F}(x)\) 의 값이 \(2\) 로 자연수가 된다. 

 \(\begin{split} {\rm A_F} \left (\dfrac{1}{2} \right ) &= \left (\dfrac{1}{2} \right ) \times 1 + \left ( \dfrac{1}{2} \right )^2 \times 1 + \left ( \dfrac{1}{2} \right )^3 \times 2 + \left ( \dfrac{1}{2} \right ) ^4 \times 3 + \left ( \dfrac{1}{2} \right ) ^5 \times 5 + \cdots \\ &= \dfrac{1}{2} + \dfrac{1}{4} + \dfrac{2}{4} + \dfrac{3}{16} + \dfrac{5}{32} + \cdots \\ &= 2 \end{split}\)  

위의 표는 \({\rm A_F}(x)\) 의 값이 자연수가 되게하는 처음 \(5\) 개 \(x\) 값들을 보여주고 있다.

이때, \({\rm A_F}(x)\) 의 값이 자연수가 되게 하는 \(x\) 값 중, 유리수 \(x\) 인 경우의 \({\rm A_F}(x)\) 를 금괴라 부르는데, 이것이 가면 갈수록 아주 드물게 등장하기 때문이다. 예를 들어, \(10\) 번째 금괴 \({\rm A_F}(x)\) 의 값은 \(74049690\) 이다.

\(15\) 번째 금괴의 값을 구하시오. 

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

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

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

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

\[(1-x) {\rm A_F}(x) = {\rm F}_1 x + ({\rm F_2 - F_1})x^2 + ({\rm F_3 - F_2})x^3 + ({\rm F_4 - F_3})x^4 + \cdots \]

이때, \(\rm F_1 = F_2 = 1\), \( {\rm F}_k - {\rm F}_{k-1} = {\rm F}_{k-2}\) 이므로 \[(1-x){\rm A_F}(x) = x + x^3 + x^4 + {\rm F_3}x^5 + {\rm F_4}x^ 6 \cdots \]

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

\[\dfrac{1-x}{x^2}{\rm A_F}(x) = \dfrac{1}{x} + x + x^2 + {\rm F_3}x^3 + {\rm F_4}x^4 + \cdots\]

우변에서 \(x+x^2+{\rm F_3}x^3 + {\rm F_4}x^4 + \cdots = {\rm A_F}(x)\) 이므로 

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

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

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

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

따라서 \[5t^2 +2t +1 = m^2,\;\; (단, \;m\; 은\; 자연수)\] 라고 하고 양변에 \(5\) 를 곱해주면 \[25 t^2 + 10t +1 + 4 = 5m^2\] \[(5t+1)^2+4=5m^2\] \[(5t+1)^2 - 5m^2 = -4\] 를 얻게 된다. 여기서 \(p=5t+1\) 이라고 한다면 \[p^2 - 5m^2 = -4\]가 된다. 당연히 \(p\) 는 \(5\) 로 나누어 \(1\) 남는 수가 되어야 하므로 \(p\) 의 값을 \(1, \; 6,\; 11,\; 16,\; \cdots\) 로 변화시키면서 \(p^2 - 5 m^2 = -4\) 를 만족시키는 \((p,\;m)\) 의 순서쌍을 찾으면 \[ (1, \;1), \; (11, \; 5),\; (76, \;34),\; \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 = -4\] 이므로 \[(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})\) 에 대입하여 새로운 근들을 얻어낸다. 예를 들어, \((1, \;1)\) 과 \((161,\; 72)\) 를 이용하여 새로운 근을 구하면 \((1 \times 161+5 \times 1 \times 72, \; 1 \times 72 + 1 \times 161)\) 이 새로운 근이 된다. (단, \(p\) 가 \(5\) 로 나누어 \(1\) 남는 자연수가 될 때만 새로운 근으로 인정한다.) 이렇게 얻어낸 근들을 오름차순으로 정렬하여 \(15\) 번째 \(p\) 값을 찾아내고, \(t= \dfrac{p-1}{5}\) 을 이용하여 \(t\) 를 구하면 우리가 찾는 답이 된다. 

재미있는 사실 하나!!! 

실제로 이렇게 코딩을 해 보니 \(10\) 번째까지의 금괴값은 다음과 같다. 

1   2

2   15

3   104

4   714

5   4895

6   33552

7   229970

8   1576239

9   10803704

10   74049690

그런데 저 위의 값들을 잘 살펴보니 \[\begin{split} 2 &= {\rm F_2} \times {\rm F_3} = 1 \times 2 \\ 15 &= {\rm F_4} \times {\rm F_5} = 3 \times 5 \\ 104 &= {\rm F_6} \times {\rm F_7} = 8 \times 13 \\ 714 &= {\rm F_8} \times {\rm F_9} = 21 \times 34 \\ &\;\vdots \end{split}\]

와 같은 규칙성이 있지 않은가? (우연히 발견한것 같지만 구글링을 해서 알아낸 사실이다. ^^;)

이렇게 되면 그냥 피보나치 수열의 30번째 항과 31번째 항을 곱하여 답을 얻어낼 수 있다.