프로젝트 오일러 025

피보나치 수열

피보나치 수열은 앞 두 항의 합으로 연결되는 수열로 그 크기가 기하급수적으로 증가합니다. 갈수록 급격하게 증가하기 때문에 의외로 답은 그리 크지 않을 수 있습니다. 큰 정수의 연산 기능을 활용하면 간단히 답을 구할 수 있습니다.

어떤 수가 몇자리의 수인지를 판단하기에 가장 간편한 방법은 상용로그를 구해보는 것입니다. 10 ~ 99범위의 자연수는 그 상용로그 값이 1이상 2미만입니다. 즉 1,000자리 수라면 상용로그 값이 999이상, 1,000미만이 될 것입니다.

문제에서 제시한 수열은 1, 1, 2, … 로 시작하기 때문에 n번째 항을 정확하게 지칭하는 위치를 잘 파악해야 합니다.

from math import log10

a, b, c = 1, 1, 1
while log10(a) < 999:
	a, b, c = b, a + b, c + 1
print(c)

피보나치 수열은 코딩 문제에서 자주 등장하는 소재이니 피보나치 수열과 관련한 몇 가지 흥미로운 사실을 좀 더 살펴보도록 합시다.

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

비네의 식

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

ϕ = (1 + 5) \div 2

여기서 $ϕ$ 는 황금비( $(1 + 5) /2$ 이고, n번째 피보나치 항은 다음 식으로 계산할 수 있습니다.

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

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

ϕ lo g_{10} (ϕ^{n} / 5) n \cdot lo g_{10} ϕ - lo g_{10} 5 /2 n n \geq 4781.859270753068... = (1 + 5) /2 \geq 999 \geq 999 \geq (999 + lo g_{10} 5 /2) / lo g_{10} ϕ

이 조건을 만족하는 가장 작은 자연수 n은 4782입니다.

from math import log10

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