```On Sat, Dec 19, 2009 at 1:20 AM, W. James <w_a_x_man / yahoo.com> wrote:

> Panagiotis Atmatzidis wrote:
>
> > -----BEGIN PGP SIGNED MESSAGE-----
> > Hash: SHA1
> >
> > Dear Sirs,
> >
> > Just to improve my programming skills and experience I found amusing
> > solving problems like the ones posed by project Euler. Doing so,
> > using Ruby is a joy, compared to Objective-C that I've used for the
> > same purpose in the past.
> >
> > I'm stuck in the second problem though. Here is the issue:
> >
> > 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, ...
> >
> > Find the sum of all the even-valued terms in the sequence which do
> > not exceed four million.
> >
> > I think that my code solves it. Works when I test it to smaller
> > fractions, can someone reply if there's something wrong with this
> > snippet:  - --------------- # fibonacci
> >
> > a = 1
> > b = 0
> > sum = 0
> > while a <= 4000000
> >  # get the old value of "a"
> >  c = a + b
> >  #puts c
> >  if (c % 2 != 0)
> >   sum = sum + c
> >  end
> >  b = a
> >  a = c
> > end
> >
> > puts sum
> > - ---------------
> >
> > Well my result is: 10316618 . I know that the original Fibonacci
> > sequence will have a (+1) in the beginning of the loop, but
> > (probably) for the sake of convenience is ignored. The system however
> > returns a "false error" in both 10316618 and 10316618 + 1.
> >
> > Thanks in advanced & best regards
>
>
> sum = 0
> a,b = 1,1
> while a <= 4_000_000
>  sum += a if a.even?
>  a,b = b,a+b
> end
>
> p sum
>
>
> --
>
>
>
One of my favourite bits of sample ruby code is the self memoizing Fibonacci
hash, and since the 3rd element of each Fibonacci sequence is the even one
( odd + even = odd; even + odd = odd; odd + odd = even; and so on .... ) you
only need to add the 3rd elements of the hash together, which is what the
second automemoizing hash will do. Then find the first one that is >
4,000,000
the
one before you hit the max limit, it is already calculated in the previous
hash
key so you just need the EFib[n-1] value. It's not as quick as the straight
sum+=a if a.even? code, or as easy to understand, but it's a useful
technique

or to express it in code:

require 'rubygems'
require 'benchmark'
MAX_FIB=4_000_000

Benchmark.bm { |x|
x.report('hash: '){
Fib = Hash.new{ |h,n| h[n] = n<2 ? n : h[n-1]+h[n-2] }
EFib = Hash.new{ |h,n| h[n] = n<1 ? 0 : h[n-1]+Fib[n*3] }
puts(EFib[(1..MAX_FIB).detect {|n| EFib[n]>MAX_FIB}])
}