Demuestre que al escribir todos los números pares en una columna, luego encadenando$2n+1$ de ellos, obtenemos todos los números naturales exactamente una vez.

Question

Aquí está la idea: Escribir todos los números en la primera columna, a continuación, obtener los números de la segunda columna tomando el número a la izquierda ($n$), y el cálculo de $2n+1$. Y tener que repetir esto.

Aquí es cómo se hace: $$\begin{matrix} 0 & 1 & 3 & 7 & 15 & 31 & 63 & \dots \\ 2 & 5 & 11 & 23 & 47 & 95 & 191 & \dots \\ 4 & 9 & 19 & 39 & 79 & 159 & 319 & \dots \\ 6 & 13 & 27 & 55 & 111 & 223 & 447 & \dots \\ 8 & 17 & 35 & 71 & 143 & 287 & 575 & \dots \\ 10 & 21 & 43 & 87 & 175 & 351 & 703 & \dots \\ 12 & 25 & 51 & 103 & 207 & 415 & 831 & \dots \\ 14 & 29 & 59 & 119 & 239 & 479 & 959 & \dots \\ 16 & 33 & 67 & 135 & 271 & 543 & 1087 & \dots \\ 18 & 37 & 75 & 151 & 303 & 607 & 1215 & \dots \\ 20 & 41 & 83 & 167 & 335 & 671 & 1343 & \dots \\ 22 & 45 & 91 & 183 & 367 & 735 & 1471 & \dots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{de la matriz}$$

Y esto es lo que parece que para escribir sólo hasta el primer $50$ números conseguido de esta manera:

$$\begin{matrix} 0 & 1 & 3 & 7 & 15 & 31 & \dots\\ 2 & 5 & 11 & 23 & 47 & \dots & \\ 4 & 9 & 19 & 39 & \dots & & & \\ 6 & 13 & 27 & \dots & & & & \\ 8 & 17 & 35 & \dots & & & & \\ 10 & 21 & 43 & \dots & & & & \\ 12 & 25 & \dots & & & & & \\ 14 & 29 & \dots & & & & & \\ 16 & 33 & \dots & & & & & \\ 18 & 37 & \dots & & & & & \\ 20 & 41 & \dots & & & & & \\ 22 & 45 & \dots & & & & & \\ 24 & 49 & \dots & & & & & \\ 26 & \dots & & & & & & \\ 28 & \dots & & & & & & \\ 30 & \dots & & & & & & \\ 32 & \dots & & & & & & \\ 34 & \dots & & & & & & \\ 36 & \dots & & & & & & \\ 38 & \dots & & & & & & \\ 40 & \dots & & & & & & \\ 42 & \dots & & & & & & \\ 44 & \dots & & & & & & \\ 46 & \dots & & & & & & \\ 48 & \dots & & & & & & \\ 50 & \dots & & & & & & \\ \end{de la matriz}$$

Pregunta: ¿podemos obtener todos los números naturales exactamente una vez cuando la redacción de todas las filas de esta manera?

Pregunta extra: Al escribir los números en orden, lo que la curva de hacer hemos aproximado al conectar el extremo de cada fila? (Lo de la curva de hacer nos acercamos más y más a añadir más números en orden a nuestra lista?)

$\quad\quad\quad\quad\quad\quad\quad\quad$

Mi conjetura es que la línea roja se aproxima a $\ln(x), x \in [0,1]$.

Answer 1

Pues bien, la primera columna tiene todos los números pares, es decir, los $\equiv 0 \bmod 2$, y no de los $\equiv 1 \bmod 2$

la segunda columna tiene los números de $\equiv 1\bmod 4$, y las dos primeras columnas pierdas los $\equiv 3 \bmod 4$

Asimismo, las tres primeras columnas pierdas solo los números de la $\equiv 7 \bmod 8$

Supongamos que tenemos el número entero $n$ - la columna que aparece en? Bueno, si $2^r$ es el mayor poder de $2$ que se divide $n+1$, entonces su número aparecerá en la $(r+1)^{th}$ columna.

He esbozado algunas ideas que usted puede ver los patrones para explorar, y las conjeturas probar. Por cierto, la tabla sería más sugerente si usted tomó a $31$ o $63$ y se cuentan los números en las diferentes columnas.

Answer 2

En primer lugar, observe que la entrada en la $m$-ésima fila y $n$-columna está dado por: $m_{m,n}=(2m+1)2^n-1$ para $m,n\geq0$.

A partir de esto es sencillo para mostrar la asignación de $(m,n)\to m_{m,n}$ es inyectiva.

Respecto a su segunda pregunta:

$$ (2m+1)2^n-1\leq M\\ \Leftrightarrow n\leq\Big(\log(M+1)-\log(2m+1)\Big)/\log(2) $$

Por lo tanto, la línea roja está dada por

$$ n=\Big\lfloor \Big(\log(M+1)-\log(2m+1)\Big)/\log(2)\Big\rfloor $$

Así que se fueron un poco a la derecha con usted asunción!