프로젝트 오일러 104번

The Fibonacci sequence is defined by the recurrence relation:

\({\rm F}_n = {\rm F}_{n-1} + {\rm F}_{n-2}, \) where \({\rm F}_1 =1 \) and \({\rm F}_2 = 1\)

It turns out that \(\rm F_{541}\), which contains \(113\) digits, is the first Fibonacci number for which the last nine digits are \(1-9\) pandigital (contain all the digits \(1\) to \(9\), but bot necessarily in order). And \(\rm F_{2749}\), which contains \(575\) digits, is the first Fibonacci number for which the first nine digits are \(1-9\) pandigital.

Given that \({\rm F}_k\) is the first Fibonacci number for which the first nine digits AND the last nine digits are \(1-9\) pandigital, find \(k\).

---

피보나치 수열의 일반항을 \({\rm F}_n\) 이라고 하면 다음과 같은 점화식을 얻을 수 있다.

\({\rm F}_n = {\rm F}_{n-1} + {\rm F}_{n-2}, \) where \({\rm F}_1 =1 \) and \({\rm F}_2 = 1\)

점화식을 이용하여 각 항을 구하다보면 \({\rm F}_{541}\) 가 113 자리의 수가 되며 마지막 9자리가 pandigital (1부터 9까지의 자연수를 하나씩 포함하는 수, 순서는 관계없음) 이 되는 첫 번째 항이라는 것을 알 수 있다. 또한 \({\rm F}_{2749}\) 는 575 자리의 수가 되며 처음 9개의 자리가 pandigital 이 되는 첫 번째 항인것을 알 수 있다.

\({\rm F}_k\) 가 피보나치 수열의 항 중 처음 9개 자리가 pandigital이고 동시에 마지막 9자리가 pandigital 인 첫 번째 항이라고 할 때, \(k\)의 값을 구하시오.

(먼저 pandigital이 뭔지 알아야 한다. pandigital은 9자리 숫자가 순서에 상관없이 1, 2, 3, 4, 5, 6, 7, 8, 9 의 숫자로 이루어지는 것을 의미한다.)  

이 문제를 풀기 위해서는 다음 두 가지를 고려하여야 한다.

1. 피보나치 수열의 일반항 맨 뒤 9자리 숫자가 pandigital 이어야 한다.

고등학교 때 아무리 수학 공부를 안했더라도 피보나치 수열을 한 번쯤은 들어봤을 것이다. 게다가 피보나치 수열의 점화식 (이전 두 개의 항을 더하여 다음 항을 만들어내는)도 왠만하면 모두 알고 있을 것이라 생각하여 패스.

문제는 맨 뒤 9자리 숫자를 알아내는 것인데, 이것은 생각만큼 간단하다. 피보나치 수열의 일반항을 \(10^9\) 으로 나눈 나머지를 생각하면 된다. 

그렇지만 피보나치 수열이 이전 항 두개를 더하여 다음 항을 만들어내기 때문에 나중에는 그 자릿수가 엄청나게 커지게 될 것임이 자명하다. (결국 컴퓨터가 다루기에도 벅찬(?) 숫자가 되어버린다.) 그런데 가만 생각을 해 보면 우리가 필요한 것은 맨 뒤 9자리까지 아닌가? 그렇다면 굳이 엄청 나게 큰 수를 생각할 필요 없이, 모든 피보나치 수열의 일반항을 맨 뒤 9자리 즉 \(10^8\) 자리까지만 생각하면 된다. 이렇게 잘라진(\(10^9\) 자리 이상의 숫자들이 생략된) 수들을 더하여 다음항을 만들어 낸다고 하더라도 \(10^8\) 자리 까지는 정확하게 계산될 것이기 때문이다. 따라서 피보나치 수열의 일반항 중 우리는 \(10^8\) 자리 까지만을 다루기로 한다.

2. 피보나치 수열의 일반항 맨 앞 9자리 숫자가 pandigital 이어야 한다.

이 문제의 핵심은 바로 이 부분이다. 앞에서 처럼 맨 뒤 9자리는 \(10^8\) 자리까지만 잘라서 만들어낼 수 있지만, 맨 앞 9자리는 이런식으로는 만들어 낼 수 없기 때문이다. 결국 이 부분에서는 앞의 방법을 사용하지 못한다.

따라서 다른 방법을 사용해야 하는데, 이를 위해서 먼저 알아야 할 사항이 두 가지가 있다.

첫 번째는 피보나치 수열의 일반항이다. 피보나치 수열의 일반항은 다음과 같다. 

\[{\rm F}_n = \dfrac{1}{\sqrt{5}} \left \{ \left ( \dfrac{1+\sqrt{5}}{2} \right )^n - \left ( \dfrac{1-\sqrt{5}}{2} \right )^n \right \} (n=1, \; 2, \; 3, \; \cdots )\]

일반항을 어떻게 구하는지 모른다면 "피보나치 수열의 일반항" 게시물을 확인하기 바란다. 

여기서 \(\dfrac{1+\sqrt{5}}{2} \approx 1.618033988749895\) 로 \(1\) 보다 큰 수다. (우리가 알고 있는 황금비다.) 또한 \(\dfrac{1-\sqrt{5}}{2} \approx 0.6180339887498948\) 로 \(1\) 보다 작은 수다. 만약 \(n\) 이 충분히 크다고 생각을 한다면, \(\left (\dfrac{1+\sqrt{5}}{2} \right )^n\) 은 엄청나게 큰 수가 될 것이고, \(\left (\dfrac{1-\sqrt{5}}{2} \right )^n\) 은 무시할 수 있을 정도로 엄청나게 작은 양수가 될 것이다. 결국 \(n\)이 충분히 크다면 피보나치 수열의 일반항을 \({\rm F}_n = \dfrac{1}{\sqrt{5}} \left ( \dfrac{1+\sqrt{5}}{2} \right ) ^n\) 으로 생각해도 무방하다는 얘기가 된다. 특히, 우리가 필요한 것은 일반항의 맨 앞 9자리 까지 이므로 더더욱 그렇다.   

두 번째는 상용로그 지표와 가수와 관련된 내용이다. 

고등학교 때 상용로그의 지표는 자릿수와 관련이 있다고 배웠다. 즉, \(\log x\)의 지표가 \(k\) 라면 \(x\) 는 십진수로 \(k+1\) 자리의 수가 된다. 또한 자릿수가 다르더라도 숫자의 배열이 똑같다면 상용로그의 가수가 같다고 배웠다. 예를 들어, \(\log 12 = 1.0791812460476247\)이고 \(\log 120 =2.0791812460476247\)으로 지표만 자릿수에 따라서 달라지고, 가수는 동일한 것을 알 수 있다. 이것은 \(12\)와 \(120\) 이 자릿수는 다르지만 1 다음에 2가 나온다는 숫자의 배열은 동일하기 때문이다. 

이런 성질을 이용한다면 피보나치 수열의 일반항에서 맨 앞 9자리 숫자들을 추출해 내는 것도 어렵지 않게 할 수 있다. 앞에서도 언급했듯이 \(n\)이 커진다면 일반항 자체가 엄청나게 큰 수가 되기 때문에, 우리는 일반항에 상용로그를 취함으로써 계산을 단순화 시킬 수 있다. 앞에서 살펴본 \(n\)이 큰 경우의 피보나치 수열의 일반항의 양변에 상용로그를 취하면 다음과 같다. 

\[ \log {\rm F}_n = n \times \log \left ( \dfrac{1+\sqrt{5}}{2} \right ) - \log \sqrt{5}\]

이 때 \(\log {\rm F}_n\) 의 지표와 가수를 각각 \(k, \; \alpha\) 라고 한다면 \(\alpha = n \times \log \left ( \dfrac{1+\sqrt{5}}{2} \right ) - \log \sqrt{5} - k\) 가 될 것이다. 만약 \(\log x = \alpha\) 라고 한다면 \(x\) 는 피보나치 수열의 일반항과 숫자의 배열은 똑같으면서 정수 부분이 한 자리인 수가 될 것이다. (지표가 0이 되었으므로)

만약 다음처럼 \(\log x\)의 지표를 \(8\) 로 만들어 주면 어떻게 될까?

\(\log x = \alpha + 8 = n \times \log \left ( \dfrac{1+\sqrt{5}}{2} \right ) - \log \sqrt{5} - k +8\)

이렇게 되면 피보나치 수열의 일반항과 숫자의 배열은 똑같으면서 정수 부분이 9자리 인 수가 될 것이다. (지표가 8이 되었으므로)

따라서 \( x = 10^{ n \times \log \left ( \frac{1+\sqrt{5}}{2} \right ) - \log \sqrt{5} - k +8}\) 의 정수부분은 우리가 찾던 바로 피보나치 수열의 맨 앞 9자리로 이루어진 수가 될 것이다.

이렇게 생각하면 큰 수를 다루지 않으면서 쉽게 피보나치 수열의 맨 앞 9자리 숫자들을 찾아낼 수 있다.

위의 두 가지 사항만 잘 이용한다면 이 문제도 쉽게 풀어낼 수 있다.