Sea [math]a_0,a_1,a_2,\dots la sucesión de [math]0 y [math]1 formada, respectivamente, por los coeficientes de [math]2^0,2^1,2^2,\dots en el desarrollo binario de [math]S. Hallar la sucesión [math]a_0,a_1,a_2,\dots.
Aclaración: Los corchetes indican la parte entera del número que encierran.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
Tenemos que [math]S=\sum_{i=0}^{1022}\left\lfloor \frac{2^i}{3}\right\rfloor=\sum_{i=0}^{1022}\frac{2^i}{3}-\sum_{i=0}^{511}\left\{\frac{2^{2i}}{3}\right\}-\sum_{i=0}^{510}\left\{\frac{2^{2i+1}}{3}\right\}. Pero [math]2^{2i}\equiv 1\pmod{3} y [math]2^{2i+1}\equiv 2\pmod{3}, luego [math]S=\sum_{i=0}^{1022}\frac{2^i}{3}-\sum_{i=0}^{511}\frac{1}{3}-\sum_{i=0}^{510}\frac{2}{3}=\frac{2^{1023}-1}{3}-512\cdot \frac{1}{3}-511\cdot \frac{2}{3}=\frac{2^{2013}-2}{3}-511. Ahora bien, notemos que
Por lo tanto, la sucesión [math]a_0,a_1,a_2,\dots verifica [math]a_i=0 si [math]i\ge 1022, [math]a_{2i+1}=1 si [math]0\le i\le 510, i \neq 4; [math]a_i=0 si [math]i es par mayor que [math]0, y [math]a_9=a_0=1.
Veamos una idea bastante útil, si tenemos cuatro números, $a, b, r, q$ siendo $r$ el resto en la división de $a$ por $b$ y $q$ el cociente, entonces se cumple que $a = q.b + r \Rightarrow \lfloor \frac{a}{b} \rfloor = \lfloor \frac{q.b+r}{b} \rfloor = \lfloor q + \frac{r}{b} \rfloor = q + \lfloor \frac{r}{b} \rfloor$ Dado que $r < b$ entonces $\lfloor \frac{r}{b} \rfloor = 0$. Esto nos dice que
$$\boxed{\bigg\lfloor \frac{a}{b} \bigg\rfloor = \bigg\lfloor \frac{a-r}{b} \bigg\rfloor = \frac{a-r}{b}}$$
Ahora podemos aplicar este resultado para sacarnos de encima la función piso. Para continuar, $2^2 \equiv 1 \pmod 3 \Rightarrow 2^{2k} \equiv 1 \pmod 3 \Rightarrow 2^{2k+1} \equiv 2 \pmod 3$.
Notar que la cantidad de términos con $-1$ que aparecen son $\frac{1022}{2} + 1 = 512$ y la cantidad de $-2$ que aparecen son $\frac{1022}{2} = 511$ debido a esto se cumple que:
Ahora que tenemos $S$ veamos el siguiente truco. Estamos familiarizados con expresar números en forma polinómica en base $10$, por ejemplo $2489 = 9 + 10.8 + 4.10^2 + 2.10^3$. Sin embargo, es cierto que esto también funciona en base $2$ y por lo tanto lo que debemos hacer es expresar $S$ de la siguiente manera $S = a_0 + a_1.10 + a_2.10^2 + a_3.10^3 + \dots$ con $a_i = 0, 1$. Entonces, intentemos llegar a eso:
Veamos que si tenemos $\frac{2^k}{3} = \frac{2^{k-2}.2^2}{3} = \frac{2^{k-2} + 3.2^{k-2}}{3} = \frac{2^{k-2}}{3} + 2^{k-2}$. Por esta razón podemos ir separando $\frac{2^{1023}-2}{3}$ en varios términos como se ve a continuación:
Usé la misma idea que @drynshock, para llegar a que:
$S=\frac{2^{1023}-2}{3}-511$
A continuación:
$S=\frac{1}{2} \times (\frac{2^{1024}-4}{3}-2^{10}+2)$
$S=\frac{1}{2} \times (\frac{4^{512}-1}{4-1}-4^{5}+1)$
Ahora uso esta notación:
$a_x$ es cómo se ve un cierto número escrito en base x.
Notemos que hay una suma geométrica, y se puede escribir la parte de la derecha fácilmente en base 4, quedando:
$S=\frac{1}{2}_{10} \times (111...111_4-100000_4+1_4)$
$S=\frac{1}{2}_{10} \times 111...11011112_4$
Teniendo el factor de la derecha 512 cifras.
Un truco que se puede hacer como 4 es potencia de 2, es reemplazar cada cifras de base 4 a x cifras de base 2, en este caso x=2, esto se puede demostrar sacando factor común.
Sacando las equivalencias:
$0_4=00_2$
$1_4=01_2$
$2_4=10_2$
$3_4=11_2$
Usando eso:
$S=\frac{1}{10}_2 \times 01010101...0101000101010110_2$
$S=\frac{01010101...010101000101010110_2}{10_2}$
La división es igual que en sistema decimal, entonces:
$S=10101010101...01010100010101011_2$
Teniendo ese número $512 \times 2 - 2 = 1022$ cifras, y ahí queda expresado el número S en binario, donde es fácil expresarlo según la paridad de $i$ con $i<1022$, pero con las excepciones de $i=0$ e $i=9$.
@drynshock, cuidado al final, que pusiste que $a_{1023}=1$, porque fijate que ya de entrada tenías que $S<2^{1023}$, entonces es imposible eso, me parece que en $\frac{2^k}{3}=2^{k-2}+\frac{2^{k-2}}{3}$, te olvidaste del $"-2"$ en el exponente en $2^{k-2}$ cuando lo aplicaste a $k=2023$.
Usé la misma idea que @drynshock, para llegar a que:
$S=\frac{2^{1023}-2}{3}-511$
A continuación:
$S=\frac{1}{2} \times (\frac{2^{1024}-4}{3}-2^{10}+2)$
$S=\frac{1}{2} \times (\frac{4^{512}-1}{4-1}-4^{5}+1)$
Ahora uso esta notación:
$a_x$ es cómo se ve un cierto número escrito en base x.
Notemos que hay una suma geométrica, y se puede escribir la parte de la derecha fácilmente en base 4, quedando:
$S=\frac{1}{2}_{10} \times (111...111_4-100000_4+1_4)$
$S=\frac{1}{2}_{10} \times 111...11011112_4$
Teniendo el factor de la derecha 512 cifras.
Un truco que se puede hacer como 4 es potencia de 2, es reemplazar cada cifras de base 4 a x cifras de base 2, en este caso x=2, esto se puede demostrar sacando factor común.
Sacando las equivalencias:
$0_4=00_2$
$1_4=01_2$
$2_4=10_2$
$3_4=11_2$
Usando eso:
$S=\frac{1}{10}_2 \times 01010101...0101000101010110_2$
$S=\frac{01010101...010101000101010110_2}{10_2}$
La división es igual que en sistema decimal, entonces:
$S=10101010101...01010100010101011_2$
Teniendo ese número $512 \times 2 - 2 = 1022$ cifras, y ahí queda expresado el número S en binario, donde es fácil expresarlo según la paridad de $i$ con $i<1022$, pero con las excepciones de $i=0$ e $i=9$.
@drynshock, cuidado al final, que pusiste que $a_{1023}=1$, porque fijate que ya de entrada tenías que $S<2^{1023}$, entonces es imposible eso, me parece que en $\frac{2^k}{3}=2^{k-2}+\frac{2^{k-2}}{3}$, te olvidaste del $"-2"$ en el exponente en $2^{k-2}$ cuando lo aplicaste a $k=2023$.