Working out which line a number is on in a Floyd's Triangle

Question

A Floyd's Triangle is explained here if you do not know what one is. Essentially most programmers at some point have made one and I was recently questioned about a way to quickly find out which line a number lies on. The best mathematical solution I could come up with to accomplish this was $$\frac{1+\sqrt{1+8x}}{2}$$ Using this you would replace the $x$ with the number whose line you want to find. For example if you wanted to know which line $2,5000,000$ was on you would use $\frac{1+\sqrt{1+8(2500000)}}{2}$ which equals $2236.568033$. To determine which line it is you just have to remove the decimal which leaves the line $2236$.

There is one floor which I did notice. If you use the a number which is on the end of a line, lets say $15$ the answer you get out of the equation is $6$ which is obviously not right because the line it is on is line $5$.

So my question is can a formula be made which gives you the correct line for all numbers when they are substituted in, including the numbers on the end of a line?

Answer 1

Let us use the formula for the lazy caterer's sequence which forms the left edge of Floyd's triangle.

$$p_n = \frac{n^2+n+2}{2}$$

Given $x$, we want $n\in \mathbb{N}$ s.t. $p_n \leq x < p_{n+1}$. Examining the right inequality gives:

$$x < \frac{(n+1)^2+(n+1)+2}{2}$$ $$n^2 + 3n + 4 - 2x > 0$$

Since the first root of the quadratic is negative, we must have $n$ bigger than the bigger root. Hence

$$n > \frac{-3+\sqrt{-7+8x}}{2}\implies n = \mathrm{ceil}\left[{\frac{-3+\sqrt{-7+8x}}{2}}\right]$$

where we should add a +1 if the argument is an integer., and we we used the intuition that there should only be one such $n$ (so we will not bother with a proof). (a proof that this $n$ is correct follows easily from solving the other inequality because the formula for $n$ below is identical to the one above).

One can do a similar derivation using the first inequality and get a cleaner result

$$ n = \mathrm{floor}\left[\frac{-1+\sqrt{-7+8x}}{2}\right]$$

(Hope I don't have any errant +1/-1; my row counting starts from 0).

Answer 2

The simple way is to start with the numbers at the right end of the rows. If $n$ is the number and $r$ is the row, we have $n=\frac 12r(r+1)$, which we can invert using the quadratic formula to get $r=\frac 12(-1+\sqrt{1+8n})$ This needs no floor or ceiling, it will always be an exact natural. If we extend $n$ to the other elements of the row, the formula gives a fractional value which is above the next lower row and below the current one. So you have $$r=\left\lceil \frac 12(-1+\sqrt{1+8n})\right \rceil$$