Why factor 2 or 3? The math behind this problem.


  • 172
    L

    I saw many solutions were referring to factors of 2 and 3. But why these two magic numbers? Why other factors do not work?
    Let's study the math behind it.

    For convenience, say n is sufficiently large and can be broken into any smaller real positive numbers. We now try to calculate which real number generates the largest product.
    Assume we break n into (n / x) x's, then the product will be xn/x, and we want to maximize it.

    Taking its derivative gives us n * xn/x-2 * (1 - ln(x)).
    The derivative is positive when 0 < x < e, and equal to 0 when x = e, then becomes negative when x > e,
    which indicates that the product increases as x increases, then reaches its maximum when x = e, then starts dropping.

    This reveals the fact that if n is sufficiently large and we are allowed to break n into real numbers,
    the best idea is to break it into nearly all e's.
    On the other hand, if n is sufficiently large and we can only break n into integers, we should choose integers that are closer to e.
    The only potential candidates are 2 and 3 since 2 < e < 3, but we will generally prefer 3 to 2. Why?

    Of course, one can prove it based on the formula above, but there is a more natural way shown as follows.

    6 = 2 + 2 + 2 = 3 + 3. But 2 * 2 * 2 < 3 * 3.
    Therefore, if there are three 2's in the decomposition, we can replace them by two 3's to gain a larger product.

    All the analysis above assumes n is significantly large. When n is small (say n <= 10), it may contain flaws.
    For instance, when n = 4, we have 2 * 2 > 3 * 1.
    To fix it, we keep breaking n into 3's until n gets smaller than 10, then solve the problem by brute-force.


  • 4
    A

    but I think
    when y = x^(n/x), y' = x^(n/x) * n/x^2 * (1-ln(x))


  • 0
    L
    This post is deleted!

  • 1
    L

    Yes, you are absolutely right. I was doing something idiot... Fixed. :)


  • 0
    L
    This post is deleted!

  • 4
    L

    Say we want to break n into x and y, where x and y are reals and x and y are positive. Then it is easy to see that xy reaches its maximum when x = y.

    Therefore, if we have an uneven partition, making them even always produces larger product.


  • 0
    L

    for 2 positive integers, this is the case, to be exact, make x and y as close as possible to (n * 1.0)/2, basically this is just trying to get max of x* (n - x). However, n, x and y are integers, they are not real numbers. We can not make x and y exactly the same as (n * 1.0)/2 in terms of value. What we can do is just to make x and y as close as possible to (n * 1.0)/2, and then we recursively do this on x and y. How do we guarantee that those side effects do not compound and lead to a wrong result?

    The conclusion might be right, but I am expecting a solid proof.


  • 0
    L

    For integers, we must have only 2's and/or 3's eventually. Note that, any number no less than 4 can be broken into 2's and 3's, and their product must be no less than the original number.

    Formally, 4 = 2 * 2, 5 < 2 * 3. For any number n greater than 5, let us just break it into 2's (and throw away the extra one if n is odd).
    Then, obviously, n < 2n/2 for any n > 5.

    Finally, as shown in my post, there can be at most two 2's, and the rest must be all 3's.


  • 169

    You're making it pretty complicated.

    If an optimal product contains a factor f >= 4, then you can replace it with factors 2 and f-2 without losing optimality, as 2*(f-2) = 2f-4 >= f. So you never need a factor greater than or equal to 4, meaning you only need factors 1, 2 and 3 (and 1 is of course wasteful and you'd only use it for n=2 and n=3, where it's needed).

    For the rest I agree, 3*3 is simply better than 2*2*2, so you'd never use 2 more than twice.


  • 0
    L

    even though n < 2 in power(n/2), how do you prove 2 in power(n/2) is the largest product?


  • 0
    L
    This post is deleted!

  • 0
    This post is deleted!

  • 0

    "any factor f >= 4"

    Edit: But see the added version, maybe that's better.


  • 0
    L

    I didn't mean to prove that. This is just to show the final factors will only contain 2's and/or 3's since we can always break any factor greater than 4 into 2s and 3s without decreasing the product.

    Then, any three 2's can be replaced by two 3's, and we will end up with at most two 2's.


  • 0
    L

    I was sort of confused. If that does not lead us to the largest product, why did we do that or it leads us to the largest product how do we prove that?


  • 0
    L

    Since you are seeking a solid proof, this is the one I give. My argument is that the final decomposition will contain at most two 2's, and the rest must be all 3's.

    I first use the statement above to show the final factors consist of only 2's and 3's. Then, use the fact in my original post to reduce the number of 2's into at most 2.


  • 0
    L

    I like your solution. :D


  • 0
    L
    This post is deleted!

  • 0
    L
    This post is deleted!

  • 0
    L
    This post is deleted!

Log in to reply
 

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