피보나치 수열 계산기

앞의 두 항을 더하면 됩니다. F(0)=0, F(1)=1로 시작해 F(n) = F(n−1) + F(n−2)입니다. 재귀 없이 한 번에 구하려면 비네 공식 F(n) = (φⁿ − ψⁿ)/√5를 쓰는데, φ=(1+√5)/2이고 ψ=(1−√5)/2입니다. |ψ|가 1보다 작아 금방 0에 가까워지므로 F(n) = round(φⁿ/√5)로도 맞습니다.

부동소수점으로 φⁿ을 계산할 때 오차가 쌓이기 때문입니다. 자바스크립트의 배정밀도에서는 71번째 항에서 이미 1이 어긋납니다. 흥미로운 것은 정수로 안전한 한계인 2⁵³을 넘는 것이 79번째부터라는 점입니다. 수가 넘치기 전에 공식이 먼저 무너지는 셈이라, 정확한 값이 필요하면 BigInt로 더해 나가야 합니다.

F(1)부터 F(n)까지의 합은 F(n+2) − 1입니다. 예를 들어 1+1+2+3+5+8+13+21+34+55 = 143이고 F(12) − 1 = 144 − 1 = 143입니다. 제곱의 합도 F(n)·F(n+1)로 딱 떨어집니다.

비네 공식에서 |ψ|<1이라 ψⁿ이 사라지고 φⁿ만 남기 때문입니다. 홀수 항은 φ보다 크고 짝수 항은 작아서 위아래로 번갈아 넘나들며 좁혀 들어가고, 오차가 매번 φ² 곧 약 2.618배씩 줄어듭니다. 그래서 열몇 항만 지나도 소수 열 자리가 맞습니다.

모든 양의 정수를 이웃하지 않는 피보나치 수의 합으로 유일하게 쓰는 것입니다. 100 = 89 + 8 + 3처럼 쓰며, 큰 것부터 욕심껏 골라 빼기만 하면 그 표현이 그대로 나옵니다. 고른 것끼리 이웃하는 일이 저절로 생기지 않는 것이 이 정리의 핵심입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.