JavaScript Implementation of Problem 76
View source code here on GitHub!
- p0076()
Project Euler Problem 76
I ended up having to do this iteratively, which I'm not super happy with. I feel like there is almost certainly a closed-form solution to this, but I was unable to figure it out.
Problem:
It is possible to write five as a sum in exactly six different ways:
4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1
How many different ways can one hundred be written as a sum of at least two positive integers?
- Returns:
number --
1/**
2 * Project Euler Problem 76
3 *
4 * I ended up having to do this iteratively, which I'm not super happy with. I feel like there is almost certainly a
5 * closed-form solution to this, but I was unable to figure it out.
6 *
7 * Problem:
8 *
9 * It is possible to write five as a sum in exactly six different ways:
10 *
11 * 4 + 1
12 * 3 + 2
13 * 3 + 1 + 1
14 * 2 + 2 + 1
15 * 2 + 1 + 1 + 1
16 * 1 + 1 + 1 + 1 + 1
17 *
18 * How many different ways can one hundred be written as a sum of at least two
19positive integers?
20 *
21 * @return {number}
22 */
23exports.p0076 = function() {
24 let answer = 0;
25 let sum = 100;
26 const counts = [...Array(101)].fill(0);
27 counts[2] = 100;
28 while (counts[100] == 0) {
29 counts[2] += 2;
30 if (sum >= 100) {
31 answer += 0 | ((100 + counts[2] - sum) / 2);
32 let idx = 2;
33 while (true) {
34 counts[idx++] = 0;
35 counts[idx] += idx;
36 sum = 0;
37 for (let i = idx - 1; i < 101; i += 1) {
38 sum += counts[i];
39 }
40 if (sum <= 100) {
41 break;
42 }
43 }
44 counts[2] = 100 - sum - (sum % 2);
45 }
46 sum = counts.reduce((a, x) => a + x, 0);
47 }
48 return answer;
49};