0

For $n\in\mathbb{N}$ choose $k_1,\dots,k_l\in\mathbb{N}$ so that $\sum_{i=1}^{l}k_i = n$. Set $k = \prod_{i=1}^{l}k_i$.

What is the largest $k$ that one can get? Is there an explicit formula?

What else can be said about this?

-- Some thoughts --

In this table I give the values for $k$ and one sequence of $k_1,\dots,k_l$ (where $k_1\geq k_2\geq\dots\geq k_l$) that gives this $k$ for $n\in\{1,\dots,10\}$: $$ \begin{array} {|r|r|r|} \hline n & k & (k_1,\dots,k_l) \\ \hline 1 & 1 & (1) \\ \hline 2 & 2 & (2) \\ \hline 3 & 3 & (3) \\ \hline 4 & 4 & (4); (2,2) \\ \hline 5 & 6 & (3,2) \\ \hline 6 & 9 & (3,3) \\ \hline 7 & 12 & (4,3) \\ \hline 8 & 18 & (3,3,2) \\ \hline 9 & 27 & (3,3,3) \\ \hline 10 & 36 & (4,3,3) \\ \hline \end{array} $$

So, as for $n=5$ it is already $k=6$, one should choose $k_1\leq4$. And of course, to get a large $k$ one should choose $k_l\geq2$. And somewhat the $3$ seems more "effective", though I am not at all sure why.

So I guess to construct the sequence one takes as many threes as possible, and if the reminder of $n:3$ is $0$, one has finished, if it is $1$, one increments one $3$ to a $4$, and if it is $2$, one simply adds this to the sequence.

C. Maier
  • 71
  • Have you worked this out for small n? Do you see a pattern? Share your thoughts. – Matthew Conroy Apr 26 '16 at 22:23
  • 2
    Why $3$? If you break it into $n$ parts, the product is maximized when the $n$ parts are about the same size, and is then about $(k/n)^n = \exp(n (\log k -\log n))$. This is maximized when the number of parts is $n = k/e$; i.e., each part has size $k/n = e \approx 3$. – mjqxxxx Apr 26 '16 at 23:33
  • 2
    The sequence of maximal products is here in OEIS: https://oeis.org/A000792 – Steve Kass Apr 27 '16 at 01:14
  • @mjqxxxx that's the right answer, you should post it as one (with a few details) – Adam Hughes Apr 27 '16 at 16:45

2 Answers2

5

Note that any $k_j = 1$ is wasted: better to combine it with some other $k_i$, since $1 \cdot k_i < k_i + 1$.

Any value $4$ or higher, we might as well split off a $2$: $x < 2 (x-2)$ if $x \ge 4$. So we're left with $2$'s and $3$'s. (Actually a $4$ is interchangeable with two $2$'s, but let's think in terms of $2$'s and $3$'s)

$2^3 < 3^2$, so any three $2$'s are better redistributed as two $3$'s. Thus besides $3$'s we will have either $0$, $1$, or $2$ $2$'s, and this will be determined by the congruence class of $n \mod 3$: if $n \equiv 0 \mod 3$, there are no $2$'s, if $n \equiv 1 \mod 3$ there are two (or equivalently a single $4$), and if $n \equiv 2 \mod 3$ there is one.

Robert Israel
  • 448,999
1

Following up on Steve Kass's comment, the sequence of maximum products is http://oeis.org/A000792, which includes a three-case explicit formula: $$a(n) = \begin{cases}3^k & \text{if } n = 3k,\\ 4\cdot3^{k-1} & \text{if } n = 3k+1,\\ 2\cdot3^k & \text{if } n = 3k+2,\end{cases}$$ with $k>0$ required for the first two cases.

Brian Hopkins
  • 2,257