Pagina 3 di 3

Re: Algoritmo Sant'Anna

MessaggioInviato: 12/08/2017, 22:49
da axpgn
@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 ... :-D ...

spieghi? Grazie :D


@Cantor99
Testo nascosto, fai click qui per vederlo
È roba per dan95 :-D ... 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 ... :wink:


Cordialmente, Alex

Re: Algoritmo Sant'Anna

MessaggioInviato: 12/08/2017, 23:51
da Cantor99
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

Re: Algoritmo Sant'Anna

MessaggioInviato: 13/08/2017, 00:21
da axpgn
@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

Re: Algoritmo Sant'Anna

MessaggioInviato: 13/08/2017, 06:29
da dan95
@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? :| :-D

Re: Algoritmo Sant'Anna

MessaggioInviato: 13/08/2017, 08:02
da giammaria
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.

Re: Algoritmo Sant'Anna

MessaggioInviato: 13/08/2017, 08:47
da totissimus
Mi pare che il problema proposto non sia altro che la famosa congettura di Colatz.https://it.wikipedia.org/wiki/Congettura_di_Collatz

Re: Algoritmo Sant'Anna

MessaggioInviato: 13/08/2017, 10:34
da axpgn
@dan95
Scusa dan95, ma se fossi riuscito a collegare tutto quello che ho scritto non avrei chiesto a te di farlo ... :lol:

Comunque una soluzione poi l'ho trovata ... :-D

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


Cordialmente, Alex

Re: Algoritmo Sant'Anna

MessaggioInviato: 13/08/2017, 10:56
da dan95
@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.

Re: Algoritmo Sant'Anna

MessaggioInviato: 13/08/2017, 10:58
da axpgn
@totissimus
Quasi, mi pare ... :-D
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

Re: Algoritmo Sant'Anna

MessaggioInviato: 13/08/2017, 10:59
da totissimus
@dans95
Non avevo interpretato bene il testo.