pb094.jl

module Problem094


"""
    problem094()

Problem 094 of Project Euler.

https://projecteuler.net/problem=064


Suppose (a, a, a ± 1) is an almost equilateral triangle.
Split it into two so that the two resulting triangles have edges (a, (a ± 1)/2, h).
Since the area of the triangle must be integer-valued, so too must (a ± 1)/2 and h.
Therefore, ((a ± 1)/2, h, a) is a pythagorean triple,
and can be generated by Euclid's formula.

If (a ± 1)/2 is generated by k(u^2 - v^2), then

    ∓1 = a - (a ± 1) = k(u^2 + v^2) - 2k(u^2 - v^2) = k(3v^2 - u^2).

This implies that k=1, so

    u = sqrt(3v^2 ± 1).

If (a ± 1)/2 is generated by 2kuv, then

    ∓1 = a - (a ± 1) = k(u^2 + v^2) - 2kuv = k(u^2 + v^2 - 2uv).

Again, this means k=1.  Solving for u yields

    u = (4v + sqrt(16v^2 - 4v^2 ∓ 4))/2 = 2v + sqrt(3v^2 ∓ 1).

In both cases, we require 3v^2 +- 1 be a perfect square x^2.
Since the quadratic residues mod 3 are {0, 1} and 3v^2 - 1 (mod 3) = 2,
we only need to check for v such that 3v^2 + 1 = x^2.
Therefore, it suffices to solve Pell's equation

    x^2 - 3v^2 = 1,

where x = sqrt(3v^2 + 1).
By inspection, (2, 1) is a solution, 
and all other solution can be obtained by

    x_{k + 1} = 2x_k + 3y_k,    y_{k + 1} = 2y_k + x_k.

For the first case where u = sqrt(3v^2 + 1),
we have a = u^2 + v^2 = 4v^2 + 1 and perimeter = 3a + 1 = 12v^2 + 4
In the second case where u = 2v + sqrt(3v^2 + 1),
we have a = u^2 + v^2 = 8v^2 + 4vx + 1 and perimeter = 3a - 1 = 24v^2 + 12vx + 2.
"""
function problem094(N::Integer=10^9)
    perimeters = 0
    x = 2
    v = 1

    while true
        p1 = 12v^2 + 4
        p2 = 24v^2 + 12v * x + 2
        p1 > N && return perimeters
        perimeters += p1
        p2 ≤ N && (perimeters += p2)
        x, v = 2x + 3v, x + 2v
    end
end


export problem094
end  # module Problem094
using .Problem094
export problem094