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