This is the second post in my Project Euler series (if series is the right word). The first problem is here.
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
This problem is near and dear to my heart for a few reasons. When my lovely wife was just a little girl, she had trouble sleeping, so her father basically taught her the Fibonacci sequence and told her to just keep adding numbers together until she fell asleep. Additionally, when I took my discrete math course, we talked about the Fibonacci sequence A LOT. And finally, I’m not sure why, but at a young age I decided to take some online IQ test and there was a problem that I found very interesting. It was something along the lines of:
If you add the numbers 1 through 5 together the answer will be odd.
If you add the numbers 1 through 20 together, will the answer be even or odd.
Now, for anyone that knows, you can always solve this problem the quick and dirty way:
|
1 2 3 4 |
1 + 20 = 21 2 + 19 = 21 3 + 18 = 21 etc.. |
then multiply 21 by the number of pairs there are (10) and you’ll wind up with 210. Nice, quick, easy and to the point. But that’s not how my little mind worked. It worked a little more like this:
|
1 2 3 |
even + even = even even + odd = odd odd + odd = even |
By this simple logic, the only way to end up with an odd number is to add it to an even one. This reduces the whole problem down to one simple question: is there an even amount of odd numbers between 1 and 20?
The answer is that there are an even number of odd numbers between 1 and 20. I believe this is a good algorithm for determining the number of odd numbers in a range. Apparently my 8 year old brain was smarter than adult me, because adult me had to look it up.
At any rate, that’s not the import part. What’s important is odd + even is the only way to get an odd number out.
The Fibonacci sequence being 1, 1, 2, 3, 5, 8... Follows a grand pattern – odd + odd, odd + even, even + odd, repeat. By taking advantage of this pattern, we don’t have to look at every number in the sequence. We can already determine that every 3rd number will be even.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int x1 = 1; int x2 = 1; int x3 = -1;; long sum = 0; while(x1 + x2 <= 4000000) { x3 = x1 + x2; //even sum += x3; x1 = x3 + x2; //odd x2 = x1 + x3; //odd } NSLog(@"The sum of all even Fibonacci numbers where F_x < 4,000,000 is: %li", sum); |
Of course, we could have just generated every value of the Fibonacci sequence and checked it’s evenness, but this way is far more clever.