project-euler/Sidef/142 Perfect Square Collection.sf

#!/usr/bin/ruby

# Perfect Square Collection
# https://projecteuler.net/problem=142

# Find the smallest x + y + z with integers x > y > z > 0 such that x + y, x − y, x + z, x − z, y + z, y − z are all perfect squares.

# Solution based on the following idea:
#   (x+y)*(x-y) = x^2 - y^2

# Since x+y and x-y must be squares, their product is also a square: (x+y)*(x-y) = n^2
# Iterate over n=1..Inf and find the (x,y) solutions to the equation n^2 = x^2 - y^2.
# Then, for each solution (x,y), try to find z, iterating from k=1 to sqrt(y), setting z = y - k^2 and checking if it satisfies the conditions.

# See the Perl version for shorter runtime.

func difference_of_two_squares_solutions(n) {

    n.divisors.map {|d|

        break if (d*d >= n)

        var a = d
        var b = n/d

        (a+b).is_even || next

        var x = (a + b)/2
        var y = (b - a)/2

        [x, y]
    }.flip
}

for k in (1 .. 1e9) {
    say "Checking: #{k}"

    difference_of_two_squares_solutions(k**2).each_2d {|x,y|

        x-y -> is_square || next
        x+y -> is_square || next

        for n in (1 .. y.isqrt) {

            var z = (y - n*n)

            if (is_square(x + z) && is_square(x - z) && is_square(y + z) && is_square(y - z)) {
                die "Found: sum(#{[x,y,z]}) = #{x+y+z}\n"
            }
        }
    }
}