¿Dejará este algoritmo antes de tiempo?

Question

Para cada $n \in \mathbb N$, vamos a definir $a_0 = 0$, $$\begin{cases} a_{i+1} = 2a_i + 1 \pmod {2^n}, &\text{if it never appeared before} \\ a_{i+1} = 2a_i \pmod {2^n},& \text{otherwise}\end{cases}$$

si tanto $2a_i + 1 \pmod {2^n}$ $2a_i \pmod {2^n}$ ya están en la secuencia, el algoritmo se detiene

por ejemplo, con $n=3$, $$0, 1, 3, 7, 6, 5, 2, 4$$ para$n=4$, $$0, 1, 3, 7, 15, 14, 13, 11, 6, 12, 9, 2, 5, 10, 4, 8$$

El objetivo es demostrar que, para cada $n$, cada número entre el $0$ $2^n - 1$ será generado.

(Por supuesto, cada número generado a ser distinto, pero usted tiene que demostrar que el algoritmo no se detiene antes)

Tengo una un poco larga prueba de esto, pero me gustaría ver otras (más elegante) de las pruebas.

Gracias por su tiempo!

EDITAR

Se me ocurrió la secuencia tratando de resolver el siguiente problema:

Demostrar que para cada $n$, existe una cadena de $A$ $2^n + n - 1$ dígitos para que cada secuencia binaria de $n$ dígitos puede ser extraído como larga de dígitos consecutivos de $A$.

Por ejemplo, con $n=3$, $A = 0001110100$ es largo, $2^3 + 3 - 1$ y podemos encontrar $000, 001, 010, 100, 101, 111, \text{etc}$ subsecuencias de $A$.

Uno puede ver que el hecho de que el algoritmo no se detiene es equivalente a la existencia de $A$

Answer 1

Demostrar que para cada $n$, existe una cadena de $A$ $2^n+n−1$ dígitos para que cada secuencia binaria de n dígitos puede ser extraído como larga de dígitos consecutivos de $A$.

Dicha cadena está garantizada por la secuencia De Bruijn (ajuste $k=2$). La prueba es bastante elegante: la construcción de un grafo cuyos nodos son todos los enteros de$0$$2^{n-1} - 1$, agregar bordes de $i$ $j$fib $i \mod 2^{n-2} = \lfloor j/4 \rfloor$ (es decir, el último $(n-2)$ dígitos de la representación binaria de $i$ es el mismo con el primer $(n-2)$ dígitos de la representación binaria fo $j$), y un camino Euleriano en este gráfico constituye a dicha secuencia. La existencia de un camino Euleriano en este gráfico está garantizada por las propiedades de la gráfica -- si $n > 2$, entonces la gráfica está conectado y todos los nodos tienen aún grado.