Algoritmo Sant'Anna

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

Testo nascosto, fai click qui per vederlo

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

spieghi? Grazie

@Cantor99

Testo nascosto, fai click qui per vederlo

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

Testo nascosto, perché contrassegnato dall'autore come fuori tema. Fai click in quest'area per vederlo.

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

Cordialmente, Alex

Testo nascosto, fai click qui per vederlo

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

@Cantor99

Testo nascosto, fai click qui per vederlo

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

@Alex

Testo nascosto, fai click qui per vederlo

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?

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

Testo nascosto, fai click qui per vederlo

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.

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

@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

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

@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

@dans95
Non avevo interpretato bene il testo.