Problema del 3n+1
Uno strano scherzo dei numeri naturali o un importante segreto non ancora scoperto?
Introduzione a questo
problema, per chi non lo conosce- I numeri dispari non sono tutti uguali: il
modesto frutto di tanti pomeriggi trascorsi studiando questo problema
- Altre
domande e altri link su questo problema.
- Altrimenti potete sempre
tornare alla mia HomePage
Introduzione
Il problema del 3n+1 e' piuttosto antico: una formulazione possibile č la seguente.
Sia n un qualunque numero naturale (ovvero intero positivo, come 1,2,3...). Si costruisca la seguente successione
a1 = n; a(k) = a(k-1)/2 se a(k-1) e' pari mentre a(k) = 3*a(k-1) + 1 se a(k-1) e' dispari.
Allora la a(k) e' definitivamente uguale ad 1.
Piu' semplicemente preso un qualunque numero se e' pari lo si divide per due, se e' dispari lo si moltiplica per tre e si aggiunge uno. Si ripete il procedimento con il numero ottenuto. Si nota che dopo un numero finito di passaggi (in genere piuttosto basso anche se il numero e' piuttosto alto) si arriva ad 1 e poiche' 1 e' dispari e 1*3 +1 = 4 -> 4/2 = 2 -> 2/2 = 1 la successione si ferma sul valore di 1 (si dice infatti che una successione ha una proprieta' definitivamente se ha questa proprieta' tolto al piu' i primi n valori: ad esempio -1 0 -34 12 1 1/2 1/3 1/4 1/5 ... 1/(n-5) .... si dice che e' definitivamente decrescente (infatti e' vero a partire dal 5^ elemento). Nel nostro esempio tolti i primi numeri diversi da uno, tutti gli altri elementi della successione saranno uguali ad 1; e' un modo come un altro per dire che si arriva ad uno dopo un numero finito di passaggi).
Per esempio considerando il 13
13 
40 20
10 5 16 8 4 2 1 1 1 1 1 ...
considerando il 19 e limitandosi ai soli numeri dispari si ha:
19 
29 11 17 13 5 1
Provate un po' con il 95 e con il 12345 per convincervi che e' molto difficile, a partite dal numero, quante iterazioni si devono effettuare per arrivare ad 1 (in questo caso ne servono piu' per il 95)
I numeri dispari non sono tutti uguali
Rispetto a questo problema i numeri dispari sono tutt'altro che uguali. Infatti consideriamo un numero dispari, allora questo "genera" un numero pari (dopo che e' stato moltiplicato per 3 ed aggiunto 1). Questo numero pari come tale sara' senz'altro divisibile per 2, ma forse lo possiamo dividere per 4 o forse per 8 o anche per 1024 prima di ottenere un nuovo numero dispari.
Ad esempio considerate tutti quei numeri dispari scrivibile come 3+4*k con k numero naturale.
Avremo che (3+4*k)*3 = 9 + 12*k e quindi (3 + 4*k)*3 + 1 = 10 + 12*k. Questo numero puo' essere diviso solo per 2 ed avremo 5 + 6*k.
Magari pensate di riapplicare a 5 +6*k questo procedimento: otterrete 16+18*k che puo' essere diviso anche per 16 o forse solo per 2, dipende da k.
Chiamiamo numeri di classe dispari con n= 0 quelli scrivibili come 3 + 4*k. Sono infatti divisibili per 2^1 dopo l'iterazione (1 = 2*0 +1)
Consideriamo adesso quelli divisibili per 2^(2n+1), ovvero per potenze dispari di due. In genere un numero sara' "divisibile" per 2^(2n+1) se e solo se e' scrivibile come
(4^n * 10 - 1)/3 + 2^(2n + 2)*k con k naturale. Infatti se moltiplichiamo questa espressione per 3 e aggiungiamo 1 si ha
4^n*10 + 3k*2^(2n + 2) = 2^(2n+1)*5 + 6*k*2^(2n+1) = 2^(2n+1) * (5 + 6*k)
Tutti i numeri della classe dispari si riducono ad un numero che puo' essere scritto come 5 + 6*k
Consideriamo adesso quelli "divisibili" per 2^(2n), ovvero per 4^n che sono le potenza pari del 2. Saranno quelli e solo quelli scrivibili come:
(4^n -1)/3 + 2^(2n +1)*k con k naturale. Infatti moltiplicando per 3 ed aggiungendo 1 si ha:
4^n + 6*k*4^n per cui dividendo si ha 1+6*k
Tutti i numeri della classe pari si riducono ad un numero che puo' essere scritto come 1+ 6*k
Notiamo che se n= 0 l'espressione precedente si riduce a 2*k.
Quindi attraverso uno ed un solo k ed uno ed un solo n numeri naturali o uguali a zero si puo' scrivere ogni numero naturale (e lo zero) attraverso una delle due espressioni (di facile dimostrazione).
Alcuni esempi:
- i numeri pari si ottengono dalla seconda espressione con n = 0 e k = n/2
- la classe 3+ 4*k si ottiene dalla prima espressione con n= 0
- il 12345 appartiene alla classe pari con n = 0 e k = 1543 (ed infatti si riduce a 1 + 6*1543, come 790101 che e' della classe pari con n = 4 e k = 1543)
Tutto cio' servira' a risolvere questo problema? Chissa'...
Ho titolato questo paragrafo "I numeri dispari non sono tutti uguali" e c'e' anche un altro motivo: un'altra possibile divisione che puo' essere fatta dei numeri dispari e' secondo il numero di passaggi richiesti per arrivare ad 1, senza contare i passaggi attraverso i numeri pari: ad esempio il 5 fa parte del gruppo 1, il 13 del 2.... Si constata che il penultimo numero prima dell'uno e' quasi sempre il 5 (???) e non ad esempio il 21 (che e' sempre del gruppo 1). Cosi' anche nel gruppo 2 si trovano dei numeri favoriti, come se esistesse una linea "privilegiata". Mah...
Qualche interessante domanda e qualche link
Dopo aver analizzato questo problema non ci si puņ non chiedere:
- Esistono altre espressioni del tipo a*n +b con a e b naturali per cui si hanno risultati simili a quelli del 3*n + 1 (sempre che questa successione finisca sempre sull'uno per ogni numero reale.)
- Se esistono quali sono? C'e' una relazione tra loro? Se non esistono perche' e' unica: quale proprieta' dei numeri naturali abbiamo toccato?
Risolvere questo problema forse non servira' a nulla, ma chissa': non si puo' mai dire.
Finisco con qualche indirizzo utile per chi volesse sul serio approfondire l'argomento:
Altrimenti potete tornare alla mia HomePage o se volete potete come sempre scrivermi