From: Paul McKibbin <pmckibbin@...>
Date: 2009-12-19T11:58:17+09:00
Subject: Re: Question about sum of fibonacci sequene [PROJECT EULER]

--000e0cd138625220d7047b0bfecc
Content-Type: text/plain; charset=ISO-8859-1

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
and print it. The thing that I like about this approach is that if you need
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
to have in your armoury.

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}])
  }
  x.report('add:  ') {
    sum = 0
    a,b = 1,1
    while a <= MAX_FIB
     sum += a if a.even?
     a,b = b,a+b
    end
    puts(sum)
  }
}

Best wishes,
Mac

--000e0cd138625220d7047b0bfecc--