Problem Analysis
This problem asks for the smallest n whose value under the partition function p(n) - the number of ways to write n as an unordered sum of positive integers - is divisible by one million. The phrase "separated into piles" is exactly the integer-partition notion: order does not matter, only the multiset of pile sizes. The crucial fact is how fast p(n) grows. By the Hardy-Ramanujan asymptotic, p(n) grows roughly like exp(pi*sqrt(2n/3)), so any approach that explicitly enumerates partitions is hopeless even for small n. The entire problem hinges on having a fast recurrence for p(n).
That recurrence is Euler's pentagonal number theorem: p(n) = sum over k != 0 of (-1)^(k+1) * p(n - g(k)), where g(k) = k(3k-1)/2 are the generalized pentagonal numbers 1, 2, 5, 7, 12, 15, 22, 26, ... generated by letting k = 1, -1, 2, -2, 3, -3, .... The signs come in pairs: +, +, -, -, +, +, .... Because g(k) grows like 3k^2/2, only about O(sqrt(n)) pentagonal numbers do not exceed n, so each p(n) costs O(sqrt(n)) given all smaller values; building the table up to the answer N is therefore O(N*sqrt(N)). Two further observations clean up the implementation. First, since we only test divisibility we can work entirely in modular arithmetic, reducing every value mod one million so nothing overflows or grows large. Second, the recurrence reads back many smaller values, making it a textbook case for dynamic programming in a flat array indexed by n.
Solution Approach
Euler Pentagonal Recurrence with Modular Reduction (Python and C)
The Python and C files implement the same algorithm; the C version exists purely for speed. Both are structured as a bottom-up dynamic programming build-up.
Base case. I seed partitions[0] = 1. There is exactly one way to partition zero - the empty sum - and this single seed is what makes every later term of the recurrence consistent. Without it the whole chain collapses to zeros.
Outer loop. I iterate n = 1, 2, 3, ... with no fixed upper bound, because I do not know the answer in advance. In Python this is itertools.count(1); in C it is a while(1) with an internal return.
Inner loop - applying the recurrence. For each n I accumulate pval by iterating k = 1, 2, 3, .... Each k contributes two generalized pentagonal numbers at once: the positive-index value g(k) = k(3k-1)/2 and the negative-index value g(-k) = k(3k+1)/2. Computing both in one iteration lets a single sign variable (-1)^(k-1) cover the pair. The loop terminates as soon as g(k) > n - that is the smaller of the two pentagonal numbers, so the test is conservative and never references a negative index. The second, larger term is guarded separately (g(-k) <= n) because it can exceed n while g(k) does not.
Reduce and test. After the inner loop I reduce pval with modular arithmetic and store it, then check for zero. The first n giving zero is the answer. A language difference surfaces here: Python's % always returns a non-negative result, so partition_value %= divisor suffices. In C the alternating subtractions can leave pval negative, so I use the idiom ((pval % divisor) + divisor) % divisor to land cleanly in [0, divisor).
Storage. The Python list simply appends each new value. The C version pre-allocates 100,000 entries and doubles capacity with realloc if it ever runs out. For the actual answer of 55,374 the resize never triggers, but the pattern keeps the code correct for larger divisors.
One stylistic note on the Python: it decorates the pentagonal helper with functools.lru_cache. Since pentagonal is a pure formula evaluated once per (n, k) pair, the cache provides no real benefit here - the algorithmic substance is identical to the C version.