Find row of pyramid based on index?

Question

Given a pyramid like:

      0
     1 2
    3 4 5
   6 7 8 9
     ...

and given the index of the pyramid i where i represents the ith number of the pyramid, is there a way to find the index of the row to which the ith element belongs? (e.g. if i = 6,7,8,9, it is in the 3rd row, starting from row 0)

Answer 1

There's a connection between the row numbers and the triangular numbers. The nth triangular number, denoted T_n, is given by T_n = n(n-1)/2. The first couple triangular numbers are 0, 1, 3, 6, 10, 15, etc., and if you'll notice, the starts of each row are given by the nth triangular number (the fact that they come from this triangle is where this name comes from.)

So really, the goal here is to determine the largest n such that T_n ≤ i. Without doing any clever math, you could solve this in time O(√n) by just computing T₀, T₁, T₂, etc. until you find something bigger than i. Even better, you could binary search for it in time O(log n) by computing T₁, T₂, T₄, T₈, etc. until you overshoot, then binary searching on the range you found.

Alternatively, we could try to solve for this directly. Suppose we want to find the choice of n such that

n(n + 1) / 2 = i

Expanding, we get

n² / 2 + n / 2 = i.

Equivalently,

n² / 2 + n / 2 - i = 0,

or, more easily:

n² + n - 2i = 0.

Now we use the quadratic formula:

n = (-1 ± √(1 + 8i)) / 2

The negative root we can ignore, so the value of n we want is

n = (-1 + √(1 + 8i)) / 2.

This number won't necessarily be an integer, so to find the row you want, we just round down:

row = ⌊(-1 + √(1 + 8i)) / 2⌋.

In code:

int row = int((-1 + sqrt(1 + 8 * i)) / 2);

Let's confirm that this works by testing it out a bit. Where does 9 go? Well, we have

(-1 + √(1 + 72)) / 2 = (-1 + √73) / 2 = 3.77

Rounding down, we see it goes in row 3 - which is correct!

Trying another one, where does 55 go? Well,

(-1 + √(1 + 440)) / 2 = (√441 - 1) / 2 = 10

So it should go in row 10. The tenth triangular number is T₁₀ = 55, so in fact, 55 starts off that row. Looks like it works!

Answer 2

I get row = math.floor (√(2i + 0.25) - 0.5) where i is your number

Essentially the same as the guy above but I reduced n² + n to (n + 0.5)² - 0.25