Giochino algoritmico

[yurifrey]

Sia $(a,b)$ una coppia di interi strettamente positivi.

Consideriamo il seguente algoritmo:

while $a>0$ do
if $a else $(a,b)$ <-- $(a-b,2b)$.

Determinare:
a). Quando l'algoritmo ha fine.
b). In quali casi l'algoritmo non ha fine ma si ripete periodicamente (con eventuale antiperiodo).
c). In quali casi l'algoritmo non ha fine e non si ripete periodicamente.

La soluzione è davvero molto carina.

[yurifrey]

Due piccoli hint, il primo è un accenno, il secondo già una parte della soluzione:

Primo

Considerare l'invariante $a+b=n$

Secondo

Vedere come si comporta a modulo n e quindi considerare l'algoritmo equivalente: $a -> 2a (mod n)$

[luluemicia]

Ciao,
Se non ho capito male l'algoritmo ha fine se esiste un naturale n tale che $a=2^(n-1)b$ o $b=2^(n-1)a$. E' così?

[yurifrey]

Diciamo che l'algoritmo ha fine se non è più verificata la condizione $a>0$.

Seguendo l'hint ciò equivale a dire: esiste un $k$ tale che $a*2^k-=0 (n)$

[luluemicia]

Ciao,
nel post precedente avevo digitato male (me ne sono accorto solo ora). Volevo dire $a=(2^n-1)b$ e la simmetrica. In altre parole:
$a+b=2^n$