1000-digit Fibonacci number | Project Euler | Problem #25

URL to the problem page: https://projecteuler.net/problem=25

The Fibonacci sequence is defined by the recurrence relation:

Fₙ = Fₙ₋₁ + Fₙ₋₂, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5

F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.


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

#include <iostream>

using namespace std;

int main()

{

    const int k = 1000;

    int number[3][k] = { 0 }, carry, i, counter = 2;

    number[2][k - 1] = number[1][k - 1] = 1;

    while (number[0][0] == 0) {

        carry = 0;

        for (i = k - 1; i >= 0; i--) {

            number[0][i] = (number[1][i] + number[2][i] + carry) % 10;

            carry = (number[1][i] + number[2][i] + carry) / 10;

        }

        for (i = k - 1; i >= 0; i--) {

            number[2][i] = number[1][i];

            number[1][i] = number[0][i];

        }

        counter++;

    }

    cout << "Index of the first term in the Fibonacci sequence to contain 1000 digits is  =  " << counter << endl;

}



CLICK TO SEE THE OUTPUT.