Pagina 1 di 1
algoritmo
Inviato: 01 set 2008, 18:13
da L'ale
Dato un numero naturale dispari n, si consideri il seguente algoritmo:
si calcoli
a1 = (3n + 1)/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 a un certo punto si arresta, cioè la successione da esso generata
a1,a2,...
è finita.
Dire da quanti termini essa è costituita.
Inviato: 07 set 2008, 16:28
da gianmaria
Riassumendo: la successione è definita da $ a_0=n $ e $ a_{k+1}=\dislaystyle \frac{3a_k+1} 2 $ e si arresta quando $ a_k $ diventa pari. Posto $ b_k=a_k+1 $ si ottiene $ b_0=n+1 $ e $ b_{k+1}=\frac 3 2 b_k $; si tratta perciò di una progressione geometrica ed è $ b_k=(n+1) (\frac 3 2)^k $. Il calcolo si ferma quando $ b_k $ diventa dispari, cioè quando k è uguale all’esponente della massima potenza di 2 per cui n+1 è divisibile.
Inviato: 07 set 2008, 17:06
da Stex19
io so che se ho un $ a_j=1 (mod4) $ allora avrò che $ 3a_j=3 (mod4) $, quindi $ a_{j+1} $ sarà pari.
però non so come dimostrare che prima o poi nella sucessione comparirà sicuramente un numero congruo a 1 mod4...
p.s. come si fa i lsegno di congruo in latex??
Inviato: 07 set 2008, 17:51
da Haile
Stex19 ha scritto:io so che se ho un $ a_j=1 (mod4) $ allora avrò che $ 3a_j=3 (mod4) $, quindi $ a_{j+1} $ sarà pari.
però non so come dimostrare che prima o poi nella sucessione comparirà sicuramente un numero congruo a 1 mod4...
p.s. come si fa i lsegno di congruo in latex??
Non c'è nulla da dimostare...
Sia $ $a_0$ $ un dispari. Esso allora è di forma $ $4k+1$ $ o $ $4k+3$ $.
Se $ $a_0=4k+1$ $ allora
$ $a_1=\frac{3(4k+1)+1}{2} = 2(3k+1)$ $
che è pari, e l'algoritmo si ferma dopo 1 passaggio. A questo punto quindi suppongo tranquillamente che l'$ $n$ $ che si sceglie all'inizio sia di forma $ $4k+3$ $.
Comunque giunti a questo punto la dimostrazione dell'intero problema è tutt'altro che finita...
Inviato: 07 set 2008, 19:47
da Stex19
Haile ha scritto:Stex19 ha scritto:io so che se ho un $ a_j=1 (mod4) $ allora avrò che $ 3a_j=3 (mod4) $, quindi $ a_{j+1} $ sarà pari.
però non so come dimostrare che prima o poi nella sucessione comparirà sicuramente un numero congruo a 1 mod4...
p.s. come si fa i lsegno di congruo in latex??
Non c'è nulla da dimostare...
Sia $ $a_0$ $ un dispari. Esso allora è di forma $ $4k+1$ $ o $ $4k+3$ $.
Se $ $a_0=4k+1$ $ allora
$ $a_1=\frac{3(4k+1)+1}{2} = 2(3k+1)$ $
che è pari, e l'algoritmo si ferma dopo 1 passaggio. A questo punto quindi suppongo tranquillamente che l'$ $n$ $ che si sceglie all'inizio sia di forma $ $4k+3$ $.
Comunque giunti a questo punto la dimostrazione dell'intero problema è tutt'altro che finita...
si... questo l'avevo capito...
volevo sapere se si riesce a dimostrare che esiste un n-esimo termine che è della forma 4k+1....
Inviato: 07 set 2008, 19:54
da Haile
Stex19 ha scritto:Haile ha scritto:Stex19 ha scritto:io so che se ho un $ a_j=1 (mod4) $ allora avrò che $ 3a_j=3 (mod4) $, quindi $ a_{j+1} $ sarà pari.
però non so come dimostrare che prima o poi nella sucessione comparirà sicuramente un numero congruo a 1 mod4...
p.s. come si fa i lsegno di congruo in latex??
Non c'è nulla da dimostare...
Sia $ $a_0$ $ un dispari. Esso allora è di forma $ $4k+1$ $ o $ $4k+3$ $.
Se $ $a_0=4k+1$ $ allora
$ $a_1=\frac{3(4k+1)+1}{2} = 2(3k+1)$ $
che è pari, e l'algoritmo si ferma dopo 1 passaggio. A questo punto quindi suppongo tranquillamente che l'$ $n$ $ che si sceglie all'inizio sia di forma $ $4k+3$ $.
Comunque giunti a questo punto la dimostrazione dell'intero problema è tutt'altro che finita...
si... questo l'avevo capito...
volevo sapere se si riesce a dimostrare che esiste un n-esimo termine che è della forma 4k+1....
Hai ragione, non ho letto bene il tuo messaggio... tra l'altro è un po' che penso a questo problema e la tua domanda mi ha dato anche un nuovo spunto di riflessione
comunque per la congruenza:
$ $ a \equiv b \pmod n $ $