Algoritmo Sant'Anna

[borgianni1]

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)

[dan952]

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ì ...

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]

"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...

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]

"axpgn":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]

"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 ...

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

[axpgn]

Secondo me sì ...

Evita di citare tutto il messaggio, a maggior ragione se è quello precedente ... per rispondere si usa il tasto "Rispondi" non quello "Cita" ...

[dan952]

@Alex

Chi lo dice che ad un certo punto "spuntano" termini della forma $4x+1$?

[axpgn]

@dan95

Perché è così ...

Battute a parte, spiego un meglio (avevo anche postato già questo pomeriggio ma il messaggio non c'è più ... boh! )

Premessa: ho considerato il primo passo uguale ai successivi (come detto nei post precedenti)

Caso 1: $n=4x+1$

$a_1=(3(4x+1)+1)/2=(12x+4)/2=6x+2$ che è pari ed abbiamo finito

Caso 2: $n=4x+3$ con $x$ pari

$a_1=(3(4x+3)+1)/2=(12x+10)/2=6x+5$

$a_2=(3(6x+5)+1)/2=(18x+16)/2=9x+8$ che è pari ed abbiamo finito

Caso 3: $n=4x+3$ con $x$ dispari

$a_1=(3(4x+3)+1)/2=(12x+10)/2=6x+5$

$a_2=(3(6x+5)+1)/2=(18x+16)/2=9x+8$

$a_3=(3(9x+8)+1)/2=(27x+25)/2=k$ con $k$ intero e si ricomincia ...

Ora, è vero che potrebbe proseguire all'infinito ma facendo un'analisi dei termini della successione si può notare che, come ho già detto, se si converte $n$ in binario il numero di passaggi è uguale al numero di cifre $1$ contate partendo da destra fino al primo zero; inoltre accade che se $x'=\lfloor x/2 \rfloor = 4k+1$ allora i passaggi sono $2$, altrimenti sono uno in più di quelli fatti con $x'$; ripetendo se necessario il dimezzamento fino ad arrivare a $1$ (che è della forma $4x+1$ ... )

Ecco, se tu riuscissi a mettere insieme i pezzi ...

Cordialmente, Alex

[Cantor99]

Partendo da $a_1$ e supponendo che dopo $k-1$ iterazioni l'algoritmo non si sia arrestato calcoliamo $a_k$ come
$a_k=\frac{3^k*n+\sum_{m=0}^k (3^m*2^(k-m))}{2^k}$
$a_k=(frac\{3}{2})^k*(n+1)+\sum_{m=0}^(k-1)(frac\{3}{2})^m$
Notando la somma finita di termini di una progressione geometrica, possiamo infine scrivere $a_k$ come
$a_k=(\frac{3}{2})^k*(n+3)-2$

$a_k$ allora è pari solo se $(\frac{3}{2})^k*(n+3)$
Posto $k=2$ abbiamo $n=4t+1$ e l'algoritmo si arresta dopo $k-1=2-1=1$ volte; per $k=3$ invece $n=8t+5$ e l'algoritmo perdura fino alla seconda iterazione. In generale per $k=h$ si ha $n=2^h*t+2^h-3$ e l'algoritmo di durata $h-1$

[dan952]

Scriviamo per bene la soluzione di Alex...

Osservazione. È facile mostrare che se $a_0 \equiv 1 \mod 4$ allora la successione si arresta al secondo termine.
Sia ora $n$ tale che $2^{n+2}|a_0-\sum_{i=0}^{n}2^i$, ricordando che $2^n+2^{n-1}+\cdots+1=2^{n+1}-1$ si dimostra per induzione che per il termine j-esimo della successione, con $j \leq n$,vale
\begin{equation}
a_j \equiv 2^{n+1-j}-1\mod 2^{n+2-j}
\end{equation}
dunque dall'osservazione si deduce che l'algoritmo si arresta dopo $n+1$ passi.

[axpgn]

@dan95
Ti ringrazio molto ed è scritta benissimo ma non c'ho capito granché ...

Forse però ho trovato il meccanismo ...

Ho scoperto che i dispari $t$ della forma $t=4x+3$ si possono generare dai dispari $u$ della forma $u=4x+1$ in questo modo: $t_(ku)=2^ku+2^k-1$

Quindi se partiamo con $n=t_(ku)$ e applichiamo la formula ricorsiva abbiamo $a_1=(3*(2^ku+2^k-1)+1)/2=(3*2^ku+3*2^k-2)/2=3*2^(k-1)u+3*2^(k-1)-1$ che è dispari; reiterando avremo $9*2^(k-2)u+9*2^(k-2)-1$ che è ancora dispari.
Quando però arriviamo alla kappesima iterazione avremo
$a_k=(3^k*2^(k-k)u+3^k*2^(k-k)-2)/2=(3^ku+3^k-2)/2=(3^k(4x+1)+3^k-2)/2=(4*3^kx+3^k+3^k-2)/2=2*3^kx+3^k-1$
che è pari.

Isn't it?

Cordialmente, Alex

[dan952]

Cosa non è chiaro?

[axpgn]

@dan95

Il fatto è che non mi pare che la prima affermazione che fai funzioni ... prendi per esempio $a_0=31$: non esiste nessun $n$ per cui funzioni ...

[dan952]

Certo che esiste $n=4$, 0 è divisibile per 64

[Cantor99]

"Cantor99":

Partendo da $a_1$ e supponendo che dopo $k-1$ iterazioni l'algoritmo non si sia arrestato calcoliamo $a_k$ come
$a_k=\frac{3^k*n+\sum_{m=0}^k (3^m*2^(k-m))}{2^k}$
$a_k=(frac\{3}{2})^k*(n+1)+\sum_{m=0}^(k-1)(frac\{3}{2})^m$
Notando la somma finita di termini di una progressione geometrica, possiamo infine scrivere $a_k$ come
$a_k=(\frac{3}{2})^k*(n+3)-2$

$a_k$ allora è pari solo se $(\frac{3}{2})^k*(n+3)$
Posto $k=2$ abbiamo $n=4t+1$ e l'algoritmo si arresta dopo $k-1=2-1=1$ volte; per $k=3$ invece $n=8t+5$ e l'algoritmo perdura fino alla seconda iterazione. In generale per $k=h$ si ha $n=2^h*t+2^h-3$ e l'algoritmo di durata $h-1$

Potete dirmi se la soluzione è corretta?

[axpgn]

@dan95
Vero, non avevo considerato lo zero ...

Comunque passare da un elemento della successione a quella congruenza per me è un salto nel buio ... ...

spieghi? Grazie

@Cantor99

È roba per dan95 ... comunque dovresti mostrare come sei giunto, dalla ricorsione, a quella formula chiusa

[ot]Non c'era bisogno di riportare nuovamente il tuo messaggio, appesantisce solo la lettura ... [/ot]

Cordialmente, Alex