summaryrefslogtreecommitdiffstats
path: root/002.lua
blob: d70cdc31c7f0a344280fba233596d29c0b7466c6 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
local function memoize(fn)
    local t = {}
    return function(x)
        local y = t[x]
        if y == nil then y = fn(x); t[x] = y end
        return y
    end
end

fib = memoize(function(n)
    if n < 3 then return 1 end
    return fib(n - 1) + fib(n - 2)
end)

local root5 = math.sqrt(5)
local phi = (1 + root5)/2
local function fib2(n)
    return math.floor((phi^n-(1-phi)^n)/root5+0.5)
end

local sum = 0
local i = 0
while true do
    i = i + 1
    local n = fib(i)
    if n > 1000000 then break end
    if n % 2 == 0 then sum = sum + n end
end

print(sum)