Question about sum of fibonacci sequene [PROJECT EULER]

ruby-talk
1

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

2

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

···

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

3

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

···

--

4

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

email: atma@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
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:

5

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

···

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

--

6

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.

···

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

7

Thank you all for the very interesting pointers :slight_smile:

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

8

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

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]

9

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]

10

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