Maximizing product in integer partitions

The other day I saw this tweet which provided this puzzle: Find sequence A such that for some fixed N, \mathrm{sum}(A) = N and \mathrm{prod}(A) is max.

In this post I’ll first build some intuition for which numbers are worth putting in A, and then turn that into a proof.


Intuition

The next lemma tells us that for numbers greater than 5, it is better to use 2s:

Lemma 1: n>5 \Longrightarrow 2^{\left\lfloor n/2\right\rfloor} \ge n (expand for proof)

Base cases:

  • n=6: 2^3 \ge 6
  • n=7: 2^3 \ge 7

Inductive hypothesis:

Assume the inequality holds true for k\ge6

2^{\left\lfloor k/2\right\rfloor} \ge k

Mult both sides by 2

\begin{array}{rcl} 2\cdot 2^{\left\lfloor k/2\right\rfloor} &\ge& 2k\\ 2^{\left\lfloor k/2\right\rfloor+1} &\ge& 2k\\ 2^{\left\lfloor (k+2)/2\right\rfloor} &\ge& 2k \end{array}

and since k\ge2, then add k to both sides to get 2k \ge k+2

2^{\left\lfloor (k+2)/2\right\rfloor} \ge 2k \ge k+2

i.e. from P(k) it follows P(k+2) and since we cover both odd/even in base, the proof is complete


So if N=18, instead of (9,9) which would give prod 9^2, it is better to use (2,2,2,2,2,2,2,2,2) to get prod 2^9

But what about numbers equal or less than 5?

  • Number 1: product is unchanged, try not to use
  • Number 4: 4=2\cdot2, product unchanged
  • Number 5: 2\cdot2 < 5, but 2\cdot3 > 5, so seq (2,3) is better than both (2,2,1) and (5)
  • Number 2: (2) vs (1,1) and it’s obvious that (2) is better
  • Number 3: interesting case is (2,2,2) vs (3,3). obviously 3^2>2^3 so 3s win here

Putting it together

For N\ge2, start with a seq of positive integers that gives max prod.

By Lemma 1, replace each n>5 with \left\lfloor n/2\right\rfloor 2s (and one 1 if n is odd).

There can’t be any 1s or 5s, since (1,a) \to (a+1) and (5) \to (2,3) would increase prod.

Replace each 4 with (2,2). now we only have 2s and 3s, and at most two 2s since (2,2,2) \to (3,3) increases prod.

So the number of 2s is determined by N\bmod 3:

N\bmod 3 = 0: no 2s
N\bmod 3 = 1: two 2s
N\bmod 3 = 2: one 2

And we fill the rest with 3s. For example, for N=12, use (3,3,3,3) to get prod 3^4=81. For N=1, the only seq is (1).

Python code
def best_seq(n):
if n == 1: return [1]
twos = [0, 2, 1][n % 3]
return [3] * ((n - 2 * twos) // 3) + [2] * twos

Leave a Reply