A mathematical constant hiding in plainsight.
The optimal solution should strike a perfect balance between the length k of the integer partition and the size of each component we are pulling out. \n\nFor ex
The optimal solution should strike a perfect balance between the length `k` of the integer partition and the size of each component we are pulling out. \n\nFor example consider the possibilities when `n = 17`:\n```\n17 = 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 1 (2 ^ 8 * 1)\n17 = 3 + 3 + 3 + 3 + 3 + 2 (3 ^ 5 * 2)\n17 = 4 + 4 + 4 + 4 + 1 (4 ^ 4 * 1)\n17 = 5 + 5 + 5 + 2 (5 ^ 3 * 2)\n...\n```\n\nThe bigger the number `m` we pull out of `n` to partition it the less times we can do it, meaning a lower exponent `m` is raised to when we do the multiplication at the end. However, the smaller `m` is, the more of it that we can partition out of `n` leading to a bigger exponent, but at the expense of the base it is being raised to.\n\nSo we must ask ourselves, what is the optimal number `x` that we can equally partition `n` into while also achieving the greatest exponential expression. Essentially what we are asking is: Find `x` such that `x ^ (n / x)` is maximized.\n\nThis `x` just so happens to be `e` therefore the answer to this question: `integerBreak(n)` for large `n` should be approximately `e^(n/e)`.\n\n\nLet\'s look at some numerical examples to make sure:\n\n**NOTE:** It is better to show how good the approximation is using the inverse relation (`n ~ e * ln(integerBreak(n))`) rather than `integerBreak(n) ~ e^(n/e)` because of how sensitive exponential functions are to their input.\n\n```\nn   integerBreak(n)     n ~ e * ln(integerBreak(n))\n--  ---------------     ---------------------------\n10  36                  9.7410\n15  243                 14.9316        \n20  1458                19.8021\n25  8748                24.6727\n30  59049               29.8634\n35  354294              34.7339\n40  2125764             39.6044\n45  14348907            44.7951\n50  86093442            49.6656\n55  516560652           54.5360\n```\n\nAs you can see `integerBreak(n) ~ e^(n/e)` is a very good approximation. \n\nGiven that this optimization problem is constrained to the integers, partitioning `n` with `e` is not possible. Therefore, we must optimize `x^(n/x)` with the restriction that `x` is an integer. Therefore `x` must either be `2` or `3` since we know the maximum occurs in between at `x = e` \n\nComputing the two possibilities:\n\n```\n2^(1/2) = 1.414213562\n3^(1/3) = 1.44224957\n```\n\nWe see that `x = 3` is larger and therefore pulling out as many `3`s as possible from `n` will strike the perfect balance between the length of the sum `k` and the base of the exponent we are using to compute the maximum product for the integers which make up the partition of `n`\n\nTherefore in cases where `n > 4` we should always decompose `n` in the following way:\n\n```\nn = 3 * q + r\n```\n\nWhen `3` perfectly divides `n` or in other words: `r = 0` : `integerBreak(n) = 3 ^ (n / 3)`\n\nWhen `3` does not perfectly divide `n` and has a remainder of `1` or in other words: `r = 1`:\n\nWe do the following manipulation:\n\n```\nn = 3 * q + 1\nn = 3 * (q - 1 + 1) + 1\nn = 3 * (q - 1) + 3 * 1 + 1\nn = 3 * (q - 1) + 4\n```\n\nTherefore, we break `n` into `(q - 1)` partitions of `3` followed by a `4` leading to: `4 * 3 ^ (n / 3 - 1)` as the answer.\n\nFactoring out the subtraction in the exponent we get:\n```\nintegerBreak(n) = (4 / 3) * 3 ^ (n / 3) \n```\n\nThis is always going to be bigger than what we would have if we didn\'t do any manipulation which have been:\n`1 * 3 ^ (n / 3)` because `4/3 > 1`. In code, I leave the subtraction inside the exponent, so that the final multiplication is between two integers rather than two floats as integer multiplication is much faster than floating point. For the sake of proof, however, I use the expression above since it shows how the manipulation leads to a product that is `33.333%` bigger than what you would have gotten without it.\n\nFinally, when `3` does not perfectly divide `n` and has a remainder of `2` or in other words: `r = 2`:\n\nWe fit `n` to the following form.\n```\nn = 3 * q + 2\n```\n\nIf we did the same manipulation steps as above we can end up with `n = 3*(q - 1) + 5` which would lead to an answer:\n\n`(5/3) * 3 ^ (n / 3)` however not doing the manipulation would give us `2 * 3 ^ (n / 3)` which is always bigger simply because `2 > 5/3`. \n\nTherefore in the `r = 2` case:\n\n```\nintegerBreak(n) = 2 * 3 ^ (n / 3)\n```\n\nAs code:\n\n```\n    def integerBreak(self, n):\n        """\n        :type n: int\n        :rtype: int\n        """\n        if n == 2:\n            return 1\n        if n == 3:\n            return 2\n        if n == 4:\n            return 4\n        \n        if n % 3 == 0:\n            return int(pow(3, n // 3))\n        if n % 3 == 1:\n            return int(pow(3, n // 3 - 1)) * 4\n        if n % 3 == 2:\n            return int(pow(3, n // 3)) * 2\n```
[]