3
$\begingroup$

Is there a way to find how to arrange $n$ tiles in order to form a rectangle that is closest to a square? As I result I am looking for the dimension of that rectangle if it exists.

For example, here are the results I expect from $1$ to $9$.

  1. a 1 by 1 square, fairly simple.
  2. a 1 by 2 rectangle.
  3. a 1 by 3 rectangle.
  4. a 2 by 2 square.
  5. this is impossible because a 1 by 5 rectangle is thinner than the previous shape.
  6. a 2 by 3 rectangle.
  7. this is impossible.
  8. a 2 by 4 rectangle.
  9. a 3 by 3 square.

I am only looking at $n$ smaller than $100$ but would rather not have to hardcode everything.

$\endgroup$
5
$\begingroup$

Although your problem statement doesn't explicitly state it, your examples indicate that you want the value of the lower of the $2$ factors to never decrease. Thus, each increase of the lower factor among your examples occurs at a square, such as $1$ being $1 \text{ by } 1$, $4$ being $2 \text{ by } 2$ and $9$ being $3 \text{ by } 3$.

If this is a correct assumption on my part, and there are no other unstated conditions, then each next value which is not "impossible" would be the integers which are multiples of the current "low" factor until you encounter the square of the next higher integer. Thus, continuing from what you have written, the next valid values would be $12 = 3 \times 4$ and $15 = 3 \times 5$ for a lower value of $3$ before you hit the next square at $16 = 4 \times 4$. From there, the next values would be $20 = 4 \times 5$ and $24 = 4 \times 6$ before you encounter $25 = 5 \times 5$. You can then continue like this until you reach $100$ or most any other limit you care to set.

To check for any specific value representing a valid rectangle, including what its shape would be, or if it's impossible, you need to determine what the largest perfect square is less or than or equal to your number. This can be done by using the integer part of the square root. For example, the square root of $143$ is $11.9\ldots$ so the factor to check is $11$. As $143 = 11 \times 13$, it is a valid rectangle. However, $142$ down to $133$ will not work, with $132 = 11 \times 12$ being the next smaller value which would work.

As previously written by Ross Millikan in the comments below, stated more succinctly using mathematical terminology, for any positive integer $n$, determine $k = \lfloor \sqrt{n} \rfloor$. If $k$ divides $n$, then the rectangle is $k \times \frac{n}{k}$, else it's impossible.

$\endgroup$
  • $\begingroup$ No, you're completely right. However, how could, given n of let's say 94, I know what's the shape without calculating every number by hand? $\endgroup$ – Alex Laquerre Dec 31 '18 at 3:05
  • 2
    $\begingroup$ Just determine the smallest perfect square less than or equal to the value. For $94$, that is $81 = 9 \times 9$. Next, check if $9$ is a factor of $94$. It isn't in this case, so $94$ would be considered "impossible" by your algorithm. I hope this makes sense. $\endgroup$ – John Omielan Dec 31 '18 at 3:09
  • 1
    $\begingroup$ What I gather from John's answer is that, given $n$, you find $d$, the integer part of the square root of $n$, and then you check whether $d$ divides $n$. If it does, then $d$ by $n/d$ is what you want. If it doesn't, then that $n$ doesn't work. $\endgroup$ – Gerry Myerson Dec 31 '18 at 3:10
  • 1
    $\begingroup$ Stated as an algorithm, given $n$ compute $k=\lfloor \sqrt n \rfloor$. If $k$ divides $n$ the rectangle is $k \times \frac nk$. If $k$ does not divide $n$ it is impossible. Good answer. $\endgroup$ – Ross Millikan Dec 31 '18 at 3:33
  • 1
    $\begingroup$ You are welcome to edit it into your answer, which will make it more accessible to readers. $\endgroup$ – Ross Millikan Dec 31 '18 at 3:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.