CODEWITHSUNDEEP
pythonalgorithmmath
Alec
Alec

Reputation: 32309

Factoring a number into roughly equal factors

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!

Upvotes: 10

Views: 2997

Answers (4)

user12540503
user12540503

Reputation: 1

m=5 n=4 then m^(1/n)

you get:

Answer=1.495

then

1.495*1.495*1.495*1.495 = 5

in C# 

double Result = Math.Pow(m,1/(double)n);

Upvotes: -2

Ishamael
Ishamael

Reputation: 12795

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]

Upvotes: 5

whiterook6
whiterook6

Reputation: 3534

How about this, for m=3 and some n:

  1. Get the largest factor of n smaller than the cube root of n, call it f1
  2. Divide n by f1, call it g
  3. Find the "roughly equal factors" of g as in the m=2 example.

For 336, the largest factor smaller than the cube root of 336 is 6 (I think). Dividing 336 by 6 gives 56 (another factor, go figure!) Performing the same math for 56 and looking for two factors, we get 7 and 8.

Note that doesn't work for any number with fewer than 3 factors. This method can be expanded for m > 3, maybe.

If this is right, and I'm not too crazy, the solution would be a recursive function:

factors=[]
n=336
m=3

def getFactors(howMany, value):
  if howMany < 2:
    return value

  root=getRoot(howMany, value) # get the root of value, eg square root, cube, etc.
  factor=getLargestFactor(value, root) # get the largest factor of value smaller than root
  otherFactors=getFactors(howMany-1, value / factor)
  otherFactors.insert(factor)
  return otherFactors
print getFactors(n, m)

I'm too lazy to code the rest, but that should do it.

Upvotes: 1

Daniel Robinson
Daniel Robinson

Reputation: 3387

You can start with the same principle: look for numbers under or equal to the mth root that are factors. Then you can recurse to find the remaining factors.

def get_factors(n, m):
    factors = []
    factor = int(n**(1.0/m) + .1) # fudged to deal with precision problem with float roots
    while n % factor != 0:
        factor = factor - 1
    factors.append(factor)
    if m > 1:
        factors = factors + get_factors(n / factor, m - 1)
    return factors

print get_factors(729, 3)

Upvotes: 1

Related Questions