Integer Right Triangles (PE39)

In the 39th problem on Project Euler, we are working with right-angled triangles with integral length sides, \((a, b, c)\), where \(a^2 + b^2 = c^2\). The perimeter of such a triangle can be computed by summing the three terms, \(a + b + c = p\) and we need to find which value of \(p \leq 1000\) has the most solutions where \(a\), \(b\), and \(c\) are integers.

Since \(p\) is fairly small and we can limit ourselves to only those cases where \(a < b < c < p\), it is efficient enough to use list comprehensions to build a vector, \(v\), of the perimeters of all right-triangle solutions where,

\[ \begin{aligned} 1 \leq &a \leq 1000 \\ a \leq &b \leq 1000 \\ b \leq &c \leq 1000 \\ a^2 + &b^2 = c^2 \\ a + b + c &= p \leq 1000\,. \\ \end{aligned}\]

Having instantiated a dictionary object, sumhistogram, we then iterate over \(v\), counting the number of times a specific perimeter sum is present. We then transform the dictionary to a vector of pairs and sort by the values of each pair, returning the key of the pair with the largest value.

@time begin
    sumhistogram = Dict{Int, Int}()

    for t in [a + b + c 
                for a in 1:1000
                    for b in a:1000
                        for c in b:1000 
                            if a^2 + b^2 == c^2 &&  
                               a + b + c ≤ 1000]
        if haskey(sumhistogram, t)
            sumhistogram[t] += 1
        else
            sumhistogram[t] = 1
        end
    end

    perimeters = sort(collect(sumhistogram), by=x -> x[2])
    @show perimeters[end][1]
end

>  0.289545 seconds (534.35 k allocations: 29.014 MiB, 71.56% compilation time)
>  840

Writing the code for this solution required under five minutes and the computation time was found to be \(0.29\) seconds making this a very easy problem.