7
$\begingroup$

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)$$ enter image description here

$$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?

$\endgroup$
3
  • $\begingroup$ 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... $\endgroup$
    – DonAntonio
    Commented Nov 25, 2017 at 15:45
  • $\begingroup$ Presumably you'd like a formula for a decomposition into $4^n$ smaller triangles for arbitrary $n$? $\endgroup$
    – rogerl
    Commented Nov 25, 2017 at 16:04
  • $\begingroup$ 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. $\endgroup$ Commented Nov 25, 2017 at 16:07

3 Answers 3

2
$\begingroup$

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. parent rows

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.

row offsets

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 pattern

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;
    }
$\endgroup$
2
$\begingroup$

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".

enter image description here

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much for your answer! $\endgroup$ Commented Nov 27, 2017 at 19:06
1
$\begingroup$

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$:

\begin{align*} 2n-1:&\qquad\quad\color{blue}{(n-1)^2+1=\frac{1}{4}\left\lfloor\sqrt{k-1}\right\rfloor^2+1}\tag{5}\\ 2n:&\qquad\quad\color{blue}{(n-1)^2+1=\frac{1}{4}\left\lfloor\sqrt{k-1}\right\rfloor^2-\frac{1}{2}\left\lfloor\sqrt{k-1}\right\rfloor+\frac{5}{4}}\tag{6} \end{align*}

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

\begin{align*} f(4j)&=2j&&\\ f(4j+l)&=2j+1,&\qquad\qquad &l=1,2,3\quad &\\ \end{align*}

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*}

we obtain \begin{align*} \color{blue}{f(4j)}&\color{blue}{=2\left\lfloor\frac{1}{4}\left(k-1-\left\lfloor\sqrt{k-1}^2\right\rfloor\right)\right\rfloor}\\ \color{blue}{f(4j+l)}&\color{blue}{=2\left\lfloor\frac{1}{4}\left(k-1-\left\lfloor\sqrt{k-1}^2\right\rfloor\right)\right\rfloor+1\qquad\qquad l=1,2,3}\\ \end{align*}


Offset in row $2n$:

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

\begin{align*} f(4j+3)&=2j+1&&\\ f(4j+l)&=2j,&\qquad\qquad &l=0,1,2\quad &\\ \end{align*}

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*}

we obtain \begin{align*} \color{blue}{f(4j+3)}&\color{blue}{=2\left\lfloor\frac{1}{4}\left(k-1-\left\lfloor\sqrt{k-1}^2\right\rfloor\right)\right\rfloor+1}\\ \color{blue}{f(4j+l)}&\color{blue}{=2\left\lfloor\frac{1}{4}\left(k-1-\left\lfloor\sqrt{k-1}^2\right\rfloor\right)\right\rfloor\qquad\qquad l=0,1,2}\\ \end{align*}


Summary:

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*}

$\endgroup$
2
  • $\begingroup$ Thank you Markus for the comprehensive answer! $\endgroup$ Commented Nov 27, 2017 at 19:05
  • $\begingroup$ @LucaHofmann: You're welcome. I've updated the answer to enhance the readability. Regards, $\endgroup$ Commented Nov 27, 2017 at 23:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .