JuliaでProject Euler(14) - inamori’s diary

Problem 14

Collatzはこう書ける。

function Collatz_length(n)
    len = 1
    while n != 1
        if n%2 == 0
            n >>= 1
        else
            n = n*3+1
        end
        len += 1
    end
    return len
end

function e014(N::Int)
    max_length, max_n = maximum((Collatz_length(n), n) for n in 1:N-1)
    return max_n
end

N = parse(Int, ARGS[1])
println(e014(N))

PyPyでもそうだが、なぜかメモ化すると遅くなる。なぜだろう。
再帰を使わなければ、メモ化が効く。

function e014(N::Int)
    memo = [ 0 for _ in 1:N-1 ]
    memo[1] = 1
    for n in 2:N-1
        counter = 0
        m = n
        while m >= N || memo[m] == 0
            if m%2 == 0
                m = m >> 1
            else
                m = m*3 + 1
            end
            counter += 1
        end
        memo[n] = counter + memo[m]
    end
    max_length, max_n = maximum((memo[n], n) for n in 1:N-1)
    return max_n
end

N = parse(Int, ARGS[1])
println(e014(N))

10^8で上のコードより5倍くらい速くなった。