notes.html
problem 78 · 33 lines
<article>
<h3>Problem Analysis</h3>
<p>
This problem asks for the smallest <code>n</code> whose value under the <a class="reference-source" href="https://en.wikipedia.org/wiki/Partition_(number_theory)" rel="noopener noreferrer" target="_blank">partition function</a> <code>p(n)</code> - the number of ways to write <code>n</code> 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 <code>p(n)</code> grows. By the <a class="reference-source" href="https://en.wikipedia.org/wiki/Partition_(number_theory)#Asymptotic_growth" rel="noopener noreferrer" target="_blank">Hardy-Ramanujan asymptotic</a>, <code>p(n)</code> grows roughly like <code>exp(pi*sqrt(2n/3))</code>, so any approach that explicitly enumerates partitions is hopeless even for small <code>n</code>. The entire problem hinges on having a fast recurrence for <code>p(n)</code>.
</p>
<p>
That recurrence is <a class="reference-source" href="https://en.wikipedia.org/wiki/Pentagonal_number_theorem" rel="noopener noreferrer" target="_blank">Euler's pentagonal number theorem</a>: <code>p(n) = sum over k != 0 of (-1)^(k+1) * p(n - g(k))</code>, where <code>g(k) = k(3k-1)/2</code> are the <a class="reference-source" href="https://oeis.org/A001318" rel="noopener noreferrer" target="_blank">generalized pentagonal numbers</a> <code>1, 2, 5, 7, 12, 15, 22, 26, ...</code> generated by letting <code>k = 1, -1, 2, -2, 3, -3, ...</code>. The signs come in pairs: <code>+, +, -, -, +, +, ...</code>. Because <code>g(k)</code> grows like <code>3k^2/2</code>, only about <code>O(sqrt(n))</code> pentagonal numbers do not exceed <code>n</code>, so each <code>p(n)</code> costs <code>O(sqrt(n))</code> given all smaller values; building the table up to the answer <code>N</code> is therefore <code>O(N*sqrt(N))</code>. Two further observations clean up the implementation. First, since we only test divisibility we can work entirely in <a class="reference-source" href="https://en.wikipedia.org/wiki/Modular_arithmetic" rel="noopener noreferrer" target="_blank">modular arithmetic</a>, 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 <a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a> in a flat array indexed by <code>n</code>.
</p>
<h3>Solution Approach</h3>
<h4>Euler Pentagonal Recurrence with Modular Reduction (Python and C)</h4>
<p>
The Python and C files implement the same algorithm; the C version exists purely for speed. Both are structured as a bottom-up <a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a> build-up.
</p>
<p>
<strong>Base case.</strong> I seed <code>partitions[0] = 1</code>. 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.
</p>
<p>
<strong>Outer loop.</strong> I iterate <code>n = 1, 2, 3, ...</code> with no fixed upper bound, because I do not know the answer in advance. In Python this is <code>itertools.count(1)</code>; in C it is a <code>while(1)</code> with an internal <code>return</code>.
</p>
<p>
<strong>Inner loop - applying the recurrence.</strong> For each <code>n</code> I accumulate <code>pval</code> by iterating <code>k = 1, 2, 3, ...</code>. Each <code>k</code> contributes two <a class="reference-source" href="https://oeis.org/A001318" rel="noopener noreferrer" target="_blank">generalized pentagonal numbers</a> at once: the positive-index value <code>g(k) = k(3k-1)/2</code> and the negative-index value <code>g(-k) = k(3k+1)/2</code>. Computing both in one iteration lets a single sign variable <code>(-1)^(k-1)</code> cover the pair. The loop terminates as soon as <code>g(k) > n</code> - 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 (<code>g(-k) <= n</code>) because it can exceed <code>n</code> while <code>g(k)</code> does not.
</p>
<p>
<strong>Reduce and test.</strong> After the inner loop I reduce <code>pval</code> with <a class="reference-source" href="https://en.wikipedia.org/wiki/Modular_arithmetic" rel="noopener noreferrer" target="_blank">modular arithmetic</a> and store it, then check for zero. The first <code>n</code> giving zero is the answer. A language difference surfaces here: Python's <code>%</code> always returns a non-negative result, so <code>partition_value %= divisor</code> suffices. In C the alternating subtractions can leave <code>pval</code> negative, so I use the idiom <code>((pval % divisor) + divisor) % divisor</code> to land cleanly in <code>[0, divisor)</code>.
</p>
<p>
<strong>Storage.</strong> The Python list simply appends each new value. The C version pre-allocates 100,000 entries and doubles capacity with <code>realloc</code> 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.
</p>
<p>
One stylistic note on the Python: it decorates the <code>pentagonal</code> helper with <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>. Since <code>pentagonal</code> is a pure formula evaluated once per <code>(n, k)</code> pair, the cache provides no real benefit here - the algorithmic substance is identical to the C version.
</p>
</article>