Detailed mathematical approach

Problem Summary

A partition of \(n\) is balanceable if its parts can be split into two groups with the same total. A partition is \(k\)-bounded if every part is at most \(k\). The problem asks for the least positive integer \(f(k)\) such that every \(k\)-bounded partition of \(f(k)\) is balanceable, and then asks for \(f(10^8)\bmod(10^9+7)\). The C++, Python, and Java implementations do not enumerate partitions at all; they rely on a structural theorem that turns the problem into one least-common-multiple computation.

Mathematical Approach

Write

$L_k=\operatorname{lcm}(1,2,\dots,k).$

The key identity behind the implementations is

$\boxed{f(k)=2L_k.}$

Once this is proved, the remaining work is purely arithmetic.

Step 1: Translate the definition into a subset-sum statement

Suppose a \(k\)-bounded partition of \(n\) is written as

$n=\lambda_1+\lambda_2+\cdots+\lambda_m,\qquad 1\le \lambda_i\le k.$

It is balanceable exactly when some submultiset of the parts has sum \(n/2\). Equivalently, there exists an index set \(I\subseteq\{1,\dots,m\}\) such that

$\sum_{i\in I}\lambda_i=\frac{n}{2}.$

So if we can show that every \(k\)-bounded partition of \(2L_k\) has a submultiset summing to \(L_k\), then \(f(k)\le 2L_k\). The opposite inequality comes from divisibility constraints.

Step 2: Monochromatic partitions force a lower bound

Fix any \(j\) with \(1\le j\le k\). Consider the partition of \(n\) consisting only of parts of size \(j\):

$n=\underbrace{j+j+\cdots+j}_{n/j\text{ terms}}.$

If this partition is balanceable, the two sides must contain the same number of \(j\)'s, so \(n/j\) has to be even. Therefore

$2j\mid n\qquad \text{for every }1\le j\le k.$

This implies

$2\operatorname{lcm}(1,2,\dots,k)=2L_k\mid n.$

Hence no universal value can be smaller than \(2L_k\), so

$f(k)\ge 2L_k.$

Step 3: View a partition of \(2L_k\) inside the cyclic group \(\mathbb{Z}/L_k\mathbb{Z}\)

Now take an arbitrary \(k\)-bounded partition of \(2L_k\):

$2L_k=a_1+a_2+\cdots+a_r,\qquad 1\le a_i\le k.$

Because every integer from \(1\) to \(k\) divides \(L_k\), each part \(a_i\) also divides \(L_k\). Regard each \(a_i\) as an element of the cyclic group \(\mathbb{Z}/L_k\mathbb{Z}\). The whole sequence has sum

$a_1+\cdots+a_r\equiv 2L_k\equiv 0 \pmod{L_k},$

so it is a zero-sum sequence in that group.

For a part \(a_i\), its order in \(\mathbb{Z}/L_k\mathbb{Z}\) is

$\operatorname{ord}(a_i)=\frac{L_k}{a_i},$

since \(a_i\mid L_k\).

Step 4: A standard minimal zero-sum bound gives the upper bound

Assume, for contradiction, that this partition is not balanceable. Then no proper nonempty submultiset of \(\{a_1,\dots,a_r\}\) sums to \(L_k\). In modular language that means the zero-sum sequence is minimal: no proper nonempty subsequence sums to \(0\) in \(\mathbb{Z}/L_k\mathbb{Z}\).

Define its cross number by

$\kappa=\sum_{i=1}^{r}\frac{1}{\operatorname{ord}(a_i)}=\sum_{i=1}^{r}\frac{a_i}{L_k}=\frac{2L_k}{L_k}=2.$

A standard theorem from zero-sum theory states that every minimal zero-sum sequence in a finite cyclic group satisfies

$\kappa\le 1.$

Our sequence has \(\kappa=2\), which is impossible. Therefore a proper nonempty zero-sum subsequence must exist. Its ordinary sum is a positive multiple of \(L_k\), but it is strictly smaller than the total sum \(2L_k\), so its sum can only be

$L_k.$

That is exactly the required balanced split. Thus every \(k\)-bounded partition of \(2L_k\) is balanceable, and therefore

$f(k)\le 2L_k.$

Step 5: Combine the bounds and rewrite the result with prime powers

The lower and upper bounds match, so

$f(k)=2L_k.$

To compute \(L_k\), factor it prime by prime. For each prime \(p\le k\), the exponent is the largest integer \(e\) such that \(p^e\le k\):

$e_p=\max\{e\in\mathbb{Z}_{\ge 0}:p^e\le k\}=\left\lfloor\log_p k\right\rfloor.$

Therefore

$L_k=\prod_{p\le k}p^{e_p},\qquad f(k)=2\prod_{p\le k}p^{e_p}.$

This is the exact arithmetic form evaluated by the implementations.

Worked Example: \(k=3\)

For \(k=3\),

$L_3=\operatorname{lcm}(1,2,3)=6,$

so the formula predicts

$f(3)=2L_3=12.$

The lower bound already forces divisibility by \(2\), \(4\), and \(6\), hence by \(12\). For the upper bound, every \(3\)-bounded partition of \(12\) uses parts drawn from \(\{1,2,3\}\), all of which divide \(6\). For example,

$12=3+3+2+2+1+1$

is balanceable because

$6=3+2+1=3+2+1.$

The theorem above guarantees that the same must happen for every \(3\)-bounded partition of \(12\), which matches the small checkpoint \(f(3)=12\).

How the Code Works

The C++, Python, and Java implementations never manipulate partitions directly. They first generate all primes up to \(k\) with an odd-only sieve: the prime \(2\) is handled explicitly, and only odd candidates are stored afterward. For each prime \(p\), the implementation repeatedly multiplies by \(p\) until the next multiplication would exceed \(k\); this produces the largest prime power \(p^{e_p}\le k\).

Those prime powers are multiplied into a running product modulo \(10^9+7\). After the product for \(L_k\) is complete, the implementation multiplies once more by \(2\) to obtain \(f(k)\bmod(10^9+7)\). In short, the code evaluates the closed form directly and avoids any exponential partition search.

Complexity Analysis

Let the input be \(k\). Building the sieve up to \(k\) costs \(O(k\log\log k)\) time and \(O(k)\) memory. The second phase loops over the primes and climbs through the prime powers \(p,p^2,p^3,\dots\le k\), which costs

$\sum_{p\le k} O(\log_p k),$

a lower-order term compared with the sieve. Therefore the overall algorithm runs in \(O(k\log\log k)\) time and uses \(O(k)\) memory.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=772
2. Integer partitions: Wikipedia — Partition (number theory)
3. Least common multiple: Wikipedia — Least common multiple
4. Cyclic groups: Wikipedia — Cyclic group
5. Zero-sum background: Wikipedia — Erdős–Ginzburg–Ziv theorem
6. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes