1

I am trying to solve a problem that requires me to extract a formula from a table, and the table has the following pattern,

\begin{array}{c|c|c|c|c|c|c} \text{row 6} & \text{26}& \text{27}& \text{28}& \text{29}& \text{30}& \text{31}\\ \text{row 5} & \text{25}& \text{24}& \text{23}& \text{22}& \text{21}& \text{32} \\ \text{row 4} & \text{10}& \text{11}& \text{12}& \text{13}& \text{20}& \text{33}\\ \text{row 3} & \text{9}& \text{8}& \text{7}& \text{14}& \text{19}& \text{34}\\ \text{row 2} & \text{2}& \text{3}& \text{6}& \text{15}& \text{18}& \text{35}\\ \text{row 1} & \text{1}& \text{4}& \text{5}& \text{16}& \text{17}& \text{36}\\\hline \text{} & \text{Col. 1}& \text{Col. 2}& \text{Col. 3}& \text{Col. 4}& \text{Col. 5}& \text{Col. 6}\\ \end{array}

In this problem, given a number I'll have to locate it's the row and column position in the table. For example, given a number 4 the answer will be the row and column pair (2, 1)

Though its simple enough for small numbers, but I need to solve it for really large number, such as 1,000,000,000,000,000. And If I try to build a large pre-calculated matrix, it will be too heavy to handle. So I was told to find a formula from the table.

The problem is, I can see the pattern, but I don't know how to approach the pattern to extract a formula from it. Can anyone help?

Quazi Irfan
  • 197
  • 2
    In the last column is there supposed to be a 33 instead of 15? – DRF Jun 01 '15 at 19:05
  • As for the pattern consider the fact that given a pair $(a,b)$ the larger of the two tells you how many rows/columns you must have filled so far. You can then reduce this to finding how many elements are in the square $(max{a-1,b-1},max{a-1,b-1})$ plus a remainder dependent on which direction you are currently filling. – DRF Jun 01 '15 at 19:09

2 Answers2

1

To solve the pattern it's a good idea looking at "nice points" and looking for regularities. In your case that "nice points" are on diagonal.

Call $a_n$ the succession of points on diagonal, you have: $$ a_n = \{1, 3, 7, 13, 21, 31, \dots \} $$ Can you see something interesting? (Differences of values...)

If you can get a function of values on diagonal, the other ones will be calculated trivially as sums and differences of relative positions to the diagonal point on the column / row.

Blex
  • 1,744
1

Look carefully at the edges. On row 1, every second number is square and the same goes for column 1. In particular, if you are given $n\in\mathbb N$ and you want to find where it is, first work out $x=\lfloor\sqrt n\rfloor,$ the integer part of the square root. Then $x^2\le n < (x+1)^2$.

If $x$ is even then $x^2$ is at position $(x,1)$ (row $x$, column 1). If $x$ is odd then $x^2$ is at $(1,x)$. You should be able to figure out how to find the value at $(x,x)$ (call it $y$) and then based on whether $n=y,\;n<y,$ or $n>y,$ you should be able to work out the position.

Dan Robertson
  • 2,959