Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Q: "Rectangularizing" a number
Replies: 8   Last Post: Mar 27, 2012 10:35 PM

 Messages: [ Previous | Next ]
 G. Ralph Kuntz, MD Posts: 4 Registered: 12/13/04
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 zero-based)
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 Vice-President and Chief Scientist
Hamilton Scientific, Ltd.
www.hamilsci.com
+1 973 377 7300

Date Subject Author
10/14/99 G. Ralph Kuntz, MD
10/14/99 Simon Langley
10/14/99 G. Ralph Kuntz, MD
3/27/12 Glenn Thorpe
10/14/99 Charles Crawford
10/15/99 Dave Rusin
10/14/99 P.G.Hamer
10/14/99 Virgil Hancher
10/15/99 G. Ralph Kuntz, MD