Maximum Product of Parts

Let $N$ be a positive integer and let $N$ be split into $k$ equal parts, $r = N/k$, so that $N = r + r + \cdots + r$.
Let $P$ be the product of these parts, $P = r \times r \times \cdots \times r = r^k$.
For example, if $11$ is split into five equal parts, $11 = 2.2 + 2.2 + 2.2 + 2.2 + 2.2$, then $P = 2.2^5 = 51.53632$.
Let $M(N) = P_{\mathrm{max}}$ for a given value of $N$.
It turns out that the maximum for $N = 11$ is found by splitting eleven into four equal parts which leads to $P_{\mathrm{max}} = (11/4)^4$; that is, $M(11) = 14641/256 = 57.19140625$, which is a terminating decimal.
However, for $N = 8$ the maximum is achieved by splitting it into three equal parts, so $M(8) = 512/27$, which is a non-terminating decimal.
Let $D(N) = N$ if $M(N)$ is a non-terminating decimal and $D(N) = -N$ if $M(N)$ is a terminating decimal.
For example, $\sum D(N)$ for $5 \le N \le 100$ is $2438$.
Find $\sum D(N)$ for $5 \le N \le 10000$.

Please note: This is a high-level combinatorics and calculus problem, typically found in competitive mathematics or higher-level coursework. Here’s a detailed solution.

The solution to this problem is largely based on the AM-GM Inequality (Arithmetic Mean-Geometric Mean Inequality), which for $k$ numbers $x_1, x_2, x_3, \dots, x_k$ says that

$\frac{x_1 + x_2 + x_3 + \dots + x_k}{k} \geq \sqrt[k]{x_1x_2x_3 \dots x_k}$

Equality holds if and only if $x_1 = x_2 = x_3 = \dots = x_k$. This inequality tells us that for fixed sum (in this case, N), the product is maximized when the terms are equal. So, we need to split N into equal parts to get the maximum product.

However, we have some flexibility in the number of equal parts (k), and selecting the right k is key to solving this problem.

Observe that $r^k$ is maximized where its derivative is zero, i.e., when $\frac{d(r^k)}{dr}=0$. The derivative is $kr^{k-1} – Nk^{k-2}$, and setting that equal to 0 and solving gives $r=\frac{k}{k-1}$. The integer part of $r$ is thus $\left\lfloor\frac{k}{k-1}\right\rfloor$.

So, if $\left\lfloor\frac{k}{k-1}\right\rfloor \leq N < \left\lfloor\frac{k+1}{k}\right\rfloor$, $r^k$ is maximized when k parts are equal (when possible) and one part is 1 unit larger. Also, note that if k is a power of 2, $r=N/k$ is a power of 2, meaning $P$ is a non-terminating decimal when divided by $k^k$. For all other k, $P$ is a terminating decimal. To implement this, we can loop over all values of N (5 to 10000) and for each N, determine the best k by checking the inequalities sequentially starting from k=2, until we find $N < \left\lfloor\frac{k+1}{k}\right\rfloor$. Then, if k is a power of 2, N is added; otherwise, N is subtracted. Sum up all these contributions and that's your answer. To code this efficiently in a language like Python for example, it would be useful to preprocess a lookup table to quickly find whether a number is a power of 2 (true only for 1,2,4,8, etc.), like so: ``` powerOf2 = [False]*(10000+1) power = 1 while(power <= 10000): powerOf2[power] = True power*=2 ``` You can then run your sum-loop calculation using this lookup table. This solution runs efficiently as both loops are O(1), fast enough for N up to 10000 or beyond.

More Answers: