Question about sum of fibonacci sequene [PROJECT EULER]

[Panagiotis Atmatzidis]

-----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 =3D 1
b =3D 0
sum =3D 0
while a <=3D 4000000
# get the old value of "a"
c =3D a + b
#puts c
if (c % 2 !=3D 0)
sum =3D sum + c
end
b =3D a
a =3D c
end
=20
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=20



Panagiotis (atmosx) Atmatzidis

email: (e-mail address removed)
URL: http://www.convalesco.org
GnuPG ID: 0xFC4E8BB4=20
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
=3Dv8zV
-----END PGP SIGNATURE-----

 

[Rob Biedenharn]

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

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

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.

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

email: (e-mail address removed)
URL: http://www.convalesco.org

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

Rob Biedenharn http://agileconsultingllc.com
(e-mail address removed)

 

[Panagiotis Atmatzidis]

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

Hello,

On Dec 18, 2009, at 2:50 PM, Panagiotis Atmatzidis wrote:
=20

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.previous two terms. By starting with 1 and 2, the first 10 terms will =
be:fractions, can someone reply if there's something wrong with this =
snippet:

=20
Note: c % 2 !=3D 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=3D9 for odds and 2+8=3D10 for =
evens

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

=20

sum =3D sum + c

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

thanks for the hint.

=20

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.

=20
Your sequence will be 1, 1, 2, 3, 5, 8, 13, ...
If you initialize b=3D1, then you should get 1, 2, 3, 5, 8, 13, ...
=20
=20
=20
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.

=20
-Rob
=20
Rob Biedenharn http://agileconsultingllc.com
(e-mail address removed)
=20
=20
=20
=20

Thanks for the pointers

Panagiotis (atmosx) Atmatzidis

email: (e-mail address removed)
URL: http://www.convalesco.org
GnuPG ID: 0xFC4E8BB4=20
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
=3D2cfD
-----END PGP SIGNATURE-----

 

[jzakiya]

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

Hello,

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

Note: c % 2 != 0 is only true for ODD values of c and you wanted EVENvalues.  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.

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

thanks for the hint.

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

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 Biedenharn            http://agileconsultingllc.com
(e-mail address removed)

Thanks for the pointers

Panagiotis (atmosx) Atmatzidis

email:  (e-mail address removed)
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-----

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)
division operation, do this instead:

# To check if integer c is even (true)
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.

 

[W. James]

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


--

 

[Paul McKibbin]

[Note: parts of this message were removed to make it a legal post.]

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

 

[Panagiotis Atmatzidis]

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


Thank you all for the very interesting pointers


Panagiotis (atmosx) Atmatzidis

email: (e-mail address removed)
URL: http://www.convalesco.org
GnuPG ID: 0xFC4E8BB4=20
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
=3D7HwR
-----END PGP SIGNATURE-----

 

[Giampiero Zanchi]

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}