Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



Q: "Rectangularizing" a number
Posted:
Oct 14, 1999 8:57 AM


Please excuse my ignorance, but this problem may be obvious...
I woke up this morning thinking about an interesting math problem :). Given a number N, find the two integer factors of N that when multiplied give N and when added, give the smallest number. In other words, if these two factors (A and B) were arranged as a rectangle with A dots along the length, and B dots along the height, the rectangle formed would have the smallest perimeter (it would be as close to a square as possible).
For example, if N = 120, A = 15 and B = 8 produces a 15 by 8 rectangle with perimeter = 15 * 2 + 8 * 2 = 46, but if A = 10 and B = 12, the perimeter = 10 * 2 + 12 * 2 = 44. This combination (10, 12) is the "squarest" for the number 120.
The algorithm I came up with seems to always produce the optimum solution, but I can't prove it. Here it is in pseudoJava:
/* Note that the characters "//" start a comment */
N = // starting number int primes[] = // array of prime factors of N sorted in ascending order double root = sqrt(N); // square root of N int left = 1; int right = 1; // Iterator down from the largest prime factor to the smallest // (arrays in pseudoJava are zerobased) for (int p = primes.size()  1; p >= 0; p) { int pr = primes[p]; // get the next prime if (left * pr <= root) left = left * pr; else right = right * pr; } print(left, right);
Does this algorithm give the best values for A and B?
Thanks, Ralph
 G. Ralph Kuntz, MD, MS (Computer Science) Executive VicePresident and Chief Scientist Hamilton Scientific, Ltd. www.hamilsci.com +1 973 377 7300



