A Clear Math Proof of the Algorithm


  • 6
    R

    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));
    		}
    

  • 0
    G

    @rikimberley thanks for the details.


  • 0
    D

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


Log in to reply
 

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