# A Clear Math Proof of the Algorithm

• It is well-known that the algorithm should return the result by breaking n into factors 2 or 3, and also many other authors have been revealed the reasons for that. However, there are still some ambiguous questions about their explanations. For example, why does n have to break down as n=x+x+...+x ?, and why choosing 3 as factors is better than 2?

Hence, here I want to share a more strict proof of the correctness of the algorithm.

/**
* Given n, let m be the number of summands so that a1+a2+...+am =
* n. By the Inequality of Arithmetic and Geometric Means, we have:
*
* a1 * a2 * ... * am <= (n/m)^m (i.e., power(n/m, m)) and that
* equality holds iff (if and only if) a1=a2=...=am.
*
* Now let x=n/m, and consider the function f(x)=x^(n/x), we are
* going to find its max. Let y=ln[f(x)]=(n/x) * ln(x). Then:
*
* y' = -(n/x^2) * ln(x) + (n/x) * (1/x) = (n/x^2) * [ln(e)-ln(x)],
*
* where e=exp(1)=2.71828... . Since ln() is an increasing function,
* so
*
* f(x) is increasing iff y is increasing iff y'>0 iff
* [ln(e)-ln(x)]>0 iff x<e; and is decreasing iff x>e; and is
* maximized when x=e.
*
* Since x is an integer, x=2 or 3 would maximize f(x). Now let's
* check which of f(2), f(3) is bigger.
*
* Since ln[f(x)]=n * ln(x)/x, and ln(2)/2 < ln(3)/3, so f(3) is the
* max.
*
* In order words, f(x) is maximized at 3 among all !integer! x.
* Given the fact that n, m, x are all integers, and the equality
* condition of the Inequality of Arithmetic and Geometric Mean, we
* have the following two results:
*
* 1. Notice that every non-negative integer n can be broken down as
* n = r * 3 + s * 2, for some non-negatives r,s. (This can be proved by
* induction or by the fact that the greatest common divisor of 3
* and 2 is 1.) Thus, x = 2 or 3 is always attainable. Therefore,
* the product P = a1 * a2 * ... * am is maximized only when ai = 2
* or 3, for all i.
*
* 2. If x=3 is attainable, i.e., if n/m=3, i.e., if n%3==0, then
* the product P is maximized when ai = 3, for all i.
*
* Now the only uncertain is the cases n=3k+1 or 3k+2, for some
* positive integer k. Why do they have to break down as 3(k-1)+2 * 2
* and 3k+2 to achieve the max of the product P?
*
* From 1, we have P must be maximized when n is broken down as
* n = r * 3 + s * 2, for some non-negatives r,s. Hence s=(n-3r)/2, so
*
* P(r) = (3^r)(2^s) = (3^r)(2^((n-3r)/2)), and ln(P) =
* rln(3)+[(n-3r)ln(2)]/2.
*
* Let z=ln(P), then z'=ln(3)-3ln(2)/2 > 0. Hence, P(r) is an
* increasing function. And so P is always maximized when r is the
* largest !attainable! non-negative integer. Strictly saying, P is
* maximized when r is the largest non-negative integer, so that
* n = r * 3 + s * 2 with s being also a non-negative integer.
*
* Until now, we are all clear about the reasons why we break down
* the integer n as what it should be for all cases of n=3k, 3k+1
* and 3k+2.
*/

``````public int integerBreak(int n) {
if (n < 3)
return 1;
if (n == 3)
return 2;
if (n % 3 == 0)
return (int) Math.pow(3, n / 3);
if (n % 3 == 1)
return 2 * 2 * ((int) Math.pow(3, (n - 4) / 3));

return 2 * ((int) Math.pow(3, (n - 2) / 3));
}
``````

• @rikimberley thanks for the details.

• This is the most correct answer.
Euler number makes result max. And 3 is only integer that close to the e.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.