Re: Algoritmo Sant'Anna

Messaggioda axpgn » 12/08/2017, 23: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: 8987 di 9532
Iscritto il: 20/11/2013, 23:03
Internet Explorer Internet Explorer
Windows Seven 64 bits Windows Seven 64 bits

Re: Algoritmo Sant'Anna

Messaggioda Cantor99 » 13/08/2017, 00: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
Starting Member
Starting Member
 
Messaggio: 14 di 48
Iscritto il: 06/08/2017, 11:52
Località: Dragoni
Google Chrome Mobile 59.0.307 Google Chrome Mobile 59.0.307
Android Android

Re: Algoritmo Sant'Anna

Messaggioda axpgn » 13/08/2017, 01: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: 8989 di 9532
Iscritto il: 20/11/2013, 23:03
Internet Explorer Internet Explorer
Windows Seven 64 bits Windows Seven 64 bits

Re: Algoritmo Sant'Anna

Messaggioda dan95 » 13/08/2017, 07: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
dan95
Advanced Member
Advanced Member
 
Messaggio: 1979 di 2122
Iscritto il: 10/06/2013, 17:37
Località: Roma Caput Mundi
Google Chrome Mobile 47.0.252 Google Chrome Mobile 47.0.252
Android Android

Re: Algoritmo Sant'Anna

Messaggioda giammaria » 13/08/2017, 09: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 4706
Iscritto il: 29/12/2008, 23:19
Località: provincia di Asti
Firefox 52.0 Firefox 52.0
Windows XP Windows XP

Re: Algoritmo Sant'Anna

Messaggioda totissimus » 13/08/2017, 09: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
Junior Member
Junior Member
 
Messaggio: 273 di 276
Iscritto il: 28/05/2012, 13:50
Località: Cefalù
Firefox 54.0 Firefox 54.0
Windows 10 64 bits Windows 10 64 bits

Re: Algoritmo Sant'Anna

Messaggioda axpgn » 13/08/2017, 11: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: 8991 di 9532
Iscritto il: 20/11/2013, 23:03
Internet Explorer Internet Explorer
Windows Seven 64 bits Windows Seven 64 bits

Re: Algoritmo Sant'Anna

Messaggioda dan95 » 13/08/2017, 11: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
dan95
Advanced Member
Advanced Member
 
Messaggio: 1983 di 2122
Iscritto il: 10/06/2013, 17:37
Località: Roma Caput Mundi
Google Chrome Mobile 47.0.252 Google Chrome Mobile 47.0.252
Android Android

Re: Algoritmo Sant'Anna

Messaggioda axpgn » 13/08/2017, 11: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: 8992 di 9532
Iscritto il: 20/11/2013, 23:03
Internet Explorer Internet Explorer
Windows Seven 64 bits Windows Seven 64 bits

Re: Algoritmo Sant'Anna

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

@dans95
Non avevo interpretato bene il testo.
totissimus
Junior Member
Junior Member
 
Messaggio: 274 di 276
Iscritto il: 28/05/2012, 13:50
Località: Cefalù
Firefox 54.0 Firefox 54.0
Windows 10 64 bits Windows 10 64 bits

Precedente

Torna a Scervelliamoci un po'

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite