This solution first finds all the sums of the triangle number pairs. To find solutions, it looks for each triangle number whether there's a pair that sums to the target:
#!/usr/bin/perl
use strict;
use warnings;
my $target = 80;
my @triangles;
my %sum;
#
# Find all triangle numbers less than the target
#
my $n = 0;
{
my $t = $n * $n++ / 2;
last if $t > $target;
push @triangles, $t;
redo;
}
#
# Find all sums of triangle numbers:
#
for (my $i = 0; $i < @triangles; $i++) {
my $t1 = $triangles[$i];
for (my $j = $i; $j < @triangles; $j++) {
my $t2 = $triangles[$j];
last if $t1 + $t2 > $target;
$sum{$t1 + $t2} ||= [$t1, $t2];
}
}
#
# Now for each number, try all triangle numbers and see if there's a s
+um
#
NUMBER:
for (my $number = 0; $number <= $target; $number++) {
foreach my $triangle (@triangles) {
next unless $sum{$number - $triangle};
printf "%d = %d + %d + %d\n", $number, $triangle,
@{$sum{$number - $triangle}};
next NUMBER;
}
}
__END__
0 = 0 + 0 + 0
1 = 0 + 0 + 1
2 = 0 + 1 + 1
3 = 0 + 0 + 3
4 = 0 + 1 + 3
5 = 1 + 1 + 3
6 = 0 + 0 + 6
7 = 0 + 1 + 6
8 = 1 + 1 + 6
9 = 0 + 3 + 6
10 = 0 + 0 + 10
11 = 0 + 1 + 10
12 = 0 + 6 + 6
13 = 0 + 3 + 10
14 = 1 + 3 + 10
15 = 0 + 0 + 15
16 = 0 + 1 + 15
17 = 1 + 1 + 15
18 = 0 + 3 + 15
19 = 1 + 3 + 15
20 = 0 + 10 + 10
21 = 0 + 0 + 21
22 = 0 + 1 + 21
23 = 1 + 1 + 21
24 = 0 + 3 + 21
25 = 0 + 10 + 15
26 = 1 + 10 + 15
27 = 0 + 6 + 21
28 = 0 + 0 + 28
29 = 0 + 1 + 28
30 = 0 + 15 + 15
31 = 0 + 3 + 28
32 = 1 + 3 + 28
33 = 3 + 15 + 15
34 = 0 + 6 + 28
35 = 1 + 6 + 28
36 = 0 + 0 + 36
37 = 0 + 1 + 36
38 = 0 + 10 + 28
39 = 0 + 3 + 36
40 = 1 + 3 + 36
41 = 3 + 10 + 28
42 = 0 + 6 + 36
43 = 0 + 15 + 28
44 = 1 + 15 + 28
45 = 0 + 0 + 45
46 = 0 + 1 + 45
47 = 1 + 1 + 45
48 = 0 + 3 + 45
49 = 0 + 21 + 28
50 = 1 + 21 + 28
51 = 0 + 6 + 45
52 = 1 + 6 + 45
53 = 10 + 15 + 28
54 = 3 + 6 + 45
55 = 0 + 0 + 55
56 = 0 + 1 + 55
57 = 0 + 21 + 36
58 = 0 + 3 + 55
59 = 1 + 3 + 55
60 = 0 + 15 + 45
61 = 0 + 6 + 55
62 = 1 + 6 + 55
63 = 3 + 15 + 45
64 = 0 + 28 + 36
65 = 0 + 10 + 55
66 = 0 + 0 + 66
67 = 0 + 1 + 66
68 = 1 + 1 + 66
69 = 0 + 3 + 66
70 = 0 + 15 + 55
71 = 1 + 15 + 55
72 = 0 + 6 + 66
73 = 0 + 28 + 45
74 = 1 + 28 + 45
75 = 3 + 6 + 66
76 = 0 + 10 + 66
77 = 1 + 10 + 66
78 = 0 + 0 + 78
79 = 0 + 1 + 78
80 = 1 + 1 + 78
