Calcular el índice del triángulo del padre.

Question

No soy matemático, así que intento explicar el tema con una imagen. Dado un triángulo subdividido. Cuento los triángulos más pequeños usando un índice que comienza en 1. Necesito una fórmula que calcule el índice del triángulo padre.$pindex = f(index)$

$$f(1) = 1$$ $$f(2) = 1$$ $$f(3) = 1$$ $$f(4) = 1$$ $$f(5) = 2$$ $$f(6) = 3$$ Esto lleva a la siguiente secuencia de enteros: $$1,1,1,1,2,3,3,3,4,2,2,2,3,4,4,4,5,6,6,6,..$$

No encontré una fórmula en OEIS para esta secuencia. También estoy interesado en cómo mejorar mi pregunta para que sea más clara.

Actualización

Llamemos al alineamiento horizontal de triángulos una fila. Puedo calcular el índice de fila con el índice de triángulo usando esta fórmula A000196: $$r(i) = round(1 + 0.5 * (-3 + sqrt(i) + sqrt(1 + i)))$$ Llamemos al desplazamiento de un triángulo en una fila el desplazamiento de fila. Puedo calcular este desplazamiento con el índice de triángulo usando esta fórmula A071797: $$o(i) =i - (floor(sqrt(i))^2$$

He obtenido la fila y el desplazamiento en esta fila para los índices de triángulo. Creo que estoy cerca de una solución con esto. ¿Algún idea?

Answer 1

Encontré una solución.

• encuentra la fila padre del triángulo
• encuentra el conteo de triángulos padre que ocurren antes de la fila padre
• encuentra el corrimiento de fila del triángulo
• usa un patrón para encontrar el corrimiento de fila para los triángulos padres
• índice padre = 'conteo de triángulos padres antes de la fila' + 'corrimiento de triángulos padres en fila'

Nota que enumero los triángulos con un índice que comienza en 0 en lugar de 1.

Primero define cada segunda fila como la fila padre.

Calculando el índice de fila usando el índice del triángulo A000196: $$r(i)=round(1+0.5(3+sqrt(i)+sqrt(1+i)))$$

Los índices de las filas padre son obviamente: $$floor(r(i) / 2)$$

El conteo de triángulos que ocurren antes de una fila padre A000290: $$c(i) = floor(1 / (1 - cos(1 / (floor(r(i) / 2))))) / 2;$$

Define el corrimiento de fila como el índice de cada triángulo en relación con su fila.

Calculando el corrimiento de fila usando el índice del triángulo A053186 $$o(i) = i - floor(sqrt(i))^ 2$$ Hay un patrón de cómo un corrimiento de fila está relacionado con el corrimiento de fila de la fila padre

El patrón de cada fila par se puede calcular usando el corrimiento de fila o A004524:

$$p2(o) = floor(o / 4) + floor((o + 1) / 4)$$ El patrón de cada fila impar se desplaza en 3 y se resta en 1: $$p1(o) = p2(o + 3) - 1$$

---

Conclusión: $$f(i) = p2(o(i) + (3 - r(i)\\mod 2 * 3)) - (1 - r(i)\\mod 2) + c(r(i) / 2)$$ Código en C#:

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

Answer 2

Indexaremos comenzando con $0$, porque todo es más simple de esa manera. Tenga en cuenta que cualquier entero no negativo $n$ se puede expresar de la siguiente manera

$$n = 4a^2 + 4b + c \tag{$\star$}$$ con enteros $a$, $b$, $c$ tales que $$0 \leq b \leq 2a \quad\text{y}\quad 0 \leq c < 4$$

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

Ahora, podemos representar cada $n$ en la figura objetivo con coordenadas $a$, $b$, $c".

Aquí, "$a$" representa un par particular de filas de números $n$ (o una sola fila de triángulos "padre" $p); "$b, c$" se leen de izquierda a derecha, con $c$ incrementando de $0$ a $3$, luego "rodando" para incrementar $b. (En el diagrama, los colores identifican varios bloques $b".) Es importante destacar que $a^2$ es el número de triángulos padres arriba de la fila $a"; en consecuencia, determinar el índice de un triángulo padre particular se reduce a estudiar $b$ y $c$ dentro de un bloque $a".

La observación clave de la figura con coordenadas es que las instancias donde $c = 0$ corresponden a puntas (hacia arriba o hacia abajo) de los triángulos padres. Vemos que

• Para puntas hacia arriba, el índice del triángulo padre (dentro del bloque $a") para $n$ es simplemente $2b"; para puntas hacia abajo, el índice es $2(b-a)-1$.

• Para $n$ "no punta" (es decir, cuando $c\neq 0$) en la fila superior de un bloque $a", el índice del padre es $2b+1"; en la fila inferior, es $2(b-a)$.

Después de un rato mirando y jugando, aparece la siguiente fórmula:

$$\text{índice del triángulo padre} = a^2 + \left(\; 2b + \operatorname{bool}\left(\;c \neq 0\;\right)\mod (2a+1)\;\right) \tag{$\star\star$}$$

donde "$\operatorname{bool}(x)$" evalúa a $1$ o $0$, según $x$ sea verdadero o falso. (Es un poco trampa, ya que no está "calculado" a partir de $n". Dejaré como ejercicio para el lector algebraizar ese aspecto de la fórmula.)

La complicación "mod $(2a+1)" acomoda el molesto bloque $b" que "envuelve" desde la fila superior hasta la inferior de un bloque $a".

Veamos si la fórmula tiene sentido:

• En la fila superior de un bloque $a", excluyendo el bloque $b" de envoltura, tenemos $b < a", así que el mod $2a+1$ no tiene efecto y $(\star\star)$ se reduce a $$a^2 + 2b + \operatorname{bool(\;c\neq 0\;)}$$ lo cual es consistente con las observaciones de "punta" y "no punta" hechas anteriormente.

• En la fila inferior de un bloque $a", excluyendo el bloque $b" de envoltura, tenemos $a < b \leq 2a", así que $0 \leq 2(b - a)-1 \leq 2a-1$. Nuestra discusión de "punta/no punta" nos dice que debemos esperar un índice de padre de $$a^2 + 2(b-a) - 1 + \operatorname{bool}(\;c\neq 0\;)$$ Dado que la expresión después de $a^2$ nunca excede $2a$, el mod $2a+1$, nuevamente, no tiene efecto. Además, añadiendo $2a+1$ a la cantidad modulada no tiene efecto, excepto para reducir lo anterior a la forma de $(\star\star)$.

• En el bloque de envoltura, $a = b". Para $c = 0$ (el último $n$ en la fila superior), esperamos un desplazamiento de índice del padre desde $a^2$ por $2b" (es decir, $2a); de lo contrario, el desplazamiento debería ser $0$. La fórmula de la fila inferior en el punto anterior cubre el último caso, pero da un desplazamiento de $-1$ para el primer caso. Sin embargo, añadir $2a+1$ es más que una formalidad; cambia el desplazamiento de $-1$ a $2a", que es lo que queremos, sin afectar el desplazamiento de 0 cuando ocurre. Por lo tanto, $(\star\star)$ es, una vez más, nuestro resultado.

Answer 3

Consideramos el triángulo $T$ con entradas $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} $$ y las entradas correspondientes del triángulo padre $T\circ f$ con entradas $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} $$

Distinguimos entre filas con número impar y par en $T$. El índice $k$ de las entradas en $T$ están en la fila ($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*}

Las regiones correspondientes del triángulo padre $T\circ f$ son

\begin{align*} 2n-1,2n:&\qquad (n-1)^2+1\leq f(k)\leq n^2\\ \end{align*} lo cual puede ser fácilmente verificado por ejemplo con $n=3$ en los triángulos anteriores.

Derivamos fórmulas para el mapeo $f$ de las entradas del triángulo $T(k)$ a las entradas del triángulo padre $T(f(k))$.

A partir de (1) y (2) encontramos una representación de $n$ en términos de $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*}

Elementos más a la izquierda en una fila: Con (3) y (4) podemos encontrar una representación del elemento más a la izquierda $(n-1)^2+1$ de $T\circ f$ en la fila $2n-1$ y $2n$ en términos de $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*}

A continuación hacemos el cálculo de desplazamiento del desfase $j\geq 0$ en filas impares y pares. Para ver mejor lo que está sucediendo, observamos un pequeño ejemplo:

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

---

Desfase en la fila $2n-1$:

Calculamos el desfase $j\geq 0$ en esta fila y distinguimos según (7) dos casos

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

Dado que el desfase $4j$ puede ser escrito como \begin{align*} 4j&=k-((2n-2)^2+1)=k-\left\lfloor\sqrt{k-1}\right\rfloor^2-1\\ \end{align*}

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

---

Desfase en la fila $2n$:

Calculamos el desfase $j\geq 0$ en esta fila y distinguimos según (7) dos casos

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

Dado que el desfase $4j+3$ puede ser escrito como \begin{align*} 4j+3&=k-((2n-1)^2+1)=k-\left\lfloor\sqrt{k-1}\right\rfloor^2-1\\ \end{align*}

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

---

Resumen:

Sea $y=\left\lfloor\frac{1}{4}\left(k-1-\left\lfloor\sqrt{k-1}\right\rfloor^2\right)\right\rfloor$. Sea $N_1=(2n-2)^2+1$ y $N_2=(2n-1)^2+1$ denotan el comienzo de una fila según (5) respectivamente. Reuniendo todo obtenemos \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*}