Deceptively Simple? Given an integer, find the SET of CLOSEST integers which exactly divide it?

Question

Given a positive integer number of objects, say little boxes, I'd like to lay them out neatly on a table in a nice 2d block which may or may not form a rectangle, but not any old rectangle, one which is as close to a square as possible. To do this, I need the TWO integers, which divide the integer number of objects, which are as close to each other as possible.

For instance;

Say I have 12 objects. I could lay them out as

(12 x 1) or (1 x 12) or (6 x 2) or (2 x 6) or (3 x 4) or (4 x 3)

I want them as (4 x 3), or even (3 x 4) but assume the largest value comes first, as this is the largest pair which divide the number which are the closest.

Given some positive integer, x, what algorithm would return (y , z) where;

((y * z) = x) AND (y > z) AND (abs(y - z) is a minimum)

When there's NO SOLUTION, I could search for a solution by increasing the integer number, starting from the number of objects I actually have, to find a nearby solution, then fit my objects into that solution, leaving gaps.

BUT... now let's pick up the pace!

What if I extend this now into 3d, instead of on a flat plane, and I want to make a nice neat block of these, assume cubic, objects in 3d space that has the CLOSEST THREE numbers which divide the integer number of objects which are as close to each other as possible, so as to form the most compact, closely-packed 3d structure possible from that number of objects? For instance;

Say I have 12 objects. I could arrange them as

(12 x 1 x 1) or (1 x 12 x 1) or (1 x 1 x 12) or (2 x 2 x 3) or (2 x 3 x 2) or (3 x 2 x 2)...

Where I accept them as a compact (3 x 2 x 2) block of objects.

Not being a mathematician, firstly, what is this kind of factor problem called and, secondly, is there an algorithm that can do this for any positive integer and suggest when no solution is possible.

I know it starts with factoring the integer number but then...

BONUS POINTS... Might there also be a way to do 4 dimensional solutions? N dimensional?

I'm trying to write a C++ algorithm, but this is an integer math problem I hit.

Thank-you.

Answer 1

You want to factor an integer n into k factors, minimizing the total Euclidean distance among all k_i. There is always a solution to this, provided that 0 < k and 0 < n. For example, consider n = any prime number: the solution is {n} + {1 repeated k - 1 times}.

A recursive pseudocode approach:

list<int> reduce(int n, int k, list<int> factors)
  // validity checks for 0 < k, 0 < n omitted
  // if there's only one factor left, we know what it is
  if(k == 1) 
    factors.add(n)
    return factors
  // we know all the remaining factors because n can't be reduced further
  if(n is prime || n == 1)
    factors.add(n)
    return reduce(1, k - 1, factors)
  // take the k-th root of n, rounded up
  int r = ceiling(root(n, k))
  // if there's an exact root here, we're done; remaining factor distance = 0
  if(n % r == 0)
    do k times
      factors.add(r)
    return factors
  // otherwise find the next largest remaining factor
  while(n % r != 0)
    r -= 1
  factors.add(r)
  return reduce(n / r, k - 1, factors)

This code is intended to be clear rather than optimized.

Conceptually, you're trying to minimize the diagonal measurement formed by extending all k factors out from a point at right angles. If k = 2, you're minimizing the hypotenuse of the right triangle formed by placing k₀ at a right angle to k₁. For k = 3, it's minimizing the area of the triangle formed by making all three factors orthogonal (i.e. forming the X-Y-Z axes of a three dimensional Cartesian graph). For k = 4, it's minimizing the volume of the tetrahedral solid; etc. To build this shape iteratively, the algorithm above uses the k-th root to bound the size of the new dimension to add.

If you want the results sorted, well, just sort the returned list. Presumably n >> k, so the k log k cost of the sort is trivial compared to the cost of factorization. Or I suppose you could use a self-sorting data structure as the return type if you're lazy.

Some examples worked:

n = 12, k = 3

• r = 3 (cube root of 12 rounded up)
• 12 % 3 == 0; 3 is a factor
• recurse; n = 4, k = 2
• r = 2 (square root of 4)
• 4 % 2 == 0; add 2 to the factors 2 times
• result: {3, 2, 2}

n = 32, k = 3

• r = 4 (cube root of 32 rounded up)
• 32 % 4 == 0; 4 is a factor
• recurse; n = 8, k = 2
• r = 3 (square root of 8 rounded up)
• 8 % 3 != 0; r = 2
• 8 % 2 == 0; 2 is a factor
• recurse; n = 2, k = 1
• k == 1; 2 is a factor
• result: {4, 2, 2}

n = 25, k = 4

• r = 2 (quad root of 25 rounded up)
• 25 % 2 != 0; r = 1
• 25 % 1 == 0; 1 is a factor
• recurse; n = 25, k = 3
• r = 3 (cube root of 25 rounded up)
• 25 % 3 != 0; r = 2
• 25 % 2 != 0; r = 1
• 25 % 1 == 0; 1 is a factor
• recurse; n = 25, k = 2
• r = 5 (square root of 25)
• 25 % 5 == 0; add 5 to the factors 2 times
• result: {1, 1, 5, 5}

More results:

• n = 88, k = 3 -> {4, 2, 11}
• n = 66, k = 5 -> {2, 1, 3, 11, 1}
• n = 14, k = 3 -> {2, 7, 1}
• n = 15, k = 3 -> {3, 5, 1}
• n = 18, k = 2 -> {3, 6}
• n = 39, k = 3 -> {3, 13, 1}
• n = 49, k = 3 -> {1, 7, 7}