## Solving the Project Euler Problems – Problem 2

The main consideration here was how to calculate the Fibonacci sequence without taking up too many resources, a common danger with recursive functions which are often touted as the solution for working out the sequence and other things like factorials. It turns out the Fibonacci sequence as a recursive function is fine up until about the 10th term, but any further than that? Not advisable!

No gists found

The much quicker solution that I’ve found is to do it as an array, which takes simple values for its calculations rather than calling a recursive function again and again and again.

The second performance optimisation is checking whether our Fibonacci number is even, which when doing it a limited number of times, is fine to do just by checking if n modulo 2 is 0, but how many times will we be doing this? Off the top of your head which Fibonacci term is the largest below 4,000,000? The 10th? The 50th? The 1,000th? We don’t know how many until we actually do it. As it happens it’s the 32nd term, 3,524,578. Run that recursive function 32 times!

As division is slow and all we’re using it to do is check if a number is even, is there a better way? Well kind of, we can check if it isn’t odd. This is done by using the bitwise AND operator. This takes the binary representation of a number – 2019’s would be 11111100011 – and it’s that final bit we’re interested in, if it’s 1 then the number is odd and if it’s 0 it’s even. So using the bitwise AND operator to compare any number to 1 checks only 2 bits and avoids division.

## Solving the Project Euler Problems – Problem 1

After stumbling across an article on Medium by Bennett Garner, I discovered the Project Euler problems and that it would be a good idea to showcase my skills in solving them in a variety of ways, as a good starting point to get a code portfolio going, so here goes with – as natural a starting point as any – problem 1!

All of the Project Euler Problems can be found at ProjectEuler.net.

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.

No gists found

There were 2 ways I considered to tackle this:

• Loop from 1 to 1000 (or as in the code, n) and check each number for dividing by 3 and 5 respectively, adding them to the result if either is true
• Reduce the number of loops by 47% and run our loop $\frac{n}{3}$ + n/5 times (for those interested, 1/3 + 1/5 = 8/15, so this reduction percentage works for any integer), by dividing n by 3, running that loop, adding 3 times each number to the result – which takes division out of the loop as well – then doing the same again, only now having to check (on a smaller loop) if our result was already added as being a multiple of 3.