프로젝트 오일러 025

문제

25번 문제

피보나치 수열에서 처음으로 1000자리가 되는 항은 몇 번째?

사이냅소프트

피보나치 수열

이번 문제에서도 피보나치 수열이 다시 등장했습니다. 피보나치 수열이 급격히 증가하기는 하지만, 이번에는 자릿수가 1,000을 넘을 때까지 더해봐야 합니다. 지금까지 구현해본 바로는 두 가지 방법이 있습니다. 하나는 파이썬의 큰 정수 연산 기능을 이용하는 방법과 다른 하나는 직접 구현한, 큰 수 덧셈이 있습니다. 사실 어떤 방법을 사용하든 이 문제는 그리 오랜 시간이 걸리지는 않을 것입니다.

💡피보나치 수열을 다룰 때에는 문제마다 첫 항과 둘째 항이 제각각인 경우가 종종 있습니다. 여기서는 1, 1, 2,∙∙∙ 로 시작합니다. n = 3 일 때 2입니다.

from math import log10

def solve():
  a, b, n = 1, 1, 1
  while log10(a) < 999:
    a, b, n = b, a + b, n + 1
  print(n)

solve()

그런데, 피보나치 수열과 관련하여 알려진 흥미로운 사실이 몇 개 있습니다.

• 연속한 두 피보나치 수의 비율은 황금비에 수렴합니다.
• 피보나치 수열을 정사각형 형태로 배치할 때, 대각선의 합은 피보나치 수가 됩니다.
• 1부터 n번째까지 피보나치 수의 제곱의 합은, n번째 피보나치 수와 그 다음 피보나치 수의 곱과 같습니다.
• a번째 피보나치 수 F_a와 b번째 피보나치 수 F_b의 최대공약수는, a와 b의 최대공약수를 g라할 때, F_g와 같습니다.
• 피보나치 수열은 어떤 수로 나눌 때 나머지가 일정한 주기를 이룹니다. 예를 들어 3으로 나눈 나머지는 1,1,2,0,2,2,1,0 패턴이 반복됩니다.

비네의 식

이웃한 피보나치 수의 비가 황금비에 근접한다고 했습니다. 황금비가 들어가는 식을 이용해서 피보나치 수열의 일반항을 구하는 공식을 만들 수 있습니다. 이 식은 처음에 레온하르트 오일러가 발견하였으나 잊혀졌다가, 비네라는 수학자에 의해 재발견되었습니다. 그래서 비네의 식이라고 부릅니다.

phi를 황금비[ 1 + √5) / 2 ]라 할 때, n 번째 피보나치 항은 다음과 같이 계산합니다.

phi = (1 + √5) / 2
f(n) = (phi^n - (1 - phi)^n) / √5

자 이때 (1 - phi)는 -0.7 정도 되는 값이고, 이 값은 n이 어느 정도만 커져도 0에 가까워지기 때문에 무시할 수 있습니다. 이 항을 무시하면 식이 간단해져서, f(n) = phi ^ n / √5 가 됩니다. 이 값이 1,000자리가 되려면 여기에 상용로그를 씌우면 그 값이 999이 상이어야 합니다. 그 때의 부등식을 만족하는 가장 작은 n을 찾으면 됩니다.

log_10 (phi^n / √5) >= 999
n∙log_10(phi) - log_10(5)/2 >= 999
n >= (999 + log_10(5) / 2) / log_10(phi)
n >= 4781.859270753068

이 계산은 파이썬으로도 할 수 있습니다. 이 조건을 만족하는 가장 작은 정수 n을 찾으면 됩니다.

from math import log10

phi = (1 + 5 ** 0.5) / 2
limit = (999 + log10(5) / 2) /log10(phi)
print(int(limit + 0.5))