algoritmo

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

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

[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??

[Haile]

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

[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??

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

[Haile]

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:

Codice: Seleziona tutto

$a \congr b \pmod n$

$ $ a \equiv b \pmod n $ $