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
Quando si ferma l'algoritmo?
Quando si ferma l'algoritmo?
Anti-intellectualism has been a constant thread winding its way through our political and cultural life. Nurtured by the false notion that democracy means that "My ignorance is just as good as your knowledge. "
Re: Quando si ferma l'algoritmo?
Testo nascosto:
Re: Quando si ferma l'algoritmo?
Molto bello! Ottimo lavoro
L'avevo dimostrato in modo molto simile in effetti, con le sequenze di numeri binari.
Avevo postato questo problema su math.stackexchange, se ti va di scrivere la tua risposta li! (se sei registrato)
http://math.stackexchange.com/questions ... efore-time
L'avevo dimostrato in modo molto simile in effetti, con le sequenze di numeri binari.
Avevo postato questo problema su math.stackexchange, se ti va di scrivere la tua risposta li! (se sei registrato)
http://math.stackexchange.com/questions ... efore-time
Anti-intellectualism has been a constant thread winding its way through our political and cultural life. Nurtured by the false notion that democracy means that "My ignorance is just as good as your knowledge. "