Re: Algoritmo Sant'Anna

Messaggioda axpgn » 12/08/2017, 22:49

@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
axpgn
Cannot live without
Cannot live without
 
Messaggio: 8969 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Algoritmo Sant'Anna

Messaggioda Cantor99 » 12/08/2017, 23:51

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
Senior Member
Senior Member
 
Messaggio: 14 di 1238
Iscritto il: 06/08/2017, 10:52
Località: Dragoni

Re: Algoritmo Sant'Anna

Messaggioda axpgn » 13/08/2017, 00:21

@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
axpgn
Cannot live without
Cannot live without
 
Messaggio: 8971 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Algoritmo Sant'Anna

Messaggioda dan95 » 13/08/2017, 06:29

@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
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Cannot live without
Cannot live without
 
Messaggio: 1979 di 5268
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Algoritmo Sant'Anna

Messaggioda giammaria » 13/08/2017, 08:02

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.
- Indicando i metri con m e i centimetri con cm, si ha m=100 cm. Quindi 5 centimetri equivalgono a metri m=100*5=500.
- E' disonesto che un disonesto si comporti in modo onesto (R. Powell)
giammaria
Cannot live without
Cannot live without
 
Messaggio: 4702 di 9469
Iscritto il: 29/12/2008, 22:19
Località: provincia di Asti

Re: Algoritmo Sant'Anna

Messaggioda totissimus » 13/08/2017, 08:47

Mi pare che il problema proposto non sia altro che la famosa congettura di Colatz.https://it.wikipedia.org/wiki/Congettura_di_Collatz
totissimus
Average Member
Average Member
 
Messaggio: 273 di 633
Iscritto il: 28/05/2012, 12:50
Località: Cefalù

Re: Algoritmo Sant'Anna

Messaggioda axpgn » 13/08/2017, 10:34

@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
axpgn
Cannot live without
Cannot live without
 
Messaggio: 8973 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Algoritmo Sant'Anna

Messaggioda dan95 » 13/08/2017, 10:56

@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.
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Cannot live without
Cannot live without
 
Messaggio: 1983 di 5268
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Algoritmo Sant'Anna

Messaggioda axpgn » 13/08/2017, 10:58

@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
axpgn
Cannot live without
Cannot live without
 
Messaggio: 8974 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Algoritmo Sant'Anna

Messaggioda totissimus » 13/08/2017, 10:59

@dans95
Non avevo interpretato bene il testo.
totissimus
Average Member
Average Member
 
Messaggio: 274 di 633
Iscritto il: 28/05/2012, 12:50
Località: Cefalù

Precedente

Torna a Scervelliamoci un po'

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite