# Calculate the triangle index of the parent triangle.

I am not a mathematician so I try to explain the topic with an image. Given is a subdivided triangle. I count the smallest triangles using an index starting at 1. I need a formula that calculates the index of the parent triangle.$$pindex = f(index)$$

$$f(1) = 1$$ $$f(2) = 1$$ $$f(3) = 1$$ $$f(4) = 1$$ $$f(5) = 2$$ $$f(6) = 3$$ This leads to the following integer sequence: $$1,1,1,1,2,3,3,3,4,2,2,2,3,4,4,4,5,6,6,6,..$$

I did not find a formula at OEIS for this sequence. I am also curious about how to improve my question that it is more clear.

Update

Let's call the horizontal alignment of triangles a row. I can calculate the row index by the triangle index using this formula A000196: $$r(i) = round(1 + 0.5 * (-3 + sqrt(i) + sqrt(1 + i)))$$ Let's call the offset of a triangle in a row the row offset. I can calculate this offset by the triangle index using this formula A071797: $$o(i) =i - (floor(sqrt(i))^2$$

I have got the row and the offset in this row for triangle indices. I think I am close to a solution with this. Any ideas?

• Do you have to ennumerate the little triangles the way you did it above? Because if you ennumerate them in such a way that in each parent triangle we have consecutive numbers (say, in parent triangle 2 we have the little triangles (=l.t.) with 5 on the upper l.t., and then below it the numbers 5,6,7... If you do it as I am describing then there is a very easy formula for the parent triangle's index. Though perhaps I'm misunderstanding something, as I've no idea what "20 indices" you are talking at the end of your post... Commented Nov 25, 2017 at 15:45
• Presumably you'd like a formula for a decomposition into $4^n$ smaller triangles for arbitrary $n$? Commented Nov 25, 2017 at 16:04
• I edited the question to explain what I mean with 'integer sequence'. Unfortunately I can not change the enumeration for the indices since my whole implementation is based on that. Commented Nov 25, 2017 at 16:07

I found a solution.

• find the parent row of the triangle
• find the count of parent triangles that occur before the parent row
• find the row offset of the triangle
• use a pattern to find the row offset for parent triangles
• parent index = 'count of parent triangles before row' + 'offset of parent triangles in row'

Notice that I enumerate triangles by an index starting at 0 instead of 1.

First let's define every second row as the parent row.

Calculating the row index using the triangle index A000196: $$r(i)=round(1+0.5∗(−3+sqrt(i)+sqrt(1+i)))$$

Parent row indices are obviously: $$floor(r(i) / 2)$$

The count of triangles that occur before a parent row A000290: $$c(i) = floor(1 / (1 - cos(1 / (floor(r(i) / 2))))) / 2;$$

Let's define row offset as the index of each triangle relative to its row.

Calculating the row offset using the triangle index A053186 $$o(i) = i - floor(sqrt(i))^ 2$$ There is a pattern of how a row offset is related to the row offset of the parent row

The pattern of each even row can be calculated using the row offset o A004524:

$$p2(o) = floor(o / 4) + floor((o + 1) / 4)$$ The pattern of each odd row is shifted by 3 and subtracted by 1: $$p1(o) = p2(o + 3) - 1$$

Conclusion: $$f(i) = p2(o(i) + (3 - r(i)\pmod 2 * 3)) - (1 - r(i)\pmod 2) + c(r(i) / 2)$$ C# code:

    public static int GetParentTriangleIndex(int i)
{
var row = GetRowOfTriangle(i); // A000196
var patternOffset = 3 - row % 2 * 3;
var rowOffset = GetTriangleRowOffset(i); // A053186
var trianglesBeforeParentRow = GetTriangleCountBeforeRow(row / 2);  //A000290
var pattern = RowPattern(rowOffset + patternOffset) - (1 - row % 2); //  A004524
return pattern + trianglesBeforeParentRow;
}


We'll index starting with $0$, because everything's simpler that way. Note that any non-negative integer $n$ can be expressed thusly

$$n = 4 a^2 + 4 b + c \tag{\star}$$ with integers $a$, $b$, $c$ such that $$0 \leq b \leq 2 a \quad\text{and}\quad 0 \leq c < 4$$

Simply take $$c := ( n \operatorname{mod} 4 ) \qquad a := \left\lfloor \;\frac12 \sqrt{n-c}\;\right\rfloor \qquad b := \frac14\left(n - 4 a^2 - c \right)$$

Now, we can represent each $n$ in the target figure with $a$, $b$, $c$ "coordinates".

Here, "$a$" represents a particular pair of rows of numbers $n$ (or a single row of "parent triangles" $p$); "$b, c$" read left-to-right, with $c$ incrementing from $0$ to $3$, then "rolling over" to increment $b$. (In the diagram, the colors identify various $b$ blocks.) Importantly, $a^2$ is the number of parent triangles above row $a$; consequently, determining the index of a particular parent triangle reduces to studying $b$ and $c$ within an $a$ block.

The key observation from the coordinatized figure is that instances where $c = 0$ correspond to (upward- or downward-pointing) "tips" of the parent triangles. We see that

• For upward-pointing tips, the parent triangle index (within the $a$ block) for $n$ is simply $2b$; for downward-pointing tips, the index is $2(b-a)-1$.

• For "non-tip" $n$ (that is, when $c\neq 0$) in the upper row of an $a$ block, the parent index is $2b+1$; in the lower row, it's $2(b-a)$.

After a while of staring and fiddling, the following formula emerges:

$$\text{parent triangle index} = a^2 + \left(\; 2 b + \operatorname{bool}\left(\;c \neq 0\;\right)\mod (2a+1)\;\right) \tag{\star\star}$$

where "$\operatorname{bool}(x)$" evaluates to $1$ or $0$, according as $x$ is true or false. (It's a little bit of a cheat, as it isn't "calculated" from $n$. I'll leave it as an exercise to the reader to algebraize that aspect of the formula.)

The "mod $(2a+1)$" complication accommodates the pesky $b$ block that "wraps around" from the top row to the bottom of an $a$ block.

Let's sanity-check the formula:

• In the top row of an $a$ block, excluding the wrap-around $b$ block, we have $b < a$, so that the $2a+1$ modding has no effect and $(\star\star)$ reduces to $$a^2 + 2 b + \operatorname{bool(\;c\neq 0\;)}$$ which is consistent with the "tip" and "non-tip" observations made above.

• In the bottom row of an $a$ block, excluding the wrap-around $b$ block, we have $a < b \leq 2a$, so that $0 \leq 2(b - a)-1 \leq 2a-1$. Our "tip/non-tip" discussion tells us to expect a parent index of $$a^2 + 2(b-a) - 1 + \operatorname{bool}(\;c\neq 0\;)$$ Since the expression after the $a^2$ never exceeds $2a$, modding by $2a+1$, again, has no effect. Moreover, adding $2a+1$ to the modded quantity has no effect, except to reduce the above to the form of $(\star\star)$.

• In the wrap-around block, $a = b$. For $c = 0$ (the final $n$ in the top row), we expect a parent index offset from $a^2$ by $2 b$ (that is, $2a$); otherwise, the offset should be $0$. The bottom row formula in the previous bullet covers the latter case, but gives an offset of $-1$ for the former case. Here, though, adding $2a+1$ is more than a formality; it changes the $-1$ offset to $2a$, which we want, while not affecting the $0$ offset when it occurs. So, $(\star\star)$ is, once more, our result.

• Thank you very much for your answer! Commented Nov 27, 2017 at 19:06

We consider the triangle $T$ with entries $T(k),k\geq 1$ $$\begin{array}{l|rrrrrrrrrrrrrrrrrr} n&T(k)\\ \hline 1&&&&&&\color{blue}{1}\\ 2&&&&&\color{blue}{2}&\color{blue}{3}&\color{blue}{4}\\ \hline 3&&&&\color{blue}{5}&6&7&8&\color{blue}{9}\\ 4&&&\color{blue}{10}&\color{blue}{11}&\color{blue}{12}&13&\color{blue}{14}&\color{blue}{15}&\color{blue}{16}\\ \hline 5&&\color{blue}{17}&18&19&20&\color{blue}{21}&22&23&24&\color{blue}{25}\\ 6&\color{blue}{26}&\color{blue}{27}&\color{blue}{28}&29&\color{blue}{30}&\color{blue}{31}&\color{blue}{32}&33&\color{blue}{34}&\color{blue}{35}&\color{blue}{36}\\ \hline \vdots&&&&&&\vdots\\ \end{array}$$ and the corresponding entries of the parent triangle $T\circ f$ with entries $T(f(k)),k\geq 1$ $$\begin{array}{l|rrrrrrrrrrrrrrrrrr} n&T(f(k))\\ \hline 1&&&&&&\color{blue}{1}\\ 2&&&&&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}\\ \hline 3&&&&\color{blue}{2}&3&3&3&\color{blue}{4}\\ 4&&&\color{blue}{2}&\color{blue}{2}&\color{blue}{2}&3&\color{blue}{4}&\color{blue}{4}&\color{blue}{4}\\ \hline 5&&\color{blue}{5}&6&6&6&\color{blue}{7}&8&8&8&\color{blue}{9}\\ 6&\color{blue}{5}&\color{blue}{5}&\color{blue}{5}&6&\color{blue}{7}&\color{blue}{7}&\color{blue}{7}&8&\color{blue}{9}&\color{blue}{9}&\color{blue}{9}\\ \hline \vdots&&&&&&\vdots\\ \end{array}$$

We distinguish odd and even numbered rows of $T$. The index $k$ of the entries in $T$ are in row ($n\geq 1$): \begin{align*} 2n-1:&\qquad (2n-2)^2+1\leq k\leq (2n-1)^2\tag{1}\\ 2n:&\qquad (2n-1)^2+1\leq k\leq (2n)^2\tag{2} \end{align*}

The corresponding regions of the parent triangle $T\circ f$ are

\begin{align*} 2n-1,2n:&\qquad (n-1)^2+1\leq f(k)\leq n^2\\ \end{align*} which can be easily checked e.g. with $n=3$ in the triangles above.

We derive formulas for the mapping $f$ from the triangle entries $T(k)$ to the parent triangle entries $T(f(k))$.

From (1) and (2) we find a representation of $n$ in terms of $k$: \begin{align*} 2n-1:&\qquad\left\lfloor\sqrt{k-1}\right\rfloor=2n-2\quad\Rightarrow\quad \color{blue}{n=\frac{1}{2}\left\lfloor\sqrt{k-1}\right\rfloor+1} \tag{3}\\ 2n:&\qquad\left\lfloor\sqrt{k-1}\right\rfloor=2n-1\quad\Rightarrow\quad \color{blue}{n=\frac{1}{2}\left\lfloor\sqrt{k-1}\right\rfloor+\frac{1}{2}}\tag{4}\\ \end{align*}

Leftmost elements in a row: With (3) and (4) we can find a representation of the left-most element $(n-1)^2+1$ of $T\circ f$ in row $2n-1$ and $2n$ in terms of $k$:

Next we do the offset calculation of the offset $j\geq 0$ in odd and even rows. In order to better see what's going on we look at a small example: \begin{align*} \begin{array}{l|rrrrrrrrrrrrrrrrrr} n&T(f(k))\\ \hline \vdots&&&&&&\vdots\\ 5&\color{blue}{0}&1&1&1&\color{blue}{2}&3&3&3&\color{blue}{4}\\ 6&\color{blue}{0}&\color{blue}{0}&\color{blue}{0}&1&\color{blue}{2}&\color{blue}{2}&\color{blue}{2}&3&\color{blue}{4}&\color{blue}{4}&\color{blue}{4}\\ \vdots&&&&&&\vdots\\ \hline j&\color{blue}{0}&1&2&3&\color{blue}{4}&5&6&7&\color{blue}{8}&9&10\\ \end{array}\tag{7} \end{align*}

Offset in row $2n-1$:

We calculate the offset $j\geq 0$ in this row and distinguish according to (7) two cases

Since the offset $4j$ can be written as \begin{align*} 4j&=k-((2n-2)^2+1)=k-\left\lfloor\sqrt{k-1}\right\rfloor^2-1\\ \end{align*}

Offset in row $2n$:

We calculate the offset $j\geq 0$ in this row and distinguish according to (7) two cases

Since the offset $4j+3$ can be written as \begin{align*} 4j+3&=k-((2n-1)^2+1)=k-\left\lfloor\sqrt{k-1}\right\rfloor^2-1\\ \end{align*}
Let $y=\left\lfloor\frac{1}{4}\left(k-1-\left\lfloor\sqrt{k-1}\right\rfloor^2\right)\right\rfloor$. Let $N_1=(2n-2)^2+1$ and $N_2=(2n-1)^2+1$ denote the beginning of a row according to (5) resp. (6). Putting all together we obtain \begin{align*} \color{blue}{f(k)}&\color{blue}{=\frac{1}{4}\left\lfloor\sqrt{k-1}\right\rfloor^2+\begin{cases} 2y+1&&\left\lfloor\sqrt{k-1}\right\rfloor\equiv 0(2),\,k-N_1\equiv 0(4)\\ 2y+2&&\left\lfloor\sqrt{k-1}\right\rfloor\equiv 0(2),\,k-N_1\not\equiv 0(4)\\ -\frac{1}{2}\left\lfloor\sqrt{k-1}\right\rfloor+2y+\frac{9}{4}&&\left\lfloor\sqrt{k-1}\right\rfloor\equiv 1(2),\,k-N_2\equiv 3(4)\\ -\frac{1}{2}\left\lfloor\sqrt{k-1}\right\rfloor+2y+\frac{5}{4}&&\left\lfloor\sqrt{k-1}\right\rfloor\equiv 1(2),\,k-N_2\not\equiv 3(4)\\ \end{cases}} \end{align*}