How to calculate (x,y) position of number in square

Question

I am looking for a way to determine the X & Y position of a number to draw following square:

1   2   5   10  17
3   4   6   11
7   8   9   12
13  14  15  16

What kind of algorithm / formula can I use ?

I have tried rounding the square root of the number to determine the X position.

To be clear, here is what I want to achieve, numbers with their corresponding X and Y position:

#  X  Y
1: 1  1
2: 2  1
3: 1  2
4: 2  2
5: 3  1
6: 3  2

Answer 1

Note the pattern in your table:

 1 | 2 | 5 |10 |17
-------|   |   |
 3   4 | 6 |11 |
-----------|   |
 7   8   9 |12 |
---------------|
13  14  15  16 |

The algorithm of filling the table is as follows:

start with a 1×1 square with a single 1 in it:

|1|

add a column along the right side of the defined area, filling it with consecutive natural numbers (it will be 1-item column with a single 2 in it):

1|2|

add a row along the bottom side of the defined area, filling it with consecutive natural numbers (it will be 2-items row with numbers 3 & 4):

 1 2
-----
|3 4|

add a column along the right side of the defined area, filling it with consecutive natural numbers (it will be 2-item column with numbers 5 & 6):

1 2|5|  
3 4|6|

add a row along the bottom side of the defined area, filling it with consecutive natural numbers (it will be 3-items row with numbers 7 through 9):

  1 2 5
  3 4 6
 -------
 |7 8 9|

and so on, expand the area by a column and by a row, a column and a row, ...

So, after completing a $k\times k$ square you make a new one of size $(k+1)\times (k+1)$, by placing numbers $k^2+1\dots k^2+k$ in a column $(k+1)$, rows $1$ through $k$, and then numbers $k^2+k+1\dots k^2+2k+1 = (k+1)^2$ in row $(k+1)$, columns $1 \dots k+1$.

Recovering coordinates for a given $n$ is quite easy now: find the largest square $k^2$ less than your number: $$k^2\lt n$$ and test if $n$ is in the $(k+1)$-st column or $(k+1)$-st row.

If $k^2 \lt n \le k^2+k$, then $row=n-k^2, col=k+1$.
If $k^2+k \lt n \le (k+1)^2$, then $row=k+1, col=n-(k^2+k)$.

Answer 2

Given your number $n$, let $n_0$ and $n_1$ be consecutive perfect squares such that $n_0<n\leq n_1$ (in symbols, using the ceiling function, they may be written as $n_0 = (\lceil \sqrt{n}\rceil - 1)^2$ and $n_1 = \lceil \sqrt n\rceil^2$).

Now, compare $n-n_0$ to $n_1-n$ (in other words, check whether $n$ is closest to $n_0$ or to $n_1$). (As a side note, they can never be equal, which is a neat little exercise on its own.) We get two cases:

• $n-n_0<n_1-n$: Then $x = \sqrt{n_1}$ and $y = n-n_0$
• $n-n_0>n_1-n$: Then $x = n - \frac{n_0+n_1-1}{2}$ and $y = \sqrt{n_1}$

You may be able to bake this into a single formula, but it will be large and practically unreadable. At any rate, since this is for programming, a simple if-test will probably suffice, and might be faster too (at least if $n$ is going to get large so that the processor can exploit branch predictions).

Answer 3

Suppose we want to find the $(x,y)$ position of $n = k^2 + r$ with $0 \le r < (k + 1)^2$. That is $k := \lfloor \sqrt n \rfloor$. So the $y$ position grows by $1$ every step, until it reaches $k^2 + k + 1$. Thus: $$y = \min\{n - k^2, k + 1\}$$ Now, $x$ has the value $k + 1$ from $k^2 + 1$ to $k^2 + k$, and grows by $1$ every step after that. Thus: $$x = \begin{cases} k + 1 & , n \le k^2 + k\\ n - (k^2 + k) & , n \gt k^2 + k \end{cases}$$

Answer 4

Here is an algorithm (written for Matlab) that works:

n = 5;

x = zeros(n*n,1);
y = zeros(n*n,1);

x(1) = 1;  % set the first 3 points
y(1) = 1;
x(2) = 2;
y(2) = 1;
x(3) = 1;
y(3) = 2;

for i = 4:n*n
    if (x(i-1) == y(i-1))       % jump all the way down (and 1 to the right)
        x(i) = x(i-1)+1;    
        y(i) = 1;
    elseif (x(i-1) == y(i-1)+1) % jump all the way to the left (and 1 up)
        x(i) = 1;           
        y(i) = y(i-1)+1;
    elseif (x(i-1) > y(i-1))    % move 1 up
        x(i) = x(i-1);
        y(i) = y(i-1)+1;
    else        
        x(i) = x(i-1)+1;        % move 1 to the right
        y(i) = y(i-1);
    end
end 

If at the end you call plot(x,y) you get the following figure: