Estaba intentando averiguar un método para obtener una potencia de 2 que dividiera un número x en una cantidad impar, y obtuve la función $\gcd(x, x - 2^{\lfloor \log_2(x) \rfloor})$ que funciona bien para lo que yo pretendía. Sin embargo, después de trazar el gráfico para ello en Desmos Obtuve algo parecido a un triángulo de Sierpinski, o al menos una aproximación a él. ¿Cuál es la razón para que esto ocurra en una función no relacionada?
Respuesta
¿Demasiados anuncios?
El número de veces que se puede dividir uniformemente un número entero $n$ por $2$ se denomina " $2$ -ordenada" o " $2$ -valorización de los radicales" (véase aquí y aquí ), y puede escribirse como $\operatorname{ord}_2n$ .
Verifiquemos la fórmula que tienes, que $2^{\operatorname{ord}_2n}=\gcd(n,n-2^{\lfloor \log_2 n\rfloor})$ . En primer lugar, hay identidades que $\gcd(a,b)=\gcd(a,b-a)$ y $\gcd(a,b)=\gcd(a,-b)$ por lo que, de hecho, su fórmula se reduce a $2^{\operatorname{ord}_2n}=\gcd(n,2^{\lfloor \log_2 n\rfloor})$ . Existe un impar $m$ tal que $n=m2^{\operatorname{ord}_2n}$ por la definición del $p$ orden -ádico, y una consecuencia de esto es que $$\log_2n = \log_2m+\operatorname{ord}_2n.$$ Desde $m\geq 1$ y $\operatorname{ord}_2n$ es un número entero, esto demuestra que $\operatorname{ord}_2n \leq \lfloor\log_2n\rfloor$ . Así, $$\gcd(n,2^{\lfloor\log_2 n\rfloor})=\gcd(m2^{\operatorname{ord}_2n},2^{\lfloor\log_2 n\rfloor})=\gcd(2^{\operatorname{ord}_2n},2^{\lfloor\log_2 n\rfloor})=2^{\operatorname{ord}_2n},$$ donde la segunda igualdad se debe a que $m$ es coprimo de $2$ y el tercero es de $\operatorname{ord}_2n \leq \lfloor\log_2n\rfloor$ .
Lo que revela este análisis es que $2^{\lfloor\log_2n\rfloor}$ es alguna elección eficiente de potencia de dos para que todo funcione. (En teoría, $2^n$ también funcionaría).
Ahora que hemos establecido que definitivamente estás graficando $2^{\operatorname{ord}_2 n}$ pensemos en su autosemejanza. Considere estos cálculos: \begin{align*} 2^{\operatorname{ord}_2 (2n)} &= 2^{1 + \operatorname{ord}_2 n} = 2\cdot 2^{\operatorname{ord}_2 n}\\ 2^{\operatorname{ord}_2(2n+1)} &= 2^0 = 1 \end{align*} La segunda se deriva de la observación de que $2n+1$ es impar. Lo que esto significa es que tenemos una regla:
" para trazar los valores del intervalo $1,\dots, 2n$ primero se trazan los valores del intervalo $1,\dots,n$ multiplícalos por dos e inserta un $1$ antes de cada valor".
Por ejemplo, aquí están las primeras iteraciones de esta regla: \begin{align*} & 1 \\ & 1,2\\ & 1,2,1,4 \\ & 1,2,1,4,1,2,1,8 \\ & 1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16 \end{align*}
Este es más o menos el tipo de auto-semejanza que se vería en una variación del triángulo de Sierpinski, donde en lugar de tener los tres subtriángulos similares al triángulo entero, sólo los dos inferiores son similares.
