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.

[Cantor99]

Il primo termine è $a_1=\frac{3n+1}{2}$, il secondo
$a_2=\frac{\frac{3*3*n+1*3}{2}+1}{2}$
$a_2=\frac{3^2*n+3^1+2^1}{2^2}$
Il terzo invece
$a_3=\frac{\frac{3^3*n+3^2+3^1*2^1}{2^2}+1}{2}$
$a_3=\frac{3^3*n+3^2+3^1*2^1+2^2}{2^3}$
E così via. Non saprei però come formalizzare il tutto

[axpgn]

@Cantor99

Ho riletto la tua soluzione e mi pare ok fino a "... allora è pari solo se ..."; non ho controllato i conti successivi, presumo siano giusti anche quelli, ma non è questo il punto: a me sembra che tu abbia dimostrato che l'algoritmo si ferma ad un dato punto $k$ se esiste un certo tipo di numero $n$ ma il problema è al contrario ovvero dato $n$ determinare se esiste $k$ ... non so se mi spiego ... IMHO

Cordialmente, Alex

[dan952]

@Alex

Per ipotesi $a_0 \equiv 2^{n+1}-1 \mod 2^{n+2}$, mostriamo che in generale se vale per $j$ vale anche per $j+1 \leq n$ (una sorta di induzione su un insieme finito). Dunque per ipotesi $a_j \equiv 2^{n+1-j}-1\mod 2^{n+2-j}$, moltiplicando per 3 e aggiungendo 1 otteniamo
\begin{equation}
3a_j+1=2a_{j+1} \equiv 2^{n+2-j}+2^{n+1-j}-2 \equiv 2^{n+1-j}-2 \mod 2^{n+2-j}
\end{equation}
dalla (1) deduco che esiste $m \in \mathbb{N}$ tale che $2a_{j+1}=2^{n+2-j}m+2^{n+1-j}-2$ da cui $a_{j+1}=2^{n+2-(j+1)}m+2^{n+1-(j+1)}-1$.

Scusa Alex ma l'idea chiave della soluzione l'ho presa da te, come fai a non capirla?

[giammaria2]

Vedo soluzioni ingegnose, ma ce n'è una molto più facile.

Consiste nell'aumentare tutto di 1 ed esaminare la successione delle $b_k=a_k+1$. Se $b_k$ è dispari, essa ha fine; se è pari ricaviamo la formula di ricorrenza:
$b_k-1=(3(b_(k-1)-1)+1)/2->b_k=1+(3b_(k-1)-3+1)/2=3/2b_(k-1)$
Tenendo presente la condizione iniziale $b_0=n+1=m$ (con $m$ pari e positivo), si ha quindi
$b_k=(3/2)^k m$
Posto allora $m=n+1=2^r A$, con A dispari, $b_k$ diventa dispari quando $k=r$ e lì si finisce.

[totissimus]

Mi pare che il problema proposto non sia altro che la famosa congettura di Colatz.https://it.wikipedia.org/wiki/Congettura_di_Collatz

[axpgn]

@dan95
Scusa dan95, ma se fossi riuscito a collegare tutto quello che ho scritto non avrei chiesto a te di farlo ...

Comunque una soluzione poi l'ho trovata ...

@giammaria
Bella e lineare ... ... in definitiva, in un modo o nell'altro si trattava di "far sparire" tutti i $2$ ...


Cordialmente, Alex

[dan952]

@totissimus
Magari fosse la congettura di Collatz, saremo tutti milionari. La congettura dice che l'algoritmo seguente:
- Prendo $n$ numero naturale
- Se $n$ pari divido per $2$
- Se $n$ dispari $(3n+1)/2$
Termina in un numero finito di passi a 1.

[axpgn]

@totissimus
Quasi, mi pare ...
Perché il quesito proposto diventi la congettura di Collatz si dovrebbe aggiungere la condizione che la catena si fermi quando l'ennesimo termine è una potenza di $2$ (oltre ovviamente al fatto che ogni termine va direttamente diviso per due se è pari invece che moltiplicarlo per tre e aggiungere uno)

Cordialmente, Alex

[totissimus]

@dans95
Non avevo interpretato bene il testo.