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.

Solution : For the explanation please see the comments. Later I realized that I could have probably used Binet's formula, however this solution also kind of looks good.

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

#

#Obersevations : starting with 2 every 3rd number is even (it must be, as to make an even number

#one needs to add two odds (or two even unlikely here))

#So, lets try to decompose the fibonacci series in terms of n-3,n-6,n-9, etc...as it make us do

#less iteration while adding

#

# F(n) = F(n-1)+F(n-2) = F(n-2)+F(n-3)+F(n-2) = F(n-3)+2(F(n-2)) = F(n-3) + 2(F(n-3)+ F(n-4))

# = 3F(n-3) + 2F(n-4)

# = 3F(n-3) + F(n-4)+F(n-5)+F(n-6) = 4F(n-3) + F(n-6)

#

#

def find_sum_of_even_terms(limit)

if(limit<2)

return 0

end

if(limit<8)

return 2

end

second_last_even_number = 2

last_even_number = 8

current_number = 4*last_even_number+second_last_even_number

sum=second_last_even_number+last_even_number

while current_number<=limit

sum+=current_number

second_last_even_number = last_even_number

last_even_number = current_number

current_number = 4*last_even_number+second_last_even_number

end

sum

end

puts find_sum_of_even_terms(4000000)

## 4 comments:

Another solution is to use a matrix to calculate Fibonacci numbers. My friend pointed me to this and I thought it was pretty clever (I am admittedly math-retarded). The result calculates almost instantaneously though slightly slower than your solution (0.011s for the posted solution vs. 0.019s for the matrix solution).

https://gist.github.com/a5b975b03bd549c9a0d7

Thanks, Good to know about this solution and the time comparision. I guess the other mathematical way , using Benet's formulae could be fatser.

By the way, Congratulation for winning RPCFN #2 ! Just saw a tweet from Satish Talim.

Why so complicated? For a simple problem, wouldn't this work? (Warning: ruby noob code coming!)

seq = [1, 2]

even = [2]

while seq.last <= 4000000

seq << seq[-1] + seq[-2]

if seq.last % 2 == 0

even << seq.last

end

end

total = 0

even.each do |i|

total = total + i

end

puts "Total: #{total}"

I have found it on this website called [url=http://tipswift.com]tip swift[/url]. You can find it there.

cheers

edit: wrong thread,

Post a Comment