Detailed mathematical approach

Problem Summary

For each positive integer \(n\), let \(f(n)\) be the largest product obtainable from a partition of \(n\) into distinct positive integers, and let \(m(n)\) be the number of parts in an optimal partition. Project Euler 374 asks for

$$M(N)=\sum_{n=1}^{N} f(n)m(n)$$

at \(N=10^{14}\), reduced modulo

$$P=982451653.$$

The local C++, Python, and Java solutions all exploit the same fact: optimal partitions fall into simple \(\Theta(\sqrt{n})\)-sized blocks, so the program never searches over partitions explicitly.

Mathematical Approach

Step 1: The optimal partition is almost consecutive

Write an optimal partition with \(k\) parts as

$$a_1 \lt a_2 \lt \cdots \lt a_k,\qquad a_1+\cdots+a_k=n.$$

If some adjacent gap is at least \(3\), say \(a_{i+1}-a_i\ge 3\), then replacing \((a_i,a_{i+1})\) by \((a_i+1,a_{i+1}-1)\) keeps the sum fixed, preserves distinctness, and increases the product because

$$ (a_i+1)(a_{i+1}-1)-a_i a_{i+1} = a_{i+1}-a_i-1 \gt 0. $$

Therefore every optimal partition has adjacent differences only \(1\) or \(2\). For \(n\ge 2\), the maximizing partitions are thus “near-consecutive”: a run of consecutive integers with at most one missing value.

Step 2: The block parameter \(m\)

The baseline near-consecutive partition with \(m\) parts is

$$\{2,3,\dots,m+1\},$$

whose sum is

$$T_m = 2+3+\cdots+(m+1)=\frac{m(m+3)}{2}.$$

This is the left endpoint of the block where the optimal partition has exactly \(m\) parts. Hence the correct block index for a given \(n\) is

$$m=\max\left\{r:\frac{r(r+3)}{2}\le n\right\}.$$

The code computes this with the integer-square-root estimate

$$m\approx \frac{\sqrt{8n+9}-3}{2},$$

and then adjusts by at most a couple of integer steps to remove rounding issues.

Step 3: Closed form inside one block

Write

$$n=T_m+s,\qquad 0\le s\le m+1.$$

Since

$$T_{m+1}=\frac{(m+1)(m+4)}{2}=T_m+m+2,$$

the full \(m\)-block is the interval

$$T_m \le n \le T_{m+1}-1=\frac{(m+1)(m+4)}{2}-1.$$

Throughout this whole interval the optimal partition size is constant:

$$m(n)=m.$$

Step 4: The optimal partition shapes

If \(0\le s\le m\), the optimal partition is obtained from the consecutive set \(\{2,3,\dots,m+2\}\) by deleting exactly one value:

$$\{2,3,\dots,m+2\}\setminus\{m+2-s\}.$$

Its sum is

$$ \left(\sum_{j=2}^{m+2} j\right)-(m+2-s) = \frac{m(m+3)}{2}+s = n, $$

and its product is

$$f(n)=\frac{(m+2)!}{m+2-s}.$$

Multiplying by the part count gives

$$f(n)m(n)=m\frac{(m+2)!}{m+2-s},\qquad 0\le s\le m.$$

If \(s=m+1\), the “deleted value” would have to be \(1\), so the shape changes to

$$\{3,4,\dots,m+1,m+3\}.$$

Its product is

$$f(n)=\frac{(m+3)!}{2(m+2)},$$

hence

$$f(n)m(n)=m\frac{(m+3)!}{2(m+2)}.$$

This is exactly the piecewise formula implemented by all three solution files. The code keeps the middle case \(s=m\) as a separate branch, but mathematically it is simply the denominator-\(2\) instance of the first formula.

Worked Example: \(n=10\)

We have

$$T_3=\frac{3\cdot 6}{2}=9,\qquad T_4=\frac{4\cdot 7}{2}=14,$$

so \(m=3\) and \(s=10-9=1\). Therefore the optimal partition is

$$\{2,3,4,5\}\setminus\{4\}=\{2,3,5\}.$$

Thus

$$f(10)=2\cdot 3\cdot 5=30,\qquad m(10)=3,\qquad f(10)m(10)=90,$$

which matches the checkpoint in the C++ verifier.

Step 5: Summing one whole block

For a complete block, first sum the \(m+1\) terms with \(0\le s\le m\):

$$ \sum_{s=0}^{m} m\frac{(m+2)!}{m+2-s} = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d}, $$

where we reindexed with \(d=m+2-s\). The final point of the block contributes

$$m\frac{(m+3)!}{2(m+2)}.$$

So the complete \(m\)-block contribution is

$$ B_m = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d} + m\frac{(m+3)!}{2(m+2)}. $$

This is why the implementation only needs a running factorial and a running harmonic-style sum of modular inverses.

Step 6: Modular inverses

Because \(P\) is prime and every denominator satisfies \(2\le d\le m_{\max}+3 \lt P\), all required inverses exist modulo \(P\). The code precomputes them in linear time via

$$\mathrm{inv}[1]=1,\qquad \mathrm{inv}[i]=-\left\lfloor\frac{P}{i}\right\rfloor\mathrm{inv}[P\bmod i]\pmod{P}.$$

This follows from writing \(P=qi+r\), so \(r\equiv -qi\pmod P\), then multiplying by \(r^{-1}i^{-1}\). Once the inverse table is built, every full block is processed in \(O(1)\) modular arithmetic.

How the Code Works

The C++, Python, and Java implementations are structurally identical. They first compute \(m_{\max}=\max\{m:T_m\le N\}\), then precompute modular inverses up to \(m_{\max}+3\). During the main loop they maintain

$$\texttt{fact}=(m+2)!\pmod P,\qquad \texttt{harmonic}=\sum_{d=2}^{m+2}\frac{1}{d}\pmod P.$$

For each \(m\), the code knows the block start \(T_m\), the block end \(T_{m+1}-1\), and how much of that block is still inside the target range. All fully covered blocks use the closed form above; only the last block may be truncated, and the code handles that by summing the needed inverse segment explicitly.

The C++ file also checks the derivation against small exact values:

$$f(5)m(5)=12,\qquad f(10)m(10)=90,\qquad \sum_{n=1}^{100} f(n)m(n)=1683550844462.$$

Complexity Analysis

Since \(T_m\sim m^2/2\), the maximal block index satisfies \(m_{\max}=\Theta(\sqrt{N})\). Precomputing inverses, advancing the running factorial, and iterating over all blocks therefore costs \(O(\sqrt{N})\) time. The inverse table uses \(O(\sqrt{N})\) memory. Only the final block can be partial, so there is no hidden extra logarithmic factor.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=374
2. Integer partition: Wikipedia — Integer partition
3. Modular multiplicative inverse: Wikipedia — Modular multiplicative inverse
4. Competitive programming reference for the inverse recurrence: cp-algorithms — Modular inverse