1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253 |
- #!/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"
- }
- }
- }
- }
|