Algoritmo Sant'Anna

[borgianni]

Dato un numero naturale dispari n, si consideri il seguente algoritmo:
si calcoli

$a1=(3n+2)/2$

se a1 è pari, l’algoritmo si arresta, altrimenti si calcoli:

$a2=(3a1+1)/2$

se a2 è pari, l’algoritmo si arresta, altrimenti si calcoli $a3=(3a2+1)/2$
e così via.
Dimostrare che, qualunque sia il numero n considerato, l’algoritmo, ad un certo punto, si arresta, cioè la successione da esso generata
a1 , a2 ,...
è finita. Dire da quanti termini essa è costituita.

[otta96]

Ma $a_1$ non è intero...

[Cantor99]

Partendo da $a_1$ possiamo costruire la successione
$a_2=\frac{9n+8}{4}$
$a_3=\frac{27n+28}{8}$
E, supponendo che dopo $k-1$ iterazioni l'algoritmo non si sia arrestato, si ha
$a_k=\frac{n*3^k+3^k\pm \1}{2^k}$
dove il segno + vale per $k$ dispari mentre il - per $k$ pari.
Ora si tratta di dimostrare che esiste un intero $m$ per cui $a_m$ è pari e ciò accade se e solo se
$n*3^m+3^m=3^m*(n+1)=2t\pm \1$ per qualche $t\in \Z$
Ma ciò è impossibile perché $n+1$ è pari e $2t\pm \1$ dispari.
Non so dove ho sbagliato ma a me l'algoritmo non si arresta mai per $n$ dispari (mentre per $n$ pari lo fa)

[dan95]

Questo problema mi sta mettendo in difficoltà, per i casi in cui $n=1+4k$ e $n=3+8n$ l'ho fatto ma mi manca il caso $n=7+8n$, che praticamente sembra impossibile...

[axpgn]

Perché non mettete sotto spoiler?

Comunque dovrebbe essere così ...

Testo nascosto, fai click qui per vederlo

Premetto che per me il primo passaggio è come gli altri, se $n=4x+1$ allora diventa pari dopo un passaggio mentre se $n=4x+3$ si deve distinguere se $x=$ è pari o dispari: se è pari dopo due passaggi si ferma mentre se è dispari continua finché $a_n$ non diventa del formato $4x+1$ ... peraltro se si converte $n$ in binario, per conoscere il numero di passaggi prima dello stop basta contare quanti $1$ ci sono partendo da destra fino al primo zero ...

Cordialmente, Alex

[Cantor99]

Questo problema mi sta mettendo in difficoltà, per i casi in cui $n=1+4k$ e $n=3+8n$ l'ho fatto ma mi manca il caso $n=7+8n$, che praticamente sembra impossibile...

Vorrei chiederti come si possa arrestare dopo un passaggio per $n=1+4k$, cioè ad esempio, ponendo $n=5$ si ha $a_1=\frac{17}{2}$, $a_2=\frac{53}{4}$ poi $a_3=\frac{163}{8}$. Non ti trovi con quello che ho scritto? Mi potresti spiegare dove ho sbagliato?
Grazie

[axpgn]

L'espressione per $a_1$ è sbagliata, deve essere come le altre perché funzioni ... comunque cosa vi costa mettere sotto spoiler?

[Cantor99]

L'espressione per $a_1$ è sbagliata, deve essere come le altre perché funzioni ... comunque cosa vi costa mettere sotto spoiler?

Sono nuovo del forum e non so come mettere lo spoiler, cosa devo scrivere?...in che senso ho sbagliato $a_1$? Ho messo $n=5$ che è nella forma $4k+1$...non capisco

[axpgn]

Non hai sbagliato tu, ha sbagliato colui che ha iniziato la discussione ... l'espressione per il calcolo di $a_1$ deve essere come le altre cioè la formula ricorsiva è unica, così $a_n=(3a_(n-1)+1)/2$.

Per quanto riguarda lo spoiler, sopra il form di risposta ci sono tante opzioni tra cui "spoiler": selezioni il testo da nascondere e poi premi quel pulsante ...

[Cantor99]

Non hai sbagliato tu, ha sbagliato colui che ha iniziato la discussione ... l'espressione per il calcolo di $a_1$ deve essere come le altre cioè la formula ricorsiva è unica, così $a_n=(3a_(n-1)+1)/2$.

Per quanto riguarda lo spoiler, sopra il form di risposta ci sono tante opzioni tra cui "spoiler": selezioni il testo da nascondere e poi premi quel pulsante ...

Quindi poniamo $a_1=\frac{3n+1}{2}$?