Project Euler with Ruby on WSL [Problem 2]

例によって

ネタばれあり

問題

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

私訳

1, 2 から始めるフィボナッチ数列の 400万 を超えない項について、偶数となる項の和を求めよ

解答方針

偶数が 3 つ周期、 (添え字 0 始まりとして) 3i + 1 番目に現れることはすぐわかる。 偶数+奇数 = 奇数, 奇数 + 奇数 = 偶数 だからだ

当初、フィボナッチ数列の一般項を使って、 等比数列の和の公式から計算しようかと思ったのだが、 逆に面倒(特に「400万を超えない」が)になってきて、 愚直に計算することにした。

# Project Euler
# problem 2

def fib_array(upper)
    list = [1,2]
    while list.last < upper
        list.push(list[-1]+list[-2])
    end

    # always list.last >= upper
    list.pop
    return list
end

arr = fib_array(4*1000*1000)
sum = 0
for i in 0..((arr.length-1)/3)
    sum += arr[3*i+1]
end

puts sum