Algoritmo Sant'Anna

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

[dan95]

@Alex

Testo nascosto, fai click qui per vederlo

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! )

Testo nascosto, fai click qui per vederlo

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]

Testo nascosto, fai click qui per vederlo

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$

[dan95]

Scriviamo per bene la soluzione di Alex...

Testo nascosto, fai click qui per vederlo

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

Testo nascosto, fai click qui per vederlo

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

[dan95]

Cosa non è chiaro?

[axpgn]

@dan95

Testo nascosto, fai click qui per vederlo

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

[dan95]

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

[Cantor99]

Testo nascosto, fai click qui per vederlo

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?