Calculate the triangle index of the parent triangle.
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.