/
count_subtriangles.pl
executable file
·82 lines (71 loc) · 1.08 KB
/
count_subtriangles.pl
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
#!/usr/bin/perl
# Author: Daniel "Trizen" Șuteu
# License: GPLv3
# Date: 20 September 2015
# Website: https://github.com/trizen
# A general formula for counting the number of possible triangles inside a triangle.
use strict;
use warnings;
## The formula is:
#
# Sum((2n+1)(k-n-1), {n=0, k-1})
#
# where "k" is the number of rows of the triangle.
## Closed forms:
#
# (k^3)/3 - (k^2)/2 + (k/6)
# (1/6)(k-1)k(2k-1)
#
# For example, the following triangle:
# 1
# 234
# 56789
# Has 3 rows and 5 different triangles inside:
# 1
# 234
# 56789
#
# 1
# 234
#
# 2
# 567
#
# 3
# 678
#
# 4
# 789
sub count_subtriangles {
my ($k) = @_;
my $sum = 0;
foreach my $n (0 .. $k - 1) {
$sum += (2 * $n + 1) * ($k - $n - 1);
}
$sum;
}
foreach my $k (1 .. 20) {
my $closed = ($k - 1) * $k * (2 * $k - 1) / 6;
printf("%2d: %10s %10s\n", $k, count_subtriangles($k), $closed);
}
__END__
1: 0
2: 1
3: 5
4: 14
5: 30
6: 55
7: 91
8: 140
9: 204
10: 285
11: 385
12: 506
13: 650
14: 819
15: 1015
16: 1240
17: 1496
18: 1785
19: 2109
20: 2470