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)
3 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}"
Post a Comment