Project Euler 25: What is the first term in the Fibonacci sequence to contain 1000 digits?

Written by on 30 January 2011

Topics: Project Euler

Back to the big numbers again in Problem 25 of Project Euler. The problem reads

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12 is the first term to contain three digits.

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

With the BigInteger class this is rather easy to brute force. So a brute force solution is one of the two solutions I will show you. The other solution is one you can use with a calculator, or if you are good at mental arithmetic, you can do it with pen and paper.

Brute Force

Finding a number with at least 1000 digits, is the same as finding a number larger than or equal to 10999, so this is the test we will use to see if the Fibonnaci number is the one we are looking for.

Other than that the solution uses three BigIntegers to store n, n-1 and n-2, and I have chosen to index them with the modulo operator, so I circulate where n is stored, so i avoid moving the numbers around a lot. Other than that there isn’t much to say about the solution, other than in C# it looks like

int i = 0;
int cnt = 2;
BigInteger limit = BigInteger.Pow(10, 999);
BigInteger[] fib = new BigInteger[3];

fib[0] = 1;
fib[2] = 1;

while (fib[i] <= limit) {
    i = (i + 1) % 3;
    cnt++;
    fib[i] = fib[(i + 1) % 3] + fib[(i + 2) % 3];
}

and the result of running the code is

The first term in the fibonnaci sequence to have more than 1000 digits is term number: 4782
Solution took 2 ms

Pretty fast and for 1000 digits it is faster than doing it by hand. However, it scales poorly unlike the next solution I will present.

Pen and Paper

It is possible to solve this exercise using pen and paper as well, due to the fact that when the Fibonacci numbers become large enough, the Fibonacci numbers converge to

where the brackets means the closest integer as stated on Wolfram. Phi is defined as the golden ratio which is approximately 1.6180. However, it is an irrational number, so I would never be able to type in all digits as there is an countably infinite amount.

Assuming that the first Fibonacci number with 1000 digits is large enough for the series to have converged we need to find the smallest integer  n which fulfils the inequality

Taking log on both sides

Isolating n

Meaning that the first Fibonacci number with 1000 digits is number 4782.

Wrapping up

I have presented you two ways, one where you can achieve the result by hand and one where you can brute force it with a small piece of C# code. The source code is as usual available for download for the latter option.

Once again I encourage you to post questions, comments, mistakes and/or other solution strategies.

18 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

    This is, without a doubt, my favorite PE problem. I love that pen & paper solution.

    Anyways, I was playing with Newton’s method and figured I could use that to solve this problem. It’s probably easier to isolate n, but this is another fun approach.

    x_{n+1}=x_n-\frac{x_n \text{Log}_{10}(\phi )-\frac{\text{Log}_{10}(5)}{2}-999}{\text{Log}_{10}(\phi )}

    And then starting with something like x0 = 100.

  2. SuprDewd says:

    The raw LaTeX was displayed instead of my beautiful math equation.
    This is what is was supposed to look like.

    Is there any way for users to render TeX here in the comments? If not, that would be an awesome future update for the blog.

  3. Kristian says:

    There wasn’t a method to do it until you asked. I didn’t want to enable it when I installed the plugin I use and then I never got around to it.

    You can encapsulate your latex formula in [latex]some formula[/latex] now such that your comment becomes

    Regarding the actual content of your comment and updating the help notes to the comment box, I will get back to that later.

  4. Kristian says:

    Getting back to the actual content of your comment…

    Yes I do believe that it is easier to isolate n than using Newton’s method. That being said, it is always fun to explore new tools and I do believe that is best done by trying to apply it to something you already know something about.

    Newton’s method is actually used quite a lot in optimization. Not as the only mean to find an optimum, but to make a step from your current position to the next.

    One thing to note about Newton’s method is that if the function behaves a bit oddly you are very likely to make an overshoot jumping back and forth over the solution. Thus it will take a very long time to converge. What is often done in optimization is to have a parameter less than 1 you multiply with the intended step so instead of

    you have

    where alpha is smaller than 1.

  5. SuprDewd says:

    Oh that’s pretty neat.

  6. Please don’t post the actual answer, it tempts to cheat ;)

  7. Kristian says:

    Been thinking about that for a while. What would you suggest I should do? Just post the solution strategy and the code and then leave out the answer?

    My big question is; would it make a difference?

  8. Yes, it would make a difference, you can just conclude the answer with “taking log on both sides and solving for n would give the answer”, this would require the viewer to solve it as an exercise and thus help in learning.

  9. SuprDewd says:

    As a first step, we could add a Show/Hide button, and leave the answer hidden by default.

  10. Kristian says:

    I will consider hiding the answer such that you will have to press a button to see the answer.

  11. Ricardo says:

    This problem is confusing, the answer is very unexpected.

    I thought that they wanted a number with 1000 digits, so for example:

    3 digits = 114
    4 digits = 1597
    5 digits = 10946

    1000 digits = ??

    How come the answer (4782) only contains 4 digits?

  12. Ricardo says:

    Nevermind, I understand now, they’re asking for the index of the number… stupid misinterpretation :}

  13. Kristian says:

    You have no idea how many questions I have read wrong and couldn’t understand why I got the wrong answer. But glad you found the reason.

  14. ggoyo says:

    instead of using fn=fn-1+fn-2 you can do this with matrix calculus :

    ( fn )=(1 1)^n-1.(f1)
    (fn-1) (1 0) (f0)

    since f1 and f0 both are equals to 1 : (1 1)^n=(fn+1 fn )
    (1 0) (fn fn-1)

  15. lince159 says:

    A good, and easy one solution is using python, we need to use dictionaries or it will takes forever recursivily!

    well my test took 0.425s quite more than C, but python is interpreted :)

    fibbonnaccinumber = {0:0, 1:1}
    def fib(n):
        if not n in fibbonaccinumber:
            fibbonaccinumber[n] = fib(n-1) + fib(n-2)
        return fibonaccinumber[n]
    
    i = 0
    while(True):
        if(len(str(fib(i)))==1000):
            print i
            break
        i = i+1
    
    

    NOTE: if you remove the break you will have all the fibonacci numbers with exactly 1000 numbers.

  16. Mark Soric says:

    Hi there! I apologize if I’m confused but I have a question regarding a statement you made when introducing the second method. You state that: the number of digits in phi form an uncountably infinite set. I’m not sure that it’s uncountable. We can index each digit in the decimal representation of phi so we have a one-to-one map from that set to the natural numbers – is that not the definition of countable?

    If I’m confused, please let me know :)

    Thanks!

  17. Kristian says:

    I have no idea what I was thinking of back when I wrote that part. However, I do believe your argument is right.

  18. Hui says:
    namespace p25
    {
        class Program
        {
            static void Main(string[] args)
            {
                // What is the first term in the Fibonacci sequence to contain 1000 digits?
                List<BigInteger> list = new List<BigInteger>();
                list.Add(1);
                list.Add(2);
                while (list.Last().ToString().Length < 1001)
                {
                    var a = list.Last();
                    var b = list[list.Count - 2];
                    list.Add(a + b);
                }
                Console.WriteLine(list.Count);
                Console.Read();
            }
        }
    }
    

Trackbacks For This Post

  1. Fibonnaci number近似值(ProjectEuler 25) | lastmayday's dream

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.