C# Implementation of Problem 76
View source code here on GitHub!
1/*
2Project Euler Problem 76
3
4I ended up having to do this iteratively, which I'm not super happy with. I feel like there is almost certainly a
5closed-form solution to this, but I was unable to figure it out.
6
7Problem:
8
9It is possible to write five as a sum in exactly six different ways:
10
114 + 1
123 + 2
133 + 1 + 1
142 + 2 + 1
152 + 1 + 1 + 1
161 + 1 + 1 + 1 + 1
17
18How many different ways can one hundred be written as a sum of at least two
19positive integers?
20*/
21using System;
22
23namespace Euler
24{
25 public class p0076 : IEuler
26 {
27 public object Answer()
28 {
29 byte idx;
30 int answer = 0;
31 byte sum = 100;
32 byte[] counts = new byte[101];
33 counts[2] = 100;
34 while (counts[100] == 0)
35 {
36 counts[2] += 2;
37 if (sum >= 100)
38 {
39 answer += (100 + counts[2] - sum) / 2;
40 idx = 2;
41 do
42 {
43 counts[idx++] = 0;
44 counts[idx] += idx;
45 sum = 0;
46 for (byte i = (byte)(idx - 1); i < 101; i += 1)
47 sum += counts[i];
48 } while (sum > 100);
49 }
50 sum = 0;
51 for (byte i = 0; i < 101; i += 1)
52 sum += counts[i];
53 }
54 return answer;
55 }
56 }
57}