notes.html
problem 77 · 78 lines
<article>
<h3>Problem Analysis</h3>
<p>
This problem asks me to count, for each integer n, the number of ways it can be written as an
unordered sum of primes (with repetition allowed), and to find the first n whose count exceeds a
given threshold. This is a constrained form of the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Partition_(number_theory)" rel="noopener noreferrer" target="_blank">integer partition</a>
problem: a partition of n is any multiset of positive integers summing to n, and here the allowed
parts are restricted to <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">primes</a>.
The word "unordered" is the crux: <code>7 + 3</code> and <code>3 + 7</code> describe the same
decomposition and must be counted once. The standard device for enforcing this is to impose a
canonical ordering on the parts - I require parts to be non-increasing, so each multiset is
reached through exactly one ordered representative.
</p>
<p>
The tractability insight is to parameterise a recursion by two quantities: the remaining sum and
a ceiling on the largest prime part still allowed. I call this ceiling <code>slots</code>. When I
select a prime p, every later part must be at most p, so the recursive call passes p as the new
ceiling - this single parameter eliminates double-counting. Because the same (number, slots) pair
recurs across many branches, I apply
<a class="reference-source" href="https://en.wikipedia.org/wiki/Memoization" rel="noopener noreferrer" target="_blank">memoization</a>
to cache each subproblem's answer, turning an exponential recursion into a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a>
computation. The number of distinct subproblems is O(N * pi(N)), where pi(N) is the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Prime-counting_function" rel="noopener noreferrer" target="_blank">prime-counting function</a>,
and each subproblem does O(pi(N)) work. Since the answer for the largest test case lies near
n = 104, this is effectively instantaneous.
</p>
<h3>Solution Approach</h3>
<h4>Count-only memoised recursion (p0077_s0.py and p0077_s0.c)</h4>
<p>
My primary approach computes only the <em>count</em> of prime partitions, never the partitions
themselves. The recursive function <code>num_prime_partitions(number, slots)</code> returns the
number of ways to partition <code>number</code> using prime parts each at most <code>slots</code>.
The base cases are direct: if <code>number == 0</code> I have completed a valid partition and
return 1; if <code>slots < 2</code> no prime fits so I return 0. For the recursive step I
iterate over every prime p up to <code>min(number, slots)</code> and sum
<code>num_prime_partitions(number - p, p)</code>. Passing p (not <code>slots</code>) as the next
ceiling is precisely what enforces the non-increasing constraint and prevents duplicate counting.
</p>
<p>
In Python I let
<a class="reference-source" href="https://docs.python.org/3/library/functools.html#functools.lru_cache" rel="noopener noreferrer" target="_blank"><code>functools.lru_cache</code></a>
handle the cache transparently. In C I hand-roll an
<a class="reference-source" href="https://en.wikipedia.org/wiki/Open_addressing" rel="noopener noreferrer" target="_blank">open-addressing</a>
hash table: each (number, slots) key is hashed to a bucket, and linear probing resolves
collisions. I sized the table at 2^18 (262144) buckets so the load factor stays low across the
input range, and the modulo reduces to a bitwise AND because the size is a power of two. The
driver iterates n from 1 upward, calling <code>num_prime_partitions(n, n)</code>, and returns the
first n whose count reaches the threshold. This is the fastest design because it allocates nothing
beyond the memo table and stores a single integer per subproblem.
</p>
<h4>Enumeration-based recursion (p0077_s1.py and p0077_s1.c)</h4>
<p>
The second approach constructs and stores every individual partition as a list of integers,
returning a list-of-lists; the answer is then just its length. In Python,
<code>get_prime_partitions_simple_recursion</code> returns <code>list[list[int]]</code> and is
memoised by the (number, slots) key. Each recursive call prepends the chosen prime p to every
sub-partition returned for the remainder. An assertion verifies each partition sums correctly - a
useful debugging aid - and a <code>safe_limit</code> parameter (default 50) guards against runaway
growth. That guard is exactly why the Python enumeration version reports <code>overflow</code> for
thresholds 5000 and 50000: the answers (71 and 104) exceed the limit, so the search aborts before
reaching them.
</p>
<p>
The C version is far more involved because C offers no built-in dynamic lists or garbage
collection. I define a <code>Partition</code> struct (an int array plus a length) and a
<code>PartList</code> struct (a growable array of Partitions). The memo is a separate hash table
of <code>PartList</code> values, sized at 2^14. For each uncached query I iterate over primes,
<code>malloc</code> and <code>memcpy</code> a new array with p prepended to each sub-partition,
and append it to the result. Memory ownership is delicate: memo entries own their arrays, and
<code>enum_memo_init</code> frees them all before clearing the table. The C driver raises its own
<code>g_safe_limit</code> to 200, large enough to find the answer for every test case. This
approach allocates and copies O(count) int arrays per subproblem, so it is dramatically slower
than the count-only version.
</p>
</article>