-
Notifications
You must be signed in to change notification settings - Fork 0
/
152.rb
100 lines (59 loc) · 1.7 KB
/
152.rb
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
=begin
Writing 1/2 as a sum of inverse squares
Problem 152
There are several ways to write the number 1/2 as a sum of inverse squares using distinct integers.
For instance, the numbers [2,3,4,5,7,12,15,20,28,35] can be used:
In fact, only using integers between 2 and 45 inclusive, there are exactly three ways to do it, the remaining two being: {2,3,4,6,7,9,10,20,28,35,36,45} and {2,3,4,6,7,9,12,15,28,30,35,36,45}.
How many ways are there to write the number 1/2 as a sum of inverse squares using distinct integers between 2 and 80 inclusive?
1/x^2 + 1/y^2 = 1/2
y^2/(x^2)(y^2) + x^2/(x^2)(y^2) = 1/2
x^2 + y^2
---------
(x^2)(y^2) = 1/2
=end
require './euler_lib.rb'
=begin
denoms = [2,3,4,5,7,12,15,20,28,35]
denoms.map! {|x| x*x}
common_denom = denoms.inject(:*)
nums = denoms.map {|x| common_denom / x }
sum_num = nums.inject(:+)
puts sum_num
puts common_denom
pp Rational(sum_num, common_denom)
=end
denoms = (2..45).to_a.map {|x| x*x}
cd = lcm(denoms[0], denoms[1])
2.upto(denoms.length - 1) do |x|
cd = lcm(cd, denoms[x])
end
numerators = denoms.map {|x| cd / x }
=begin
Check: We get all the fractions back correctly..
numerators.each do |x|
pp Rational(x, cd)
end
=end
def ways_to_add_to_n(arr, target, cur_sum = 0, cur_addens = [], &proc)
if cur_sum == target
yield cur_addens
return
end
if cur_sum > target
puts "too big"
return
end
if arr.empty?
return
end
a = arr.shift
ways_to_add_to_n(arr, target, cur_sum, cur_addens, &proc)
cur_addens.push a
ways_to_add_to_n(arr, target, cur_sum + a, cur_addens, &proc)
cur_addens.pop
arr.unshift a
end
target = cd / 2
ways_to_add_to_n(numerators, cd / 2) do |ans|
pp ans
end