How to find a function that maps an element to row number in a triangle of integers?

50 Views Asked by At

This is a triangle of integers

0
1      2
3      4      5
6      7      8      9
10     11     12     13     14
........

Is there some function that could map an element number to row number(1 based)?
Here are some examples of different inputs and outputs
Input(element) -> output(row number)
0 -> 1
1, 2 -> 2
3, 4, 5 -> 3
6, 7, 8, 9 -> 4
10, 11, 12, 13, 14

I can't find a function that relates element to row number, this isn't linear, quadratic, exponential, etc.....

1

There are 1 best solutions below

2
On

The first number in row $r$ is $$0+1+\cdots+(r-1)=\frac{r(r-1)}{2}\ .$$ Hence we need to find $r$ such that $$\frac{r(r-1)}{2}\le n<\frac{r(r+1)}{2}\ .$$ Doing some algebra, $$r^2-r\le2n\ ,\qquad r^2+r>2n$$ so $$(2r-1)^2\le8n+1\ ,\qquad (2r+1)^2>8n+1\ .$$ and hence $$\frac{\sqrt{8n+1}-1}{2}<r\le\frac{\sqrt{8n+1}+1}{2}\ .$$ This means that $r$ is the greatest integer which is less than or equal to the RHS, that is, $$r=\left\lfloor\frac{\sqrt{8n+1}+1}{2}\right\rfloor\ .$$