Determining the row of an element at position _i_ in a triangle generated from this sequence

Question

I'm working on Project Euler problem 18 where we're given a triangle that looks like this:

I can solve the problem (using a shortest-path-like algorithm), but as is often the case with problems like these, I stumbled onto another problem while solving the first.

The problem arose while I was trying to find a simple way to generate a graph from the triangle.

If this were a binary tree (which it is not) I would be able to determine the left and right children for each parent node with the equations left_child = 2*i+1 and right_child = 2*i+2 – but I haven't been able to come up with a closed-form solution for the triangle in this problem.

So what I would like to know, for a start, is if there is a closed-form equation to find the corresponding level for a given index in this triangle; hopefully, from there I can derive the left and right child equations. If no closed-form equation exists, how could I prove it?

I can already see that the levels would follow the pattern

[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6...]

Is there even a way to represent this sequence as a summation or some other formula?

Thank you.

---

EDIT:

# Code for messing around with this problem
triangle = \
    "0 \n" \
    "1 2 \n" \
    "3 4 5 \n" \
    "6 7 8 9 \n" \
    "10 11 12 13 \n" \
    "14 15 16 17 18 \n" \
    "19 20 21 22 23 24"


from collections import namedtuple, defaultdict

Children = namedtuple('Children', ['left', 'right'])
children = defaultdict(lambda: None)

triangle = [s.split() for s in triangle.split("\n")]
print(triangle)
print('number of elements: ', sum([len(ls) for ls in triangle]))

index = 0
for level in range(len(triangle)):
    lvl = triangle[level]
    for element in range(1, len(lvl)):
        children[index] = Children(lvl[element - 1], lvl[element])
        index += 1

print('0 -->', children[0])

print('3 -->', children[3])
print('4 -->', children[4])
print('5 -->', children[5])

print('23 -->', children[23])
print('24 -->', children[24])

Answer 1

Call the first row (with 1 element) row $0$ and the first element on each row element $0$. (as in Pascal's triangle)

For row $y$, there are $y$ rows on top it, and for element $x$, there are $x$ elements to the left of it.

So to find the index of the element $x$ on row $y$, where $0 \le x \le y$,

$$i(y, x) = \frac{y(y+1)}{2} + x$$

where the element $0$ on row $0$ has index $i(0,0) = 0$.

For the purpose of finding the children of a particular element, it is easier if you also know the element's row $y$ (the level in your for loop). Then the index of the left child is just $y+1$ later:

$$L(i,y) = i + y + 1,\quad R(i,y) = L(i,y) + 1$$

Otherwise, the row $y$ of an element at index $i$ can be determined by some flooring:

$$\begin{align*} 0 &\le x &x&< y+1\\ \frac{y(y+1)}{2} &\le i &i&<\frac{y(y+1)}{2} + y + 1\\ y^2 + y -2i &\le 0&0 &< y^2 + 3y + 2 - 2i\\ \frac{-1+\sqrt{1-4(-2i)}}{2}&\ge y & y &> \frac{-3 + \sqrt{9 - 4(2-2i)}}{2}\\ \frac{-1+\sqrt{1+8i}}{2}&\ge y&y&>\frac{-1 + \sqrt{1+8i}}{2}-1\\ \end{align*}$$ $$\begin{align*} y &= \left\lfloor\frac{-1+\sqrt{1+8i}}{2}\right\rfloor\\ L(i) &= i + \left\lfloor\frac{-1+\sqrt{1+8i}}{2}\right\rfloor + 1\\ &= i + \left\lfloor\frac{1+\sqrt{1+8i}}{2}\right\rfloor \end{align*}$$

But I don't see this easier than keeping a $y$ level counter somewhere.