notes.html
problem 76 · 100 lines
<article>
<h3>Problem Analysis</h3>
<p>
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
<a class="reference-source" href="https://en.wikipedia.org/wiki/Partition_(number_theory)" rel="noopener noreferrer" target="_blank">integer partition</a>
function <code>p(n)</code>, which counts the number of ways to write <code>n</code> as an
unordered sum of positive integers. The phrase "at least two" is the only twist: by convention
<code>p(n)</code> includes the single-term partition <code>n = n</code>, so the answer I want
is <code>p(n) - 1</code>. For <code>n = 5</code> we have <code>p(5) = 7</code>, and subtracting
the trivial partition <code>[5]</code> leaves the six sums shown in the problem. Recognizing
the problem as <code>p(n) - 1</code> is the unlocking insight: it turns an open-ended counting
question into one with well-studied recurrences.
</p>
<p>
Naive enumeration of partitions is exponential, but the structure is full of overlapping
subproblems, which is the hallmark situation for
<a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a>
(solving each distinct subproblem once and reusing the result). One natural formulation counts
partitions of <code>n</code> 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
<a class="reference-source" href="https://en.wikipedia.org/wiki/Pentagonal_number_theorem" rel="noopener noreferrer" target="_blank">Euler's pentagonal number theorem</a>,
which expresses <code>p(n)</code> as an alternating sum of only about O(sqrt(n)) earlier
partition values. Because the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Pentagonal_number" rel="noopener noreferrer" target="_blank">generalized pentagonal numbers</a>
<code>g(k) = k(3k-1)/2</code> grow quadratically in <code>k</code>, the recurrence touches only
roughly <code>sqrt(2n/3)</code> previous terms, yielding an O(n*sqrt(n)) algorithm. One more
practical concern: for <code>n = 1000</code> the answer has 32 decimal digits, well beyond a
64-bit integer, so any C solution must carry
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision arithmetic</a>.
</p>
<h3>Solution Approach</h3>
<h4>s0 - Euler's Pentagonal Number Theorem</h4>
<p>
I chose the pentagonal recurrence as my primary algorithm because it is asymptotically the best
of the three. The
<a class="reference-source" href="https://en.wikipedia.org/wiki/Pentagonal_number_theorem" rel="noopener noreferrer" target="_blank">pentagonal number theorem</a>
states <code>p(0) = 1</code> and, for <code>n >= 1</code>,
<code>p(n) = sum over k = 1, 2, 3, ... of (-1)^(k+1) * (p(n - g(k)) + p(n - g(-k)))</code>,
where <code>g(k) = k(3k-1)/2</code> is the k-th
<a class="reference-source" href="https://en.wikipedia.org/wiki/Pentagonal_number" rel="noopener noreferrer" target="_blank">generalized pentagonal number</a>
and any term with a negative argument is treated as zero. The alternating sign
<code>(-1)^(k+1)</code> adds for <code>k = 1, 3, 5, ...</code> and subtracts for
<code>k = 2, 4, 6, ...</code>, which I encode with <code>k % 2</code>.
</p>
<p>
The Python version (<code>p0076_s0.py</code>) writes the identity directly as a recursion
guarded by
<a class="reference-source" href="https://docs.python.org/3/library/functools.html#functools.lru_cache" rel="noopener noreferrer" target="_blank">functools.lru_cache</a>,
so each <code>p(i)</code> is evaluated once. The inner loop uses
<code>itertools.count(1)</code> and breaks the instant both <code>p(n - g(k))</code> and
<code>p(n - g(-k))</code> evaluate to zero, which happens once both pentagonal offsets exceed
<code>n</code>. The C version (<code>p0076_s0.c</code>) fills a flat array
<code>p[0..n]</code> 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
<em>subtracted</em>, so the C big integer here implements both <code>bigint_add</code> and
<code>bigint_sub</code>. The payoff is dramatic: at <code>n = 1000</code> the C solution runs
in 0.0007 s and the Python solution in 0.0008 s.
</p>
<h4>s1 - Memoized 2D Partition Recursion (number, slots)</h4>
<p>
This approach defines <code>count(number, slots)</code> as the number of partitions of
<code>number</code> whose largest part is at most <code>slots</code>. The recurrence sums over
each possible largest part <code>n</code> in <code>1..slots</code>:
<code>count(number - n, min(number - n, n))</code>, plus <code>1</code> when
<code>number <= slots</code> to count the whole-number partition <code>[number]</code>. The
second argument <code>min(number - n, n)</code> enforces a non-increasing order - the next part
may not exceed the current part <code>n</code>, nor the remaining sum - and that constraint is
precisely what prevents counting reorderings of the same partition. The base case is
<code>number <= 1</code> returning <code>number</code> itself.
</p>
<p>
The Python version (<code>p0076_s1.py</code>) memoizes the core with
<a class="reference-source" href="https://docs.python.org/3/library/functools.html#functools.lru_cache" rel="noopener noreferrer" target="_blank">functools.lru_cache</a>.
The C version (<code>p0076_s1.c</code>) translates the same recursion into a bottom-up flat 2D
table indexed by <code>nb*(num+1)+sl</code>, filling <code>nb</code> from 2 upward so every
<code>count(nb-n, ...)</code> 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)
<a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a>,
which is why at <code>n = 1000</code> the C build takes 2.5217 s and the Python build 0.8583 s -
three to four orders of magnitude slower than s0.
</p>
<h4>s2 - Explicit Partition Enumeration</h4>
<p>
The Python s2 (<code>p0076_s2.py</code>) materializes the actual partitions as lists of lists
and returns their count. It carries a <code>safe_limit = 50</code> guard that raises
<code>OverflowError</code> for larger inputs, which is why the benchmark reports overflow at
<code>n = 100</code> and <code>n = 1000</code>. It also embeds
<code>assert sum(partition) == number</code> checks that serve as executable documentation of
the invariant. The C version (<code>p0076_s2.c</code>) 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 <code>n == nb</code> (the leaf partition <code>[n]</code>)
and otherwise accumulates the table value <code>dp[nb-n][min(nb-n, n)]</code>. The result
matches s1 exactly and runs in the same O(n^3) class - 2.4439 s at <code>n = 1000</code> -
needing only an add-in-place, an increment, and a decrement on the big-integer type.
</p>
</article>