Problem 25

题目发布于 2002-08-31 翻译更新于 2025-03-16

Problem 25

$1000$ -digit Fibonacci Number

The Fibonacci sequence is defined by the recurrence relation:
$F_{n} = F_{n - 1} + F_{n - 2}$ , where $F_{1} = 1$ and $F_{2} = 1$ .

Hence the first 12 terms will be:
$\begin{aligned} F_{1} & = 1 \\ F_{2} & = 1 \\ F_{3} & = 2 \\ F_{4} & = 3 \\ F_{5} & = 5 \\ F_{6} & = 8 \\ F_{7} & = 13 \\ F_{8} & = 21 \\ F_{9} & = 34 \\ F_{10} & = 55 \\ F_{11} & = 89 \\ F_{12} & = 144 \end{aligned}$

The $12$ th term, $F_{12}$ , is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain $1000$ digits?

$1000$ 位斐波那契数

斐波那契数列是按如下递归定义的数列：
$F_{n} = F_{n - 1} + F_{n - 2}$ ，且 $F_{1} = 1$ ， $F_{2} = 1$ 。

因此斐波那契数列的前12项分别是：
$\begin{aligned} F_{1} & = 1 \\ F_{2} & = 1 \\ F_{3} & = 2 \\ F_{4} & = 3 \\ F_{5} & = 5 \\ F_{6} & = 8 \\ F_{7} & = 13 \\ F_{8} & = 21 \\ F_{9} & = 34 \\ F_{10} & = 55 \\ F_{11} & = 89 \\ F_{12} & = 144 \end{aligned}$

在斐波那契数列中，第一个包含三位数字的是第 $12$ 项 $F_{12}$ 。

在斐波那契数列中，第一个包含 $1000$ 位数字的是第几项？

10 comments

Anonymous

Markdown is supported

Stardustencommentedabout 4 years ago

Mathematica

NestWhile[#+1&,1,Fibonacci[#]<=10^999&]

liiuhongbocommentedalmost 4 years ago

#include<iostream>
using namespace std;

int a = 0, b = 1, num[2][1005] = { {1, 1}, {1, 1} };

int func(int x, int y) {
    num[y][0] = num[x][0];
    for (int i = 1; i <= num[y][0]; i++) {
        num[y][i] += num[x][i];
        if (num[y][i] > 9) {
            num[y][i + 1] += num[y][i] / 10;
            num[y][i] %= 10;
            if (num[y][0] == i) num[y][0]++;
        }
    }
    return num[y][0] == 1000;
}

int main() {
    cout << (sizeof(num[0]) / sizeof(int)) << endl;


    for (int i = 3; 1; i++) {
        if (func(b, a)) {
            cout << i << endl;
            break;
        }
        swap(a, b);
    }
    return 0;
}

jinyiliucommentedalmost 4 years ago

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


n = 1
while len(str(fib(n))) < 1000:
    n += 1

p-gpcommentedabout 3 years ago

#include <stdio.h>
#define M 1000

int add(int *ver1, int *ver2);

int main(){
    int a[M+2]={1,1}, b[M+2]={1,1}, cnt=0, co=2;

    while(cnt<M){
        co++;
        cnt=add(a,b);
    }

    printf("f(%d):", co);
    if(co%2==1){
        for(int i=a[0]; i>0; --i){
            i%100==0?printf("\n%d", a[i]):printf("%d", a[i]);
        }
    }else{
        for(int i=b[0]; i>0; --i){
            i%100==0?printf("\n%d", b[i]):printf("%d", b[i]);
        }
    }

    return 0;
}

int add(int *ver1, int *ver2){
    static int count=3;               
    int arr[M+2]={0}, up=0, ad=0;
    int m=ver1[0]>ver2[0]?ver1[0]:ver2[0];

    for(int i=1; i<=m; ++i){
        if((ad=ver1[i]+ver2[i]+up-10)>=0){
            up=1;
            arr[i]=ad;
            m=i==m?m+1:m;
        }else{
            arr[i]=ad+10;
            up=0;
        }
    }
    arr[0]=m;

    if(count%2==1){
        for(int i=0; i<=arr[0]; ++i){
            ver1[i]=arr[i];
        }
    }else{
        for(int i=0; i<=arr[0]; ++i){
            ver2[i]=arr[i];
        }
    }
    count++;

    return m;
}

zhou-ying-wancommentedabout 3 years ago

#include
#include

using namespace std;
const int N = 10000;

int f[N];

int fabonacci(int u)
{
f[1]=1,f[2]=1;
for(int i =3;i<=u;i++)
{
f[i]=f[i-1]+f[i-2];
}
return f[u];
}

int main()
{
int n;
cin>>n;

cout<<fabonacci(n);
return 0;

}

oldtommmycommentedabout 3 years ago

import java.math.BigInteger;

public class T25 {
    public static void main(String[] args) {

        BigInteger[] fab = new BigInteger[10000];
        fab[1] = BigInteger.ONE;
        fab[2] = BigInteger.ONE;
        for (int i = 3; i < 10000; i++) {
            fab[i] = fab[i-1].add(fab[i-2]);
            if (String.valueOf(fab[i]).length()>=1000){
                System.out.println(i); //4782
                break;
            }
        }
    }
}

182663823commentedalmost 3 years ago

#include
using namespace std;

int func(int *num1, int *num2) {
num1[0] = num2[0];

for(int i = 1; i <= num1[0]; i++) {
    num1[i] += num2[i];
    if(num1[i] > 9) {
        num1[i + 1] += num1[i] / 10;
        num1[i] %= 10;
        if(i == num1[0])
            num1[0]++;
    }
}
return num1[0] == 1000;

}

int main() {
int num[2][1005] = {{1, 1}, {1, 1}};
int a = 0, b = 1;

for(int i = 1; ;i++) {
    if(func(num[a], num[b])) {
        cout << i << endl;
        break;
    }
    swap(a, b);
}

return 0;

}

weisuscommentedalmost 3 years ago

Mathematica

(* 不再赘述如何求斐波那契数列 *)

NestWhile[# + 1 &, 1,
 (Fibonacci[#] // IntegerLength) != 1000 &]

xiaodouzi666commentedabout 2 years ago

#include
using namespace std;

void add(int *n1, int *n2) {
n2[0] = n1[0];
for (int i = 1; i <= n2[0]; i++) {
n2[i] += n1[i];
if (n2[i] > 9) {
n2[i + 1] += n2[i] / 10;
n2[i] %= 10;
if (n2[0] == i) {
n2[0]++;
}
}
}
}

int main() {
int num[2][1005] = {{1, 1}, {1, 1}}, a = 0, b = 1; //第一个维度表示第几个数字，第二个维度表示这个数字是什么; a表示后面一个数字，b表示前面一个数字
for (int i = 3; 1; i++) {
add(num[a], num[b]);
if (num[b][0] >= 1000) {
cout << i << endl;
break;
}
swap(a, b);
}

return 0;

}

AdwardAllancommentedover 1 year ago

using Combinatorics

findfirst(x->x>=1000,1:10000 .|> fibonaccinum .|> digits .|> length) #4782

Problem 25

1000-digit Fibonacci Number

1000位斐波那契数

Mathematica

Mathematica

$1000$ -digit Fibonacci Number

$1000$ 位斐波那契数