Problem Analysis
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
integer partition
problem: a partition of n is any multiset of positive integers summing to n, and here the allowed
parts are restricted to primes.
The word "unordered" is the crux: 7 + 3 and 3 + 7 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.
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 slots. 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
memoization
to cache each subproblem's answer, turning an exponential recursion into a
dynamic programming
computation. The number of distinct subproblems is O(N * pi(N)), where pi(N) is the
prime-counting function,
and each subproblem does O(pi(N)) work. Since the answer for the largest test case lies near
n = 104, this is effectively instantaneous.
Solution Approach
Count-only memoised recursion (p0077_s0.py and p0077_s0.c)
My primary approach computes only the count of prime partitions, never the partitions
themselves. The recursive function num_prime_partitions(number, slots) returns the
number of ways to partition number using prime parts each at most slots.
The base cases are direct: if number == 0 I have completed a valid partition and
return 1; if slots < 2 no prime fits so I return 0. For the recursive step I
iterate over every prime p up to min(number, slots) and sum
num_prime_partitions(number - p, p). Passing p (not slots) as the next
ceiling is precisely what enforces the non-increasing constraint and prevents duplicate counting.
In Python I let
functools.lru_cache
handle the cache transparently. In C I hand-roll an
open-addressing
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 num_prime_partitions(n, n), 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.
Enumeration-based recursion (p0077_s1.py and p0077_s1.c)
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,
get_prime_partitions_simple_recursion returns list[list[int]] 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 safe_limit parameter (default 50) guards against runaway
growth. That guard is exactly why the Python enumeration version reports overflow for
thresholds 5000 and 50000: the answers (71 and 104) exceed the limit, so the search aborts before
reaching them.
The C version is far more involved because C offers no built-in dynamic lists or garbage
collection. I define a Partition struct (an int array plus a length) and a
PartList struct (a growable array of Partitions). The memo is a separate hash table
of PartList values, sized at 2^14. For each uncached query I iterate over primes,
malloc and memcpy 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
enum_memo_init frees them all before clearing the table. The C driver raises its own
g_safe_limit 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.