Product-maximising partitions

Let N={1,2,…} be the set of positive integers. A partition of n∈N is a way of writing n as a sum of positive integers, called parts. For example, 1+2+3 is a partition of 6, with parts 1, 2, and 3. Partitions are unique up to rearrangement: 1+2+3 and 3+2+1 are the same partition, but 1+2+3 and 3+3 are different partitions.

This post discusses the following problem:

Let n≥2 be a positive integer. Find a partition of n whose parts have maximum product.

For example, the parts in 1+2+3 have product 1×2×3=6, while the parts in 3+3 have product 3×3=9. Our goal is to find a product-maximising partition for arbitrary n.

Let x1+x2+⋯+xk be a partition of n. If x1=1 then k≥2 (since n≥2) and k∏i=1xi=1×x2×k∏i=3xi<(1+x2)×k∏i=3xi because the xi are strictly positive.¹ Thus, replacing the partition x1+x2+⋯+xk with (1+x2)+x3+⋯+xk delivers a greater product. Since the xi can be rearranged arbitrarily, it follows that product-maximising partitions contain no parts equal to one. Similarly, if x1>4 then k∏i=1xi=x1×k∏i=2xi<3(x1−3)×k∏i=2xi, so we can obtain a greater product by replacing x1+x2+⋯+xk with 3+(x1−3)+x2+⋯+xk. It follows that product-maximising partitions contain no parts greater than four. But 2×2=4 and 2+2=4, so we can replace each four with two twos without reducing the parts’ product. Thus, we can obtain a product-maximising partition using only twos and threes. Finally, if a partition contains three twos then we should replace them with two threes, since 2+2+2=3+3 but 23=8<9=32.

To summarise, we can obtain a product-maximising partition using only twos and threes, with as many threes as possible. Letting n=3q+r for some q∈N∪{0} and r∈{0,1,2}, the maximum product we can obtain is P(n)={3qif r=022×3q−1if r=12×3qif r=2. We can approximate this solution by relaxing the integrality constraint on the xi. For any given k, we can find the vector x∗ that solves max where \R_+ is the set of positive real numbers. This vector has x_i^*=n/k for each i\in\{1,2,\ldots,k\}, so that \prod_{i=1}^kx_i^*=(n/k)^k.² If there was no integrality constraint on k then we could maximise (n/k)^k by choosing k=n/e, where e\approx2.718 is Euler’s constant. But k must be an integer, so we should round it to the nearest integer in whatever direction delivers the greatest value of (n/k)^k. Doing so delivers an estimate \hat{P}(n)=\max\left\{\left(\frac{n}{\lfloor n/e\rfloor}\right)^{\lfloor n/e\rfloor},\left(\frac{n}{\lceil n/e\rceil}\right)^{\lceil n/e\rceil}\right\} of P(n), where x\mapsto\lfloor x\rfloor and x\mapsto\lceil x\rceil are the floor (“round down”) and ceiling (“round up”) functions.

The table below compares P(n) and \hat{P}(n) for various n. Since \{2,3\}\subset\mathbb{R}_+, the partition of n using twos and as many threes as possible is a feasible, but not necessarily optimal, solution to (1). Thus P(n)\le\hat{P}(n) for each n\ge2. The multiplicative error \hat{P}(n)/P(n) grows exponentially with n because the exponent k\in\{\lfloor n/e\rfloor,\lceil n/e\rceil\} of (n/k)^k grows (increasingly linearly) with n, amplifying the error in the approximation n/k\sim e to each part in the partition underlying P(n).