Thursday, October 23, 2014

Project Euler in CMD: Even Fibonacci numbers

Aloe polyphylla Schönland ex Pillans by brewbooks is licensed CC BY-SA 2.0
Before I go any further with this project, I just want to point out that I haven't taken a math class in over a decade and it's pretty rare, at least in my corner of IT, that I have to use anything more advanced than basic algebra. Consequently, I'm certain there are some pretty clever mathematical solutions to the Project Euler problems that I'm overlooking (the previous problem, for example, was just a sum of two arithmetic progressions, minus the arithmetic progression of when a number is a multiple of both 3 and 5), but I'm in this more for the scripting experience than I am for a refresher in mathematics.

That's not to say I mind having a refresher in mathematics, of course.

This brings me to my solution for this problem:
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.
Now, if you take a look, you'll notice that the even number in a Fibonacci sequence happens every three numbers, at least once you get past two - O, E, O, O, E, O, O, E, O, O, ... and so on. There's a very elementary reason for that - since at least one of the numbers being added into the sequence is guaranteed to be odd, the only way you're going to get an even number is if you add two odd numbers together; after that, you just end up adding an even number to an odd number, at which point you have another odd number.

Can I take advantage of this insight myself? Not on your life.

So, with that in mind, let's apply a little brute force to the problem:


@ECHO OFF
SET _FibL=1
SET _FibR=2
SET _FibZ=0
SET _FibSum=0

:Loop
IF %_FibL% GEQ 4000000 GOTO Finish

SET /A "_LMod2=_FibL%%2"
IF %_LMod2% EQU 0 SET /A "_FibSum=_FibSum+_FibL"
SET /A "_FibZ=_FibL+_FibR"
SET /A "_FibL=_FibR"
SET /A "_FibR=_FibZ"

GOTO Loop

:Finish
ECHO Sum is %_FibSum%
GOTO :EOF

So, there you have it - the answer, by the way, is 4,613,732.

No comments:

Post a Comment