# Question about sum of fibonacci sequene

-----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

Panagiotis (atmosx) Atmatzidis

email: [email protected]
URL: http://www.convalesco.org
GnuPG ID: 0xFC4E8BB4
gpg --keyserver x-hkp://pgp.mit.edu --recv-keys 0xFC4E8BB4

The wise man said: “Never argue with an idiot. They bring you down to
their level and beat you with experience.”

-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.12 (Darwin)

iEYEARECAAYFAksr3P4ACgkQrghUb/xOi7Sj3ACfRTXLtHk9vhUuPJ9Ul2o2jlor
mLkAoJGFCERzUJsXjdrnNeYAhXAqn2wf
=v8zV
-----END PGP SIGNATURE-----

On Dec 18, 2009, at 2:50 PM, Panagiotis A. wrote:

I’m stuck in the second problem though. Here is the issue:
I think that my code solves it. Works when I test it to smaller
c = a + b
#puts c
if (c % 2 != 0)

Note: c % 2 != 0 is only true for ODD values of c and you wanted EVEN
values. Change the 4000000 to be 10 and you ought to see the
difference: 1, 2, 3, 5, 8 means 1+3+5=9 for odds and 2+8=10 for evens

sum = sum + c

you could do:
puts [ c, sum ].inspect
to see the c’s that are being added

(probably) for the sake of convenience is ignored. The system
however returns a “false error” in both 10316618 and 10316618 + 1.

Your sequence will be 1, 1, 2, 3, 5, 8, 13, …
If you initialize b=1, then you should get 1, 2, 3, 5, 8, 13, …

Thanks in advanced & best regards

Panagiotis (atmosx) Atmatzidis

Once you get the right answer, you should think about why the value of
your first guess is off to the degree that it is.

-Rob

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hello,
On 18 Î”ÎµÎº 2009, at 10:23 Î¼.Î¼., Rob B. wrote:

a = 1
b = 0
sum = 0
while a <= 4000000

# get the old value of “a”

c = a + b
#puts c
if (c % 2 != 0)

Note: c % 2 != 0 is only true for ODD values of c and you wanted EVEN values. Change the 4000000 to be 10 and you ought to see the difference: 1, 2, 3, 5, 8 means 1+3+5=9 for odds and 2+8=10 for evens

omg. I missread that part. Yes I thought it was asking for odd
numbers… sorry lol.

sum = sum + c

you could do:
puts [ c, sum ].inspect
to see the c’s that are being added

thanks for the hint.

Thanks for the pointers

Panagiotis (atmosx) Atmatzidis

email: [email protected]
URL: http://www.convalesco.org
GnuPG ID: 0xFC4E8BB4
gpg --keyserver x-hkp://pgp.mit.edu --recv-keys 0xFC4E8BB4

The wise man said: “Never argue with an idiot. They bring you down to
their level and beat you with experience.”

-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.12 (Darwin)

iEYEARECAAYFAkssD/0ACgkQrghUb/xOi7QdCACbBVk4GNr60LnD4wF1GH3itZPg
GQYAmQHTtle9EuakjDEsZ0iLjN06Fa84
=2cfD
-----END PGP SIGNATURE-----

On Dec 18, 6:28Â pm, Panagiotis A. [email protected] wrote:

-----BEGIN PGP SIGNED MESSAGE-----
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
while a <= 4000000

Once you get the right answer, you should think about why the value of your first guess is off to the degree that it is.
email: Â [email protected]
GQYAmQHTtle9EuakjDEsZ0iLjN06Fa84
=2cfD
-----END PGP SIGNATURE-----

Just a quick tip for you.

To check for (odd/even)ness:

Instead of doing this: if (c % 2 != 0)
which uses the modulo operator ‘%’ which is
“expensive” in terms of cpu cycles, because it
performs (with a direct implementation) a (hardware)

if (c & 1 == 0)

# To check if integer c is odd (true)

if (c & 1 == 1)

‘&’ bitwise ANDs the integers c with 1.
If c is even then its lsb (least significant bit) is ‘0’
if odd it’s ‘1’.

The ‘&’ operation is done in most modern CPUs as a
single cycle hardware bitwise register operation and
is much faster than the modulo operation ‘%’

It makes a big difference if you’re looping through
that test a lot of times. Benchmark the comparisons
as an exercise to convince yourself.

On Sat, Dec 19, 2009 at 1:20 AM, W. James [email protected] wrote:

same purpose in the past.
not exceed four million.
c = a + b

while a <= 4_000_000

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
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

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}])
}
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

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Thank you all for the very interesting pointers

Panagiotis (atmosx) Atmatzidis

email: [email protected]
URL: http://www.convalesco.org
GnuPG ID: 0xFC4E8BB4
gpg --keyserver x-hkp://pgp.mit.edu --recv-keys 0xFC4E8BB4

The wise man said: “Never argue with an idiot. They bring you down to
their level and beat you with experience.”

-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.12 (Darwin)

iEYEARECAAYFAksscfIACgkQrghUb/xOi7Sn0gCfRFNmKgHj/iY2B2VwQx57GrNt
zqsAn3xYLH21uYnq6AFJcSjpRBL9b+aG
=7HwR
-----END PGP SIGNATURE-----

Panagiotis A. wrote:

I’m stuck in the second problem though. Here is the issue:
I think that my code solves it. Works when I test it to smaller
if (c % 2 != 0)
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

Shot (Piotr S.):

Better yet, use
if c.even?
or
if c.even?
(which are both more readable and do the above binary checks in C).

Or even c.odd?, of course.

â€” Shot (sorry!)

jzakiya:

Just a quick tip for you.

To check for (odd/even)ness:

Instead of doing this: if (c % 2 != 0)
which uses the modulo operator ‘%’ which is
“expensive” in terms of cpu cycles, because it
performs (with a direct implementation) a (hardware)

if (c & 1 == 0)

# To check if integer c is odd (true)

if (c & 1 == 1)

Better yet, use
if c.even?
or
if c.even?
(which are both more readable and do the above binary checks in C).

â€” Shot

Not efficient but with no explicit loop (while…)

fibonacci = (1…100).inject(f = [1,1]) {|f, n| f.insert(-1,(f[-2] +
f[-1])) }
fibonacci.delete_if {|n| n>= 4_000_000 or n.odd?}
p fibonacci.inject(0) {|s,n| s + n}

one line:
p (1…100).inject(f = [1,1]) {|f, n| f.insert(-1,(f[-2] + f[-1]))
}.delete_if {|n| n>= 4_000_000 or n.odd?}.inject(0) {|s,n| s + n}