Problem Analysis
The task is to count the number of ways to write 100 as a sum of at least two positive
integers where the order of the terms is irrelevant. This is exactly the
integer partition
function p(n), which counts the number of ways to write n as an
unordered sum of positive integers. The phrase "at least two" is the only twist: by convention
p(n) includes the single-term partition n = n, so the answer I want
is p(n) - 1. For n = 5 we have p(5) = 7, and subtracting
the trivial partition [5] leaves the six sums shown in the problem. Recognizing
the problem as p(n) - 1 is the unlocking insight: it turns an open-ended counting
question into one with well-studied recurrences.
Naive enumeration of partitions is exponential, but the structure is full of overlapping
subproblems, which is the hallmark situation for
dynamic programming
(solving each distinct subproblem once and reusing the result). One natural formulation counts
partitions of n using parts no larger than a bound, giving O(n^2) states with O(n)
work each, hence O(n^3) overall. A far better route uses
Euler's pentagonal number theorem,
which expresses p(n) as an alternating sum of only about O(sqrt(n)) earlier
partition values. Because the
generalized pentagonal numbers
g(k) = k(3k-1)/2 grow quadratically in k, the recurrence touches only
roughly sqrt(2n/3) previous terms, yielding an O(n*sqrt(n)) algorithm. One more
practical concern: for n = 1000 the answer has 32 decimal digits, well beyond a
64-bit integer, so any C solution must carry
arbitrary-precision arithmetic.
Solution Approach
s0 - Euler's Pentagonal Number Theorem
I chose the pentagonal recurrence as my primary algorithm because it is asymptotically the best
of the three. The
pentagonal number theorem
states p(0) = 1 and, for n >= 1,
p(n) = sum over k = 1, 2, 3, ... of (-1)^(k+1) * (p(n - g(k)) + p(n - g(-k))),
where g(k) = k(3k-1)/2 is the k-th
generalized pentagonal number
and any term with a negative argument is treated as zero. The alternating sign
(-1)^(k+1) adds for k = 1, 3, 5, ... and subtracts for
k = 2, 4, 6, ..., which I encode with k % 2.
The Python version (p0076_s0.py) writes the identity directly as a recursion
guarded by
functools.lru_cache,
so each p(i) is evaluated once. The inner loop uses
itertools.count(1) and breaks the instant both p(n - g(k)) and
p(n - g(-k)) evaluate to zero, which happens once both pentagonal offsets exceed
n. The C version (p0076_s0.c) fills a flat array
p[0..n] bottom-up; because the recurrence only ever reads backward, no explicit
cache is needed - the natural left-to-right fill guarantees every dependency is already
computed. Python handles large integers natively, whereas the C code carries a base-10^9
multi-limb big-integer type. This is the only approach where partition values are
subtracted, so the C big integer here implements both bigint_add and
bigint_sub. The payoff is dramatic: at n = 1000 the C solution runs
in 0.0007 s and the Python solution in 0.0008 s.
s1 - Memoized 2D Partition Recursion (number, slots)
This approach defines count(number, slots) as the number of partitions of
number whose largest part is at most slots. The recurrence sums over
each possible largest part n in 1..slots:
count(number - n, min(number - n, n)), plus 1 when
number <= slots to count the whole-number partition [number]. The
second argument min(number - n, n) enforces a non-increasing order - the next part
may not exceed the current part n, nor the remaining sum - and that constraint is
precisely what prevents counting reorderings of the same partition. The base case is
number <= 1 returning number itself.
The Python version (p0076_s1.py) memoizes the core with
functools.lru_cache.
The C version (p0076_s1.c) translates the same recursion into a bottom-up flat 2D
table indexed by nb*(num+1)+sl, filling nb from 2 upward so every
count(nb-n, ...) it reads (which always has a smaller first argument) is already
written. With O(n^2) states and O(n) work each, this is O(n^3)
dynamic programming,
which is why at n = 1000 the C build takes 2.5217 s and the Python build 0.8583 s -
three to four orders of magnitude slower than s0.
s2 - Explicit Partition Enumeration
The Python s2 (p0076_s2.py) materializes the actual partitions as lists of lists
and returns their count. It carries a safe_limit = 50 guard that raises
OverflowError for larger inputs, which is why the benchmark reports overflow at
n = 100 and n = 1000. It also embeds
assert sum(partition) == number checks that serve as executable documentation of
the invariant. The C version (p0076_s2.c) keeps the same recursion structure but
abandons list construction (which would be memory-prohibitive at this scale); instead it
increments a big-integer counter when n == nb (the leaf partition [n])
and otherwise accumulates the table value dp[nb-n][min(nb-n, n)]. The result
matches s1 exactly and runs in the same O(n^3) class - 2.4439 s at n = 1000 -
needing only an add-in-place, an increment, and a decrement on the big-integer type.