performancejuliaone-liner

Optimize performance Euler problem 12 in a Julia oneliner


I recently started coding in Julia (coming from Python). To practice my Julia skills, I started solving Euler problems. Euler problem 12 (https://projecteuler.net/problem=12) is not so hard to solve.

To make things a little harder, I try to solve each problem one line of code, sometimes with a helper function.

The code below gives the right answer, but does not perform well (takes 3 minutes).

function factors(n)
    treshold = 500
    counter = 0
    s = sum(1:n)
    for i in 1:s
        if s%i == 0
            counter += 1
        end
    end
    if counter > treshold
        return false
    else
        return true
    end
end

sum(1:maximum(Iterators.takewhile(factors, Iterators.countfrom()))+1)

What a the best options in Julia to speed up this oneliner?


Solution

  • The simplest speedup would be to only count up to isqrt(s) instead of s. With

    function factors(n)
        treshold = 500
        counter = 0
        s = sum(1:n)
        for i in 1:isqrt(s)
            if i*i == s
                counter += 1
            elseif s%i == 0
                counter += 2
            end
        end
        if counter > treshold
            return false
        else
            return true
        end
    end
    

    This takes only 0.07 seconds.