Category Archives: Project Euler

Find The First 1000-digit Fibonacci Number [Project Euler Problem 25]

We all know how the Fibonacci numbers are defined: the nth Fibonacci number is equal to the sum of the two before it, with initial conditions F1 = F2 = 1. Translated into my mathematical language, that is:

Fn = Fn – 1 + Fn – 2

This is an example of a recurrence relation.

Using the theory of generating functions we can turn this recurrence relation into a “closed-form” or explicit formula:Image

[This book taught me generating functions – it’s awesome! You can buy it from that link and earn me a coffee :D]

Here, that odd-looking symbol φ (shame on you) is the magical Golden Ratio (read up on it!), equal to:

Image

Oh, another thing. The number of digits in a number is equal to the ceiling of its logarithm in base 10Here’s why.

Manipulating these leads us to an expression for the index of the first Fibonacci number with d digits:

Fn = (d − 1 + log10(5) /2) / log10(φ)

And with that, here’s the two lines of code! (Code!) (OMG code!)

from math import log10, sqrt, ceil
print(int(ceil((999 + log10(5)/2.0) /
          log10((1 + sqrt(5))/2.0))))

And that’s how I became the 70181st person to solve this problem!

[image credit: Wikimedia]

Multiples of 3 or 5 below 1000 [Project Euler Problem 1]

This is the first Project Euler problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Pretty simple, right? The dumb brute-force method would be:

public class M35 {
    public static void main(String[] args) {
        long time = System.nanoTime();

        int val = 0;
        for (int i = 0; i < 1000; i++){
            if(i%3==0 || i%5 == 0){val+=i;}
        }
        time = System.nanoTime() - time;

        System.out.println(time/1.0e9);
    }
}

It returns:

233168
2.6782E-5

Less than 0.0002 seconds? Neat, right? But what about an intelligent solution?
Try and recall how Gauss stumped his teacher in primary school when asked to sum the range 1 to 100 mentally. He understood that the range 1 to 100 consists of:
(1+100) + (2+99) + (3+98) … + (50+51) = 50 x 101 = 5050.

Now, in our case, we need the sum of all multiples of either three or five – but what about 15? 30? They’ll get counted twice, right?

In our case, what we need to do is,

(sum of multiples of 3) + (sum of multiples of 5) – (sum of multiples of 15)

=> (3 + 6 + 9 + … +999) + (5 + 10 + 15 + … + 995) – (15 + 30 + 45 + … + 990)

=> 3 x (1 + 2 + 3 + … + 333) + 5 x (1 + 2 + 3 + … + 199 ) – 15 x (1 + 2 + 3 + … + 66)

I’ll leave you to find out how these series can be summed.

After all, Project Euler tells us not to give out spoilers :D

PS. Hint, hint, arithmetic progression sums.