From a given number, determine three close numbers whose product is the original number

Question

I have a number n, and I want to find three numbers whose product is n but are as close to each other as possible. That is, if n = 12 then I'd like to get 3, 2, 2 as a result, as opposed to 6, 1, 2.

Another way to think of it is that if n is the volume of a cuboid then I want to find the lengths of the sides so as to make the cuboid as much like a cube as possible (that is, the lengths as similar as possible). These numbers must be integers.

I know there is unlikely to be a perfect solution to this, and I'm happy to use something which gives a good answer most of the time, but I just can't think where to go with coming up with this algorithm. Any ideas?

Answer 1

Here's my first algorithm sketch, granted that n is relatively small:

• Compute the prime factors of n.
• Pick out the three largest and assign them to f1, f2, f3. If there are less than three factors, assign 1.
• Loop over remaining factors in decreasing order, multiply them into the currently smallest partition.

---

Edit

Let's take n=60.

Its prime factors are 5 3 2 2.

Set f1=5, f2=3 and f3=2.

The remaining 2 is multiplied to f3, because it is the smallest.

We end up with 5 * 4 * 3 = 60.

---

Edit

This algorithm will not find optimum, notice btillys comment:

Consider 17550 = 2 * 3 * 3 * 3 * 5 * 5 * 13. Your algorithm would give 15, 30, 39 when the best is 25, 26, 27.

---

Edit

Ok, here's my second algorithm sketch with a slightly better heuristic:

• Set the list L to the prime factors of n.
• Set r to the cube root of n.
• Create the set of three factors F, initially set to 1.
• Iterate over the prime factors in descending order:
  • Try to multiply the current factor L[i] with each of the factors in descending order.
    • If the result is less than r, perform the multiplication and move on to the next prime factor.
    • If not, try the next F. If out of Fs, multiply with the smallest one.

This will work for the case of 17550:

n=17550
L=13,5,5,3,3,3,2
r=25.98

F = { 1, 1, 1 }

Iteration 1:

• F[0] * 13 is less than r, set F to {13,1,1}.

Iteration 2:

• F[0] * 5 = 65 is greated than r.
• F[1] * 5 = 5 is less than r, set F to {13,5,1}.

Iteration 3:

• F[0] * 5 = 65 is greated than r.
• F[1] * 5 = 25 is less than r, set F to {13,25,1}.

Iteration 4:

• F[0] * 3 = 39 is greated than r.
• F[1] * 3 = 75 is greated than r.
• F[2] * 3 = 3 is less than r, set F to {13,25,3}.

Iteration 5:

• F[0] * 3 = 39 is greated than r.
• F[1] * 3 = 75 is greated than r.
• F[2] * 3 = 9 is less than r, set F to {13,25,9}.

Iteration 6:

• F[0] * 3 = 39 is greated than r.
• F[1] * 3 = 75 is greated than r.
• F[2] * 3 = 27 is greater than r, but it is the smallest F we can get. Set F to {13,25,27}.

Iteration 7:

• F[0] * 2 = 26 is greated than r, but it is the smallest F we can get. Set F to {26,25,27}.

Answer 2

Here's a purely math based approach, that returns the optimal solution and does not involve any kind of sorting. Hell, it doesn't even need the prime factors.

Background:

1) Recall that for a polynomial

the sum and product of the roots are given by

where x_i are the roots.

2) Recall another elementary result from optimization theory:

i.e., given two variables such that their product is a constant, the sum is minimum when the two variables are equal to each other. The tilde variables denote the optimal values.

A corollary of this would be that if the sum of two variables whose product is constant, is a minimum, then the two variables are equal to each other.

Reformulate the original problem:

Your question above can now be reformulated as a polynomial root-finding exercise. We'll construct a polynomial that satisfies your conditions, and the roots of that polynomial will be your answer. If you need k numbers that are optimal, you'll have a polynomial of degree k. In this case, we can talk in terms of a cubic equation

We know that:

1. c is the negative of the input number (assume positive)
2. a is an integer and negative (since factors are all positive)
3. b is an integer (which is the sum of the roots taken two at a time) and is positive.
4. Roots of p must be real (and positive, but that has already been addressed).

To solve the problem, we simply need to maximize a subject to the above set of conditions. The only part not explicitly known right now, is condition 4, which we can easily enforce using the discriminant of the polynomial.

For a cubic polynomial p, the discriminant is

and p has real and distinct roots if ∆>0 and real and coincident (either two or all three) if ∆=0. So, constraint 4 now reads ∆>=0. This is now simple and easy to program.

Solution in Mathematica

Here's a solution in Mathematica that implements this.

And here's a test on some of the numbers used in other answers/comments.

The column on the left is the list and the corresponding row in the column on the right gives the optimal solution.

NOTE:

I just noticed that OP never mentioned that the 3 numbers needed to be integers although everyone (including myself until now) assumed that they were (probably because of his first example). Re-reading the question, and going by the cube example, it doesn't seem like OP was fixated on integers.

This is an important point which will decide which class of algorithms to pursue and needs to be defined. If they need not be integers, there are several polynomial based solutions that can be provided, one of which is mine (after relaxing the integer constraint). If they should be integers, then perhaps an approach using branch-n-bound/branch-n-cut/cutting plane might be more appropriate.

The following was written assuming the OP meant the three numbers to be integers.

The way I've implemented it right now, it can give a non-integer solution in certain cases.

The reason this gives non-integer solutions for x is because I had only maximized a, when actually, b also needs to be minimum (not only that, but also because I haven't placed a constraint on the x_i being integers. It is possible to use the integer root theorem, which would involve finding the prime factors, but makes things more complicated.)

Mathematica code in text

Clear[poly, disc, f]
poly = x^3 + a x^2 + b x + c;
disc = Discriminant[poly, x];
f[n_Integer] := 
 Module[{p, \[CapitalDelta] = disc /. c -> -n}, 
  p = poly /. 
     Maximize[{a, \[CapitalDelta] >= 0, 
        b > 0 && a < 0 && {a, b} \[Element] Integers}, {a, b}][[
      2]] /. c -> -n;
  Solve[p == 0]
  ]