Factoring a number into roughly equal factors

Question

I would like to decompose a number into a tuple of numbers as close to each other in size as possible, whose product is the initial number. The inputs are the number n we want to factor and the number m of factors desired.

For the two factor situation (m==2), it is enough to look for the largest factor less than a square root, so I can do something like this

def get_factors(n):
  i = int(n**0.5 + 0.5)
  while n % i != 0:
    i -= 1
  return i, n/i

So calling this with 120 will result in 10,12.

I realize there is some ambiguity as to what it means for the numbers to be "close to each other in size". I don't mind if this is interpretted as minimizing Σ(x_i - x_avg) or Σ(x_i - x_avg)^2 or something else generally along those lines.

For the m==3 case, I would expect that 336 to produce 6,7,8 and 729 to produce 9,9,9.

Ideally, I would like a solution for general m, but if someone has an idea even for m==3 it would be much appreciated. I welcome general heuristics too.

EDIT: I would prefer to minimize the sum of the factors. Still interested in the above, but if someone has an idea for a way of also figuring out the optimal m value such that the sum of factors is minimal, it'd be great!

Answer 1

To answer your second question (which m minimizes the sum of factors), it will always be optimal to split number into its prime factors. Indeed, for any positive composite number except 4 sum of its prime factors is less that the number itself, so any split that has composite numbers can be improved by splitting that composite numbers into its prime factors.

To answer your first question, greedy approaches suggested by others will not work, as I pointed out in the comments 4104 breaks them, greedy will immediately extract 8 as the first factor, and then will be forced to split the remaining number into [3, 9, 19], failing to find a better solution [6, 6, 6, 19]. However, a simple DP can find the best solution. The state of the DP is the number we are trying to factor, and how many factors do we want to get, the value of the DP is the best sum possible. Something along the lines of the code below. It can be optimized by doing factorization smarter.

n = int(raw_input())
left = int(raw_input())


memo = {}
def dp(n, left): # returns tuple (cost, [factors])
    if (n, left) in memo: return memo[(n, left)]

    if left == 1:
        return (n, [n])

    i = 2
    best = n
    bestTuple = [n]
    while i * i <= n:
        if n % i == 0:
            rem = dp(n / i, left - 1)
            if rem[0] + i < best:
                best = rem[0] + i
                bestTuple = [i] + rem[1]
        i += 1

    memo[(n, left)] = (best, bestTuple)
    return memo[(n, left)]


print dp(n, left)[1]

For example

[In] 4104
[In] 4 
[Out] [6, 6, 6, 19]