Quando si ferma l'algoritmo?
Inviato: 15 nov 2014, 00:31
Per ogni $n \in \mathbb N$, definiamo $a_0 = 0$, $$\begin{cases} a_{i+1} = 2a_i + 1 \pmod {2^n}, &\text{se non è mai apparso} \\ a_{i+1} = 2a_i \pmod {2^n},& \text{altrimenti}\end{cases}$$
Se sia $2a_i + 1 \pmod {2^n}$ che $2a_i \pmod {2^n}$ sono già nella sequenza, l'algoritmo si ferma.
Per esempio con $n=3$, otteniamo $$0, 1, 3, 7, 6, 5, 2, 4$$
Con $n=4$, si ha $$0, 1, 3, 7, 15, 14, 13, 11, 6, 12, 9, 2, 5, 10, 4, 8$$
Dimostrare che, per ogni $n$, ogni numero tra $0$ and $2^n - 1$ sarà generato
(Ovviamente ogni numero generato sarà distinto, bisogna dimostrare che l'algoritmo non si fermi prima di averli generati tutti)
Bonus per la dimostrazione più elegante
Se sia $2a_i + 1 \pmod {2^n}$ che $2a_i \pmod {2^n}$ sono già nella sequenza, l'algoritmo si ferma.
Per esempio con $n=3$, otteniamo $$0, 1, 3, 7, 6, 5, 2, 4$$
Con $n=4$, si ha $$0, 1, 3, 7, 15, 14, 13, 11, 6, 12, 9, 2, 5, 10, 4, 8$$
Dimostrare che, per ogni $n$, ogni numero tra $0$ and $2^n - 1$ sarà generato
(Ovviamente ogni numero generato sarà distinto, bisogna dimostrare che l'algoritmo non si fermi prima di averli generati tutti)
Bonus per la dimostrazione più elegante