-
Notifications
You must be signed in to change notification settings - Fork 6
/
142 Perfect Square Collection.sf
52 lines (34 loc) · 1.31 KB
/
142 Perfect Square Collection.sf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#!/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"
}
}
}
}