Product-maximising partitions

Let $N=\{1,2,\dots \}$ be the set of positive integers. A partition of $n\in 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\ge 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\times 2\times 3=6$, while the parts in $3+3$ have product $3\times 3=9$. Our goal is to find a product-maximising partition for arbitrary $n$.

Let $x_1+x_2+\cdots +x_k$ be a partition of $n$. If $x_1=1$ then $k\ge 2$ (since $n\ge 2$) and $$\begin{array}{cc}\prod _{i=1}^k{x}_i& =1\times x_2\times \prod _{i=3}^k{x}_i\\ & <(1+x_2)\times \prod _{i=3}^k{x}_i\end{array}$$ because the $x_i$ are strictly positive.¹ Thus, replacing the partition $x_1+x_2+\cdots +x_k$ with $(1+x_2)+x_3+\cdots +x_k$ delivers a greater product. Since the $x_i$ can be rearranged arbitrarily, it follows that product-maximising partitions contain no parts equal to one. Similarly, if $x_1>4$ then $$\begin{array}{cc}\prod _{i=1}^k{x}_i& =x_1\times \prod _{i=2}^k{x}_i\\ & <3(x_1-3)\times \prod _{i=2}^k{x}_i,\end{array}$$ so we can obtain a greater product by replacing $x_1+x_2+\cdots +x_k$ with $3+(x_1-3)+x_2+\cdots +x_k$. It follows that product-maximising partitions contain no parts greater than four. But $2\times 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 $2^3=8<9=3^2$.

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\in N\cup \left\{0\right\}$ and $r\in \{0,1,2\}$, the maximum product we can obtain is $$P\left(n\right)=\{\begin{array}{cc}{3}^q& \text{if}r=0\\ 2^2\times 3^{q-1}& \text{if}r=1\\ 2\times 3^q& \text{if}r=2.\end{array}$$ We can approximate this solution by relaxing the integrality constraint on the $x_i$. For any given $k$, we can find the vector $x^{\ast }$ that solves $$\begin{array}{}\underset{x\in R_{+}^k}{max}\prod _{i=1}^k{x}_i\text{subject to}\sum _{i=1}^k{x}_i=n,& \text{(1)}\end{array}$$ where $R_{+}$ is the set of positive real numbers. This vector has $x_i^{\ast }=n/k$ for each $i\in \{1,2,\dots ,k\}$, so that ${\prod }_{i=1}^k{x}_i^{\ast }=(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\approx 2.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}\left(n\right)=max\{{\left(\frac{n}{\lfloor n/e\rfloor }\right)}^{\lfloor n/e\rfloor },{\left(\frac{n}{\lceil n/e\rceil }\right)}^{\lceil n/e\rceil }\}$$ of $P\left(n\right)$, 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\left(n\right)$ and $\hat{P}\left(n\right)$ for various $n$. Since $\{2,3\}\subset R_{+}$, the partition of $n$ using twos and as many threes as possible is a feasible, but not necessarily optimal, solution to $\left(1\right)$. Thus $P\left(n\right)\le \hat{P}\left(n\right)$ for each $n\ge 2$. The multiplicative error $\hat{P}\left(n\right)/P\left(n\right)$ 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\left(n\right)$.