# Question about sum of fibonacci sequene [PROJECT EULER]

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: atma@convalesco.org
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 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

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
Rob@AgileConsultingLLC.com

···

On Dec 18, 2009, at 2:50 PM, Panagiotis Atmatzidis 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

···

--

Hello,

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

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.

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

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
Rob@AgileConsultingLLC.com

Thanks for the pointers

Panagiotis (atmosx) Atmatzidis

email: atma@convalesco.org
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."

···

On 18 Δεκ 2009, at 10:23 μ.μ., Rob Biedenharn wrote:

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

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

···

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

--

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)

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

···

On Dec 18, 6:28 pm, Panagiotis Atmatzidis <a...@convalesco.org> wrote:

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

Hello,
On 18 Δεκ 2009, at 10:23 μ.μ., Rob Biedenharn wrote:

> On Dec 18, 2009, at 2:50 PM, 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)

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

>> 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: a...@convalesco.org
>> 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
> R...@AgileConsultingLLC.com

Thanks for the pointers

Panagiotis (atmosx) Atmatzidis

email: a...@convalesco.org
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-----

Thank you all for the very interesting pointers

Panagiotis (atmosx) Atmatzidis

email: atma@convalesco.org
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."

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)

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

···

--
To find a rhyme for silver,
A seemingly rhymeless rhyme,
Requires only will, ver-
bosity and time.
[Willard R. Espy]

Shot (Piotr Szotkowski):

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

···

--
until programmers stop acting like obfuscation is morally hazardous,
they’re not artists, just kids who don’t want their food to touch.
[_why]

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}

···

--
Posted via http://www.ruby-forum.com/.