-
Notifications
You must be signed in to change notification settings - Fork 0
/
counting_summations.rs
34 lines (31 loc) · 1.03 KB
/
counting_summations.rs
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
use crate::utils;
pub fn solve() -> i64 {
// Approach is similar to that used for P78. The difference is that the
// exact values of the partition function are computed.
let mut p = vec![0; 101];
p[0] = 1;
p[1] = 1;
for idx in 2..p.len() {
for (offset, pentagonal) in (1..).zip(utils::Polygonal::new(5)) {
if idx < pentagonal as usize {
break;
}
let recurrence_term = p[idx - pentagonal as usize]
+ if idx < pentagonal as usize + offset {
0
} else {
p[idx - pentagonal as usize - offset]
};
if offset % 2 == 1 {
p[idx] += recurrence_term;
} else {
p[idx] -= recurrence_term;
}
}
}
// Exclude the singleton partition, because we are asked for the number of
// ways to sum to 100 using at least two numbers.
let result = p[100] - 1;
assert_eq!(result, 190569291);
result as i64
}