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

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.

Posted by Kristian

SuprDewd

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.

SuprDewd

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.

Kristian

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 [$some formula$] now such that your comment becomes

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

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

Kristian

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

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

you have

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

where alpha is smaller than 1.

SuprDewd

Oh that’s pretty neat.

Nischay Nahata

Kristian

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?

Nischay Nahata

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.

SuprDewd

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

Kristian

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

Ricardo

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?

Ricardo

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

Kristian

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.

ggoyo

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)

[…] + sqrt{5}) )^n approx 0.4472135955 cdot 1.618033988745^n 关于此题的详解见这篇文章: Project Euler 25: What is the first term in the Fibonacci sequence to contain 1000 digits? 有了这个公式之后我们就只用求a的值就好啦 displaystyle frac{a^n}{sqrt{5}} > […]

lince159

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.

Mark Soric

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!

Kristian

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

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>();
while (list.Last().ToString().Length < 1001)
{
var a = list.Last();
var b = list[list.Count - 2];