Skip to main content

Project Euler Problem # 25 1000-digit Fibonacci number

Spoiler Alert: As the About page of Project Euler says, "Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery." If you are currently attempting to solve this problem in the archives, please do not continue to read this post. I personally worked through all the problems I post on this blog and it has brought me immense satisfaction.

Problem:

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 index of the first term in the Fibonacci sequence to contain 1000 digits?

Solution:

Using the BigInteger class, this problem can be solved very simply using C#:


            //Time the process
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            //First Fibonacci number
            BigInteger n1 = 1;
            //Second Fibonacci number
            BigInteger n2 = 1;
            //Variable to hold next Fibonacci
            BigInteger sum;
            //i represents which term we are on
            int i = 2;
            do
            {
                sum = n2 + n1;
                n1 = n2; n2 = sum;
                i++;
            } while (BigInteger.Log10(sum)<999);
            stopwatch.Stop();
            Console.WriteLine($"First Fib with 1000 digits: {i}");
            Console.WriteLine($"Time to calculate (ms): {stopwatch.Elapsed.TotalMilliseconds}");
            Console.ReadKey();

Notice the "while (BigInteger.Log10(sum)<999)" line. When I first solved this problem, my first reaction was to convert each sum to a string and then count the number of characters in the string (while (sum.ToString().Length<1000)) This is a bad idea. While using the log base 10 method only takes about 60 milliseconds on my machine, using the string method takes more than 350. Converting numbers to strings is an expensive operation. At least in this case, it is 6x more expensive to convert to a string and count the characters vs. getting the log base 10.

I've avoided putting the answer in the solution, just in case someone solving the problem on Project Euler ignored the Spoiler Alert. But this method will provide the correct answer.

Comments

Popular posts from this blog

How NOT To Write Code / How To Decipher Bad Code

Confusing code is bad code. In this post I'll be talking about one of the worst coding practices: using nondescript variables. As an example, we'll be looking at a simple problem from Project Euler (#28). I'll give you an example using really bad code and then we'll look at how we can decipher it and make it more clear and understandable. First, here's the problem: Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows: 21  22 23 24  25 20   7   8   9  10 19  6   1   2 11 18   5   4   3  12 17  16 15 14  13 It can be verified that the sum of the numbers on the diagonals is 101. What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way? Ok, so now check out this solution:             int i = 1; int j = 1; int s = 0; ...

Merging Files into a Single .NET Assembly

.NET assemblies can be single-file or multifile.   As I've been preparing to take Microsoft Exam 70-483, I came across the Al.exe command, a tool which is installed along with Visual Studio. Al stands for "Assembly Linker" and when you run it, it "links" different manifest or resource files together into a single assembly. If you work with .NET at all, you probably have a pretty good idea of what an assembly is, but here's a simple definition from Stack Overflow : "A chunk of (precompiled) code that can be executed by the .NET runtime environment. A .NET program consists of one or more assemblies." -Adrian Grigore Here's a more technical definition from Wikipedia :  "A compiled code library used for deployment, versioning, and security."  Normally when you create a new project in Visual Studio, VS pretty much creates the assembly for you. You don't have to worry about merging different files together using the c...

Programming in R

Image saved from my new ShinyApp Over the past few days I've been playing around with R, a statistical language which is essentially an offshoot of S, which was created in the 1980's. R has some powerful features which enable to it rapidly create meaningful graphical illustrations. I've really enjoyed manipulating some of the datasets on Kaggle with it. Here's a ShinyApp I published to demonstrate a simple R program to track where different plant and animal species live within the US national parks.