Problema del 3n+1
Esiste un curioso problema della teoria del numeri che può essere formulato come segue:
“Si scelga un qualsiasi Intero positivo $N$.
Se $N$ è dispari lo si moltiplica per 3 e si somma 1, ossia si ottiene 3N+1.
Se $N$ è pari lo si divide per 2, ossia si ottiene N/2.
In entrambi i casi il risultato è il nuovo valore di $N$, e si ripete la procedura.”
e' facile verificare che la serie converge fino a 1.
Quello che io chiedo è:è possibile calcolare quanti passagi compie $n$ prima di ridursi ad uno?
Faccio notare che questo non è strettamente legato alla grandezza di un numero:
27 compie 111 passaggi, 100 ne compie 25.
“Si scelga un qualsiasi Intero positivo $N$.
Se $N$ è dispari lo si moltiplica per 3 e si somma 1, ossia si ottiene 3N+1.
Se $N$ è pari lo si divide per 2, ossia si ottiene N/2.
In entrambi i casi il risultato è il nuovo valore di $N$, e si ripete la procedura.”
e' facile verificare che la serie converge fino a 1.
Quello che io chiedo è:è possibile calcolare quanti passagi compie $n$ prima di ridursi ad uno?
Faccio notare che questo non è strettamente legato alla grandezza di un numero:
27 compie 111 passaggi, 100 ne compie 25.
Risposte
"blackdie":
Esiste un curioso problema della teoria del numeri che può essere formulato come segue:
Come disse Erdos: "Noi siamo ancora pronti per questi problemi..."
Ciao, ciao!
"carlo23":
Come disse Erdos: "Noi siamo ancora pronti per questi problemi..."
Scherzi a parte, credo che sia un problema che vada affrontato con il concetto di macchina di Turing, cioè algoritmizzazione (spero si scriva così!)
perchè va affrontato in quel modo?
se non sbaglio lo disse riferito all'ultimo teorema di fermat
Come disse Erdos: "Non siamo ancora pronti per questi problemi..."
se non sbaglio lo disse riferito all'ultimo teorema di fermat
"blackdie":
perchè va affrontato in quel modo?
Come disse Erdos: "Non siamo ancora pronti per questi problemi..."
se non sbaglio lo disse riferito all'ultimo teorema di fermat
A me non sembrava per Fermat, ma forse mi sono confuso...
Andrebbe affrontato in quel modo a mio parere, infatti esistono molti problemi simili, problemi computazionali che chiedono se il valore di una funzione è determinabile in modo polinomiale, esponenziale o meno...
Un problema famoso affrontato anche da Achille Serra in questo articolo, pubblicato nella sezione "Teoria dei Numeri" del nostro sito.
Il link: https://www.matematicamente.it/numeri/3n+1.pdf
Il link: https://www.matematicamente.it/numeri/3n+1.pdf
A me non sembrava per Fermat, ma forse mi sono confuso...
La notte porta consiglio:erdos disse precisamente "La matematica non è ancora pronta per questi problemi" proprio riferito a questo problema, detto di Collatz.
"blackdie":
Esiste un curioso problema della teoria del numeri che può essere formulato come segue:
“Si scelga un qualsiasi Intero positivo $N$.
Se $N$ è dispari lo si moltiplica per 3 e si somma 1, ossia si ottiene 3N+1.
Se $N$ è pari lo si divide per 2, ossia si ottiene N/2.
In entrambi i casi il risultato è il nuovo valore di $N$, e si ripete la procedura.”
e' facile verificare che la serie converge fino a 1.
Sfortunatamente non è così semplice determinarne la convergenza... infatti molti degli studi di ricerca di teoria dei numeri cercano la convergenza.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo