Suma de todas las potencias de dos

Question

Demostrar que para cualquier entero positivo $n$ existe un número entero no negativo $k$ con la propiedad de que $n$ puede escribirse como una suma de los números $2^0,2^1,\dots,2^k$ Cada uno de ellos aparece una o dos veces.

Parece que debemos comenzar con la representación canónica de $n$ como una suma de potencias de dos. Para asegurarnos de que todas las potencias de dos aparecen, tendremos que "descomponer" algunas potencias de dos para rellenar los huecos.

Answer 1

Consideremos la representación binaria de $\,n+1 = 2^{k+1}+\sum_{j=0}^k b_j 2^j \;\mid\; b_j \in \{0,1\}\,$ Entonces:

$$n = 2^{k+1}-1+\sum_{j=0}^k b_j2^j = \sum_{j=0}^k 2^{j}+\sum_{j=0}^k b_j2^j = \sum_{j=0}^k (b_j+1)2^j \quad \style{font-family:inherit}{\text{where}}\;\; b_j+1 \in \{1,2\}$$

Answer 2

Básicamente, como dices, rellenar los huecos. Siempre podemos escribir un entero positivo $n$ como una suma de potencias de $2$ utilizando la expansión binaria: $$n = \delta_0 2^0 + \delta_1 2^1 + \ldots + \delta_k 2^k,$$ donde $\delta_i \in \lbrace 0, 1\rbrace$ . Tome el menos $m$ tal que $\delta_i = 0$ y considerar lo menos $l > m$ tal que $\delta_l = 1$ . Entonces, podemos escribir: $$n = 2^0 + \ldots + 2^{m-1} + 2\cdot 2^m + 2^{m+1} + \ldots + 2^{l-1} + \delta_{l+1} 2^{l+1} + \ldots + \delta_k 2^k.$$ Tenga en cuenta que, si bien esto no reduce necesariamente el número de huecos, sí hace que el inicio del primer hueco se adelante. Se podría considerar el uso de la inducción fuerte en $\lfloor\log_2(n)\rfloor - m$ , donde $m$ es el inicio del primer hueco.

Answer 3

Dada cualquier cadena binaria $\overline{b_n\dots b_1b_0}(b_i\in \{0, 1\}, b_n = 1)$ Considere el siguiente procedimiento:

Repita los pasos 1, 2 y 3 hasta que la cadena no contenga "0":

1. $10\mapsto 02$ : Si $\overline{b_{j +1}b_j} = 10$ , dejemos que $\overline{b_{j +1}b_j} \gets02$ .
2. Borra el dígito más alto si es 0.
3. $20\mapsto 12$ : Si $\overline{b_{j +1}b_j} = 20$ , dejemos que $\overline{b_{j +1}b_j} \gets 12$ .

El procedimiento terminará eventualmente y dará la cadena que deseas. Para ver por qué este procedimiento terminará, observe que si definimos $m = \max\{i\colon b_i = 0\}$ para la cadena $\overline{b_n\dots b_1b_0}$ entonces $m \leq n -1$ y disminuye en al menos 1 durante un bucle (1-2-3). En consecuencia, este procedimiento terminará como máximo en $n$ pasos.

Como ejemplo, dado "110101", este procedimiento da

$110101 \mapsto 102021 \mapsto 101221 \mapsto 021221 \mapsto 21221$ .

Answer 4

Las siguientes afirmaciones son equivalentes: $$n=c_02^0+c_12^1+\cdots+c_k2^k\text{ for some }c_0,c_1,\dots,c_k\in\{1,2\}$$ $$n=2^0+2^1+\cdots+2^k+m\text{ where }0\le m\le2^0+2^1+\cdots+2^k$$ $$2^0+2^1+\cdots+2^k\le n\le2(2^0+2^1+\cdots+2^k)$$ $$2^{k+1}-1\le n\le2^{k+2}-2$$ $$2^{k+1}-1\le n\lt2^{k+2}-1$$ $$2^{k+1}\le n+1\lt2^{k+2}$$ $$k+1\le\log_2(n+1)\lt k+2$$ $$k+1=\lfloor\log_2(n+1)\rfloor$$ $$k=\lfloor\log_2(n+1)\rfloor-1$$

Answer 5

Si puedes escribir todos los números de $0$ a $2^n-1$ utilizando sumas de potencias de $2$ de $2^0$ a $2^{n-1}$ , entonces se puede escribir cualquier número de $0$ a $2^{n+1}-1$ utilizando sumas de potencias de $2$ de $2^0$ a $2^n$ representándolo como el número de $0$ a $2^n-1$ y luego añadir $2^n$ . La propiedad se mantiene para $n=0$ por lo que, por inducción, se cumple para todo $n$ .