mattoneal.com

Problem 2 of Project Euler follows. As of this posting, there have been 113,666 correct answers posted.

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.

Here’s the MATLAB/Octave code I used to solve the problem. This executed in 0.010 seconds on my computer.

% ProjectEuler.net problem #002
% sum all even Fibonacci numbers below 4 million
 
clear
t = cputime;
 
% create array of Fibonacci numbers
a=0; b=1; c=0; i=1; j=0; newsum=0;
 
while c < 4e6
	c=a+b;
	a=b;
	b=c; 
	fib(i,1) = c;
	i=i+1;
end
 
disp('=================');
len = length(fib)
second_to_last = fib(len-1,1)
last = fib(len,1)
sum_of_fib = sum(fib)
disp('=================');
 
% parse the even numbers out of the array
 
for j = 1:len-1
	if rem(fib(j,1),2) == 0
		newsum(j,1) = fib(j,1);
	else
		newsum(j,1) = 0;
	end
end
 
sum_of_even = sum(newsum) # This outputs the answer.
exec_time = cputime-t # This is how long it takes to execute.

I typically try to avoid too many loops in my coding, but in this problem it didn’t slow it down much at all. Probably because there are only 33 numbers in the Fibonacci sequence that are below 4 million. I ran the code again for the sum of all even Fibonacci numbers below 4 Billion and there was no change at all in the execution time. This is actually intuitive when you realize that there are still only 47 Fibonacci numbers in the sequence below 4 billion – so the code only had to loop an extra 14 times.

What about summing all the numbers less than 4 Trillion?? Still only 61 numbers to loop through. Execute time was still 0.01 seconds. Here’s a quick table showing the results of running this code with three different upper limits. Note, the last digits are approximations.

Upper Limit, Fibonacci Numbers, Sum of all Even
4,000,000           33            4,613,000
4,000,000,000       47        1,485,600,000
4,000,000,000,000   61    2,026,400,000,000

There you have it. Happy coding!

I recently came across a very interesting problem solving site. It’s called Project Euler (usually pronounced Oiler) and it looks like it has been around for several years. The concept is simple. The administrators post problems to solve. The problems are typically math/science based and most require some type of programming language to solve. Users try to solve problems (in their language of choice) and are credited when they post a correct answer.

The site keeps track of the basic stats – like which problems and how many you have answered, as well as how many other users have successfully answered each problem. Also interesting is the number of users and what languages they are using. It was interesting to see that C/C++ seems to be the language of choice (with over 14,000 users as of this posting). The next most popular were Python (13,000 users), Java (8,600) and C# (4,600). MATLAB and Octave had about 1,000 users.

One of the coolest features of the site is that once you’ve solved a problem, you get access to their solution (in pdf) and the bulletin board to see many of the other solvers’ solutions. For example, if you’re a C++ programmer, you can learn several other approaches on how to solve the same problem. Since there aren’t too many users of MATLAB or Octave on the site, I didn’t see any other users’ code for solving the problems in these languages. So I’ve decided it might be beneficial to post my code here.

One last note, if you’re participating in the project, don’t worry about me revealing the answers here. I’ll try my best not to. If I do on occasion, don’t get all worked up, just try not to violate the spirit of the project. The site exists for fun – to practice coding, learn from others, and perhaps share your own knowledge. I realize that most of us in this game are in it because we find it interesting. We like seeing a problem, figuring out a way to solve it, and then coding a solution to solve it.

If you haven’t seen the site, I encourage you to check out Project Euler. It’s pretty fun, but be careful. For true geeks, it can be addictive. Good luck and happy coding!