Organizing objects in a near-square pattern
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I don't have any fixed constraints but just a general idea. This probably a well known problem too - yet I can't seem to find any literature on it.
Given n identical 2D objects, what is an algorithm to arrange them on the plane such that they form a near square ? Leaving a hole at the end (e.g. in the case of prime numbers, but not only) is acceptable (hence the word near) but having some objects "sticking out" to the right is not okay - though this is often a variant of another arrangement, simply rotated 90°.
The final shape may actually be a rectangle, let's see how much the dimensions can differ and if we need to put a constraint on that.
e.g. for n = 4 :
1 2
3 4
n = 6
1 2 3
4 5 6
or
1 2
3 4
5 6
n = 8 perfect 3x3 square with one hole
1 2 3
4 5 6
7 8
n = 10
1 2 3
4 5 6
7 8 9
10
or
1 2 3 4
5 6 7 8
9 10
but not
1 2 3
4 5 6
7 8 9 10
which is anyway the first arrangement turned 90°.
... and so on.
algorithms greatest-common-divisor euclidean-algorithm fair-division
asked Sep 6 at 8:40
Charles
918
add a comment |Â
up vote
0
down vote
favorite
I don't have any fixed constraints but just a general idea. This probably a well known problem too - yet I can't seem to find any literature on it.
Given n identical 2D objects, what is an algorithm to arrange them on the plane such that they form a near square ? Leaving a hole at the end (e.g. in the case of prime numbers, but not only) is acceptable (hence the word near) but having some objects "sticking out" to the right is not okay - though this is often a variant of another arrangement, simply rotated 90°.
The final shape may actually be a rectangle, let's see how much the dimensions can differ and if we need to put a constraint on that.
e.g. for n = 4 :
1 2
3 4
n = 6
1 2 3
4 5 6
or
1 2
3 4
5 6
n = 8 perfect 3x3 square with one hole
1 2 3
4 5 6
7 8
n = 10
1 2 3
4 5 6
7 8 9
10
or
1 2 3 4
5 6 7 8
9 10
but not
1 2 3
4 5 6
7 8 9 10
which is anyway the first arrangement turned 90°.
... and so on.
algorithms greatest-common-divisor euclidean-algorithm fair-division
asked Sep 6 at 8:40
Charles
918
Can you explain why is your first $n=10$ example allowed, but the third isn't? They are the same shape, just rotated 90 degrees. Do you mean it is allowed to stick out at the bottom but not on the right? How close do the dimensions need to be? Must there be at most a difference of 1?
– Jaap Scherphuis
Sep 6 at 9:32
Updated my post. arrangements that are equivalent if one considers 90° rotations are accepted, so long as they are rotated at the end such that extra numbers stick out at the bottom and not the right.
– Charles
Sep 6 at 9:46
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I don't have any fixed constraints but just a general idea. This probably a well known problem too - yet I can't seem to find any literature on it.
Given n identical 2D objects, what is an algorithm to arrange them on the plane such that they form a near square ? Leaving a hole at the end (e.g. in the case of prime numbers, but not only) is acceptable (hence the word near) but having some objects "sticking out" to the right is not okay - though this is often a variant of another arrangement, simply rotated 90°.
The final shape may actually be a rectangle, let's see how much the dimensions can differ and if we need to put a constraint on that.
e.g. for n = 4 :
1 2
3 4
n = 6
1 2 3
4 5 6
or
1 2
3 4
5 6
n = 8 perfect 3x3 square with one hole
1 2 3
4 5 6
7 8
n = 10
1 2 3
4 5 6
7 8 9
10
or
1 2 3 4
5 6 7 8
9 10
but not
1 2 3
4 5 6
7 8 9 10
which is anyway the first arrangement turned 90°.
... and so on.
algorithms greatest-common-divisor euclidean-algorithm fair-division
asked Sep 6 at 8:40
Charles
918
I don't have any fixed constraints but just a general idea. This probably a well known problem too - yet I can't seem to find any literature on it.
Given n identical 2D objects, what is an algorithm to arrange them on the plane such that they form a near square ? Leaving a hole at the end (e.g. in the case of prime numbers, but not only) is acceptable (hence the word near) but having some objects "sticking out" to the right is not okay - though this is often a variant of another arrangement, simply rotated 90°.
The final shape may actually be a rectangle, let's see how much the dimensions can differ and if we need to put a constraint on that.
e.g. for n = 4 :
1 2
3 4
n = 6
1 2 3
4 5 6
or
1 2
3 4
5 6
n = 8 perfect 3x3 square with one hole
1 2 3
4 5 6
7 8
n = 10
1 2 3
4 5 6
7 8 9
10
or
1 2 3 4
5 6 7 8
9 10
but not
1 2 3
4 5 6
7 8 9 10
which is anyway the first arrangement turned 90°.
... and so on.
algorithms greatest-common-divisor euclidean-algorithm fair-division
algorithms greatest-common-divisor euclidean-algorithm fair-division
asked Sep 6 at 8:40
Charles
918
asked Sep 6 at 8:40
Charles
918
edited Sep 6 at 9:45
asked Sep 6 at 8:40
Charles
918
asked Sep 6 at 8:40
Charles
918
asked Sep 6 at 8:40
Charles
918
918
Can you explain why is your first $n=10$ example allowed, but the third isn't? They are the same shape, just rotated 90 degrees. Do you mean it is allowed to stick out at the bottom but not on the right? How close do the dimensions need to be? Must there be at most a difference of 1?
– Jaap Scherphuis
Sep 6 at 9:32
Updated my post. arrangements that are equivalent if one considers 90° rotations are accepted, so long as they are rotated at the end such that extra numbers stick out at the bottom and not the right.
– Charles
Sep 6 at 9:46
add a comment |Â
Can you explain why is your first $n=10$ example allowed, but the third isn't? They are the same shape, just rotated 90 degrees. Do you mean it is allowed to stick out at the bottom but not on the right? How close do the dimensions need to be? Must there be at most a difference of 1?
– Jaap Scherphuis
Sep 6 at 9:32
Updated my post. arrangements that are equivalent if one considers 90° rotations are accepted, so long as they are rotated at the end such that extra numbers stick out at the bottom and not the right.
– Charles
Sep 6 at 9:46
Can you explain why is your first $n=10$ example allowed, but the third isn't? They are the same shape, just rotated 90 degrees. Do you mean it is allowed to stick out at the bottom but not on the right? How close do the dimensions need to be? Must there be at most a difference of 1?
– Jaap Scherphuis
Sep 6 at 9:32
Can you explain why is your first $n=10$ example allowed, but the third isn't? They are the same shape, just rotated 90 degrees. Do you mean it is allowed to stick out at the bottom but not on the right? How close do the dimensions need to be? Must there be at most a difference of 1?
– Jaap Scherphuis
Sep 6 at 9:32
Updated my post. arrangements that are equivalent if one considers 90° rotations are accepted, so long as they are rotated at the end such that extra numbers stick out at the bottom and not the right.
– Charles
Sep 6 at 9:46
Updated my post. arrangements that are equivalent if one considers 90° rotations are accepted, so long as they are rotated at the end such that extra numbers stick out at the bottom and not the right.
– Charles
Sep 6 at 9:46
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
Find out which two consecutive squares $n$ lies between, i.e. $m^2le n < (m+1)^2$.
You can find $m$ by calculating $m=lfloor sqrtn rfloor$.
Then calculate the surplus $k=m^2-n$. Obviously we have $0le k<2m+1$ because $(m+1)^2-m^2=2m+1$.
If $0le k<m$, you can form an $mtimes m$ square with an extra row of $k$ units underneath.
If $m le k<2m+1$ then first add a column to the right of the square to form an $mtimes (m+1)$ rectangle, and then add the remaining $k-m$ as a partial row underneath. This is then an $(m+1)times (m+1)$ square with part of the last row missing.
answered Sep 6 at 9:47
Jaap Scherphuis
3,686616
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Find out which two consecutive squares $n$ lies between, i.e. $m^2le n < (m+1)^2$.
You can find $m$ by calculating $m=lfloor sqrtn rfloor$.
Then calculate the surplus $k=m^2-n$. Obviously we have $0le k<2m+1$ because $(m+1)^2-m^2=2m+1$.
If $0le k<m$, you can form an $mtimes m$ square with an extra row of $k$ units underneath.
If $m le k<2m+1$ then first add a column to the right of the square to form an $mtimes (m+1)$ rectangle, and then add the remaining $k-m$ as a partial row underneath. This is then an $(m+1)times (m+1)$ square with part of the last row missing.
answered Sep 6 at 9:47
Jaap Scherphuis
3,686616
add a comment |Â
up vote
2
down vote
accepted
Find out which two consecutive squares $n$ lies between, i.e. $m^2le n < (m+1)^2$.
You can find $m$ by calculating $m=lfloor sqrtn rfloor$.
Then calculate the surplus $k=m^2-n$. Obviously we have $0le k<2m+1$ because $(m+1)^2-m^2=2m+1$.
If $0le k<m$, you can form an $mtimes m$ square with an extra row of $k$ units underneath.
If $m le k<2m+1$ then first add a column to the right of the square to form an $mtimes (m+1)$ rectangle, and then add the remaining $k-m$ as a partial row underneath. This is then an $(m+1)times (m+1)$ square with part of the last row missing.
answered Sep 6 at 9:47
Jaap Scherphuis
3,686616
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Find out which two consecutive squares $n$ lies between, i.e. $m^2le n < (m+1)^2$.
You can find $m$ by calculating $m=lfloor sqrtn rfloor$.
Then calculate the surplus $k=m^2-n$. Obviously we have $0le k<2m+1$ because $(m+1)^2-m^2=2m+1$.
If $0le k<m$, you can form an $mtimes m$ square with an extra row of $k$ units underneath.
If $m le k<2m+1$ then first add a column to the right of the square to form an $mtimes (m+1)$ rectangle, and then add the remaining $k-m$ as a partial row underneath. This is then an $(m+1)times (m+1)$ square with part of the last row missing.
answered Sep 6 at 9:47
Jaap Scherphuis
3,686616
Find out which two consecutive squares $n$ lies between, i.e. $m^2le n < (m+1)^2$.
You can find $m$ by calculating $m=lfloor sqrtn rfloor$.
Then calculate the surplus $k=m^2-n$. Obviously we have $0le k<2m+1$ because $(m+1)^2-m^2=2m+1$.
If $0le k<m$, you can form an $mtimes m$ square with an extra row of $k$ units underneath.
If $m le k<2m+1$ then first add a column to the right of the square to form an $mtimes (m+1)$ rectangle, and then add the remaining $k-m$ as a partial row underneath. This is then an $(m+1)times (m+1)$ square with part of the last row missing.
answered Sep 6 at 9:47
Jaap Scherphuis
3,686616
answered Sep 6 at 9:47
Jaap Scherphuis
3,686616
answered Sep 6 at 9:47
Jaap Scherphuis
3,686616
answered Sep 6 at 9:47
Jaap Scherphuis
3,686616
3,686616
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2907234%2forganizing-objects-in-a-near-square-pattern%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Can you explain why is your first $n=10$ example allowed, but the third isn't? They are the same shape, just rotated 90 degrees. Do you mean it is allowed to stick out at the bottom but not on the right? How close do the dimensions need to be? Must there be at most a difference of 1?
– Jaap Scherphuis
Sep 6 at 9:32
Updated my post. arrangements that are equivalent if one considers 90° rotations are accepted, so long as they are rotated at the end such that extra numbers stick out at the bottom and not the right.
– Charles
Sep 6 at 9:46