Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.num-analysis.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
G. Ralph Kuntz, MD

Posts: 4
Registered: 12/13/04
Q: "Rectangularizing" a number
Posted: Oct 14, 1999 8:57 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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





Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.