## Three-Way Minimum Sum Partitions

### November 22, 2019

I had a lot of fun working on this problem:

Given n, find x, y and z such that x y z = n and x + y + z is minimal; for instance, given n = 1890, the correct answer is (9 14 15).

Your task is to write a program to find x, y and z. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 12 Responses to “Three-Way Minimum Sum Partitions”

1. Paul said

The method below is much faster than brute force. First determine all divisors and sort them in decreaing order. Loop for x starting from the cubic root downwards. Divide n by x, determine the sqrt of the result and check if it possible to improve the sum. Break if not possible. Otherwise loop downwards from this sqrt and find the first possible solution.
I will post full code later on ideone.

```def threeway3(n):
divs = sorted(divisors(n), reverse=True)
n3 = iroot(3, n)
min_val, min_sol = inf, None
for x in divs:
if x > n3:
continue
m = n // x
sqrtm = isqrt(m)
if x + 2 * sqrtm > min_val:
break
for y in divs:
if y < x:
break
if y > sqrtm:
continue
if m % y == 0:
z = m // y
if x + y + z < min_val:
min_val = x + y + z
min_sol = (x, y, z)
break
return min_sol, min_val
```
2. Paul said

Full code with some changes is on Ideone.

3. matthew said

@Paul: nice – I was thinking on similar lines, but didn’t think of the cutoff on line 10. I think that break on line 22 can be outdented (any smaller divisor than y will have a larger sum). It would be nice to do a binary search through the divisors to find the start points of the iterations.

4. Paul said

@matthew. I saw also that I could outdent that line (see my Ideone post)

5. matthew said

@Paul: So I see, good stuff. I’m wondering if we can remove cubic factors from n before finding the minimum sum, ie. if a+b+c = n is minimal, then is it the case that ka+kb+kc = k^3n is minimal?

6. Paul said

@matthew. An interesting idea, but unfortunately there is a counterexample. Take 24=83. The best solution is x,y,z = 2, 3, 4 with sum 9. If you solve for n=3 with solution 1,1,3 (sum 5) the total sum is 25=10.

7. Paul said

@matthew. Formatting caught me here, Of course, I meant 24=8×3 and 2×5=10.

8. matthew said

@Paul: nice counterexample. Probably wouldn’t have helped much in the general case anyway.

9. Daniel said

Here’s a recursive solution in Python that supports an arbitrary number of factors, as opposed to 3 specified in the problem.

```def prime_factorize(n):
assert n >= 2
factors = []
x = 2
while x * x <= n:
if n % x == 0:
factors.append(x)
n //= x
continue
x += 1 + (x & 1)
factors.append(n)
return tuple(factors)

def calc_divisors(n):
divisors = {1}
for factor in prime_factorize(n):
divisors.update([factor * d for d in divisors])
return tuple(divisors)

def min_sum_factorize(n, num_factors):
if num_factors == 1:
return n,
best = (n,) + (1,) * (num_factors - 1)
best_sum = sum(best)
for x in calc_divisors(n):
if pow(x, num_factors) > n:
continue
if n % x == 0:
rest = min_sum_factorize(n // x, num_factors - 1)
total = sum(rest) + x
if total < best_sum:
best = (x,) + rest
best_sum = total
return best

print(min_sum_factorize(2490, 3))
print(min_sum_factorize(1890, 3))
print(min_sum_factorize(33731641944000, 3))

print(min_sum_factorize(2490, 4))
print(min_sum_factorize(1890, 4))
print(min_sum_factorize(33731641944000, 4))
```

Output:

```(5, 6, 83)
(9, 14, 15)
(32292, 32300, 32340)
(2, 3, 5, 83)
(5, 6, 7, 9)
(2394, 2400, 2415, 2431)
```
10. Daniel said

Here’s the recursive solution I posted above, with @Paul’s short-circuiting optimization. It runs noticeably faster now :-), even with the naive integer root function I wrote.

```def iroot(n, k):
"""A naive algorithm for calculating the degree k integer root of n"""
x = 1
while pow(x, k) < n:
x *= 2
while pow(x, k) > n:
x -= 1
return x

def prime_factorize(n):
assert n >= 2
factors = []
x = 2
while x * x <= n:
if n % x == 0:
factors.append(x)
n //= x
continue
x += 1 + (x & 1)
factors.append(n)
return tuple(factors)

def calc_divisors(n):
divisors = {1}
for factor in prime_factorize(n):
divisors.update([factor * d for d in divisors])
return tuple(divisors)

def min_sum_factorize(n, num_factors):
num_factors_minus_one = num_factors - 1
if num_factors == 1:
return n,
best = (n,) + (1,) * num_factors_minus_one
best_sum = sum(best)
for x in sorted(calc_divisors(n), reverse=True):
if pow(x, num_factors) > n:
continue
if x + num_factors_minus_one * iroot(n // x, num_factors_minus_one) > best_sum:
break
if n % x == 0:
rest = min_sum_factorize(n // x, num_factors_minus_one)
total = sum(rest) + x
if total < best_sum:
best = (x,) + rest
best_sum = total
return best

for n in (2490, 1890, 33731641944000):
for num_factors in (3, 4, 5):
result = min_sum_factorize(n, num_factors)
print(f'min_sum_factorize({n}, {num_factors}) = {result}')
```

Output:

```min_sum_factorize(2490, 3) = (6, 5, 83)
min_sum_factorize(2490, 4) = (5, 3, 2, 83)
min_sum_factorize(2490, 5) = (3, 5, 2, 83, 1)
min_sum_factorize(1890, 3) = (9, 14, 15)
min_sum_factorize(1890, 4) = (6, 5, 7, 9)
min_sum_factorize(1890, 5) = (3, 5, 3, 6, 7)
min_sum_factorize(33731641944000, 3) = (32300, 32292, 32340)
min_sum_factorize(33731641944000, 4) = (2400, 2394, 2415, 2431)
min_sum_factorize(33731641944000, 5) = (506, 504, 494, 510, 525)
```
11. Steve said

Klong solution

In addition to the brute force approach, I tried the following 2 alternatives:
1) Iterated the first loop from 1 to the floored cube root of the initial number; and
2) Iterated the first loop from 1 to the floored cube root of the initial number and iterated the 2nd loop from 1 to the floored square root of the quotient of the initial number and the 1st iterator.

The run shows one of the combinations which yields one of the least sums as well as the number of combinations before finding the minimum.

```
go::{[l]; l::l@<{+/x}'l::{x}'go1(x); (#l),,*l}

go1::{[l n q]; l::[]; n::x;n{:[q=_q::n%x; l::go2(l; x; _q);""]; x+1}:*1; l}

go2::{[l2 y2 n2 q2]; l2::x; y2::y; n2::z; n2{:[q2=_q2::n2%x; l2::l2,,y2,x,_q2; 1]; x+1}:*1; l2}

go3::{[l]; l::l@<{+/x}'l::{x}'go4(x); (#l),,*l}

go4::{[l n q]; l::[]; n::x; (_n^1%3){:[q=_q::n%x; l::go5(l; x; _q);""]; x+1}:*1; l}

go5::{[l2 y2 n2 q2]; l2::x; y2::y; n2::z; n2{:[q2=_q2::n2%x; l2::l2,,y2,x,_q2; 1];x+1}:*1; l2}

go6::{[l]; l::l@<{+/x}'l::{x}'go7(x); (#l),,*l}

go7::{[l n q]; l::[]; n::x; (_n^1%3){:[q=_q::n%x; l::go8(l; x; _q);""]; x+1}:*1; l}

go8::{[l2 y2 n2 q2]; l2::x; y2::y; n2::z; (_n2^1%2){:[q2=_q2::n2%x; l2::l2,,y2,x,_q2; 1]; x+1}:*1; l2}

n::#l::go(1890); .p("Brute force:       Answer - [",(l@1),"], # Entries - ",,(l@0)); .p("")

n::#l::go3(1890); .p("Square root:       Answer - [",(l@1),"], # Entries - ",,l@0); .p("")

n::#l::go6(1890); .p("Cube/Square roots: Answer - [",(l@1),"], # Entries - ",,l@0); .p("")

```
12. Steve said

Results from the Klong run:

[Brute force: Answer – [ 9 14 15 ], # Entries – 270]

[Square root: Answer – [ 9 15 14 ], # Entries – 140]

[Cube/Square roots: Answer – [ 9 14 15 ], # Entries – 70]