La congettura di Collatz

La congettura di Collatz, detta anche congettura di Syracuse, o congettura 3n+1, è tanto facile da enunciare quanto difficile da dimostrare, essa infatti non è mai stata provata, anche se i matematici la ritengono vera. La sua enunciazione è semplice: dato un qualsiasi numero intero positivo n: - se n è pari lo si divida per 2, - se n è dispari lo si moltiplichi per 3, e gli si aggiunga 1, - e si ripetano le operazioni sul numero ricavato. La congettura di Collatz dice che qualunque sia il numero di partenza si arriva sempre al ciclo finale 4, 2, 1. Ad esempio, partendo dal numero 7: 7→ 22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1 La successione di numeri ottenuta a partire da n viene detta "volo", il numero di passaggi per arrivare da n a 1 è detto "durata del volo" (nel nostro esempio la "durata del volo" è stata 16), il numero più alto raggiunto è detta "altezza massima del volo" (nel nostro esempio, 52). Ricorrendo all'aiuto dei computer, la congettura di Collatz è stata finora verificata valida fino al numero 3,2 x 1016 (a meno che questo record non sia già stato battuto). La verifica al computer ha iniziato dai numeri più bassi a salire, tenendo presenti alcune scorciatoie: - se durante la verifica del numero n si arriva ad un numero che gli è inferiore il calcolo può essere arrestato, in quanto tutti i numeri inferiori ad n sono già stati verificati, - tutti i numeri pari possono essere scartati, perché alla prima operazione diventano inferiori a n, - tutti i numeri del tipo n=4k+1 possono essere scartati, perché diventano 12k+4, quindi 6k+2 e 3k+1, sicuramente inferiore a n, - tutti i numeri del tipo n=4k+2 possono essere scartati, perché diventano 2k+1, minori di n. - Quindi, devono essere verificati soltanto i numeri del tipo n=4k+3. Può stupire il fatto che questi calcoli, alla fine, portino al risultato finale 1. Il ragionamento (errato) che si fa è il seguente: essendoci tanti numeri pari quanti dispari, in media una volta su due il numero dovrebbe essere dimezzato, e l'altra triplicato; il valore allora dovrebbe crescere ogni volta in media di 3/2 e tendere quindi all'infinito. Ma questo ragionamento, come abbiamo detto, è sbagliato. Infatti, se partiamo da un numero pari la prima volta esso sicuramente diminuisce, se invece partiamo da un numero dispari al primo passaggio si ottiene 3n+1, che è ancora pari. Al secondo passaggio si ottiene (3n+1)/2, che ha il 50% di probabilità di essere dispari, il 25% di essere il doppio di un numero dispari, il 12,5% di essere il quadruplo di un numero dispari, e così via. Quindi, in media un numero dispari ha probabilità 1/2 di essere moltiplicato per 3/2, 1/4 di essere moltiplicato per 3/4, 1/8 di essere moltiplicato per 3/8, e così via. Cioè, in media, tra un numero dispari e il successivo dispari il numero viene moltiplicato per 3/21/2, 3/41/4,3/81/8…, il cui prodotto è 3/4, quindi il numero diminuisce mediamente del 75%. Si è cercato di affrontare il problema partendo dalla fine anziché dall'inizio, e cioè: iniziando dal numero 1, ed eseguendo le operazioni inverse (cioè, raddoppiandolo oppure sottraendogli 1 e moltiplicandolo per 3), si toccano tutti i numeri? Purtroppo, neanche questo metodo fornisce risultati. Infatti, dopo pochi passaggi le alternative possibili diventano talmente sconfinate da essere ingestibili (ad esempio, arrivati al numero 16, occorre raddoppiarlo ottenendo 32 oppure sottrargli 1 e dividerlo per 3, ottenendo 5? E 64 proviene da 128 oppure da 21?) Risulta invece ovvio che, se la congettura di Collatz è vera, eseguendo i calcoli all'incontrario e scegliendo tutte le alternative possibili il calcolo deve toccare qualsiasi numero naturale.

k=1,2,3,...

I. n!=1.

n=2k => collatz(n): n/2 = 2k/2 = k HALF n. [n->k]

n=(2k+1) => collatz(n): 3(2k+1)+1 = 6k+3+1 = 6k+4 = 2(3k+2) = n'

             collatz(n'):  n'/2 = 2(3k+2)/2 = 3k+2   
           1).6k'+2=2(3k'+1)  collatz=> 3k'+1 = collatz(k')   k'<k<n.
           2).3(2k'+1)+2=6k'+5=6(k'-1)   collatz=> 3(k'-1)=3k/2 => 1.5k

collatz(1.5k)<collatz(2k+1)

 II. n=1.

collatz(n): 3n+1=4 = n'

  collatz(n'):  n'/2 = 2 =n"
     collatz(n"):  n"/2 = 1 = n
           INFINITE CICLE RETURN OLWAYS 1.

Ho compilato i sorgenti in C proposti nella pagina. Per quanto riguarda quello ricorsivo, consiglio la rimozione dell'inutile chiamata alla funzione getch(), per altro compatibile solamente con sistemi Windows. Se necessario potrebbe essere sostituita con getchar(), che funziona anche in sistemi UNIX.

Ho notato inoltre che, usando il primo codice proposto, molti numeri non terminano l'algoritmo, che prosegue usando numeri negativi. Si puo` provare, per esempio, con 113383. Il programma continuera` senza raggiungere mai l'uno. E` ovviamente un bug del codice C: la versione Perl funziona benissimo...

Se nessuno si oppone, provvedero` io alla cancellazione della chiamata a getch(). Per quanto riguarda invece il bug, non capisco da cosa possa essere provocato... --Mghis (msg) 21:22, 24 mag 2011 (CEST)[rispondi]

Il codice ricorsivo in linguaggio Gambas è il seguente:

Private Procedure Collatz(n As Integer)

  Print n
 
  If n > 1
    If Even(n) = False Then
      collatz((3 * n) + 1)
    Else
      collatz(n / 2)
    Endif
  Endif
  
End

--Samnispentrorum (msg) 01:06, 1 mar 2015 (CET)[rispondi]

non vorrei peccare di arroganza , ciò che ho scritto è corretto oppure non va bene ? Samdepss (msg) 02:59, 21 ott 2022 (CEST)[rispondi]

la congettura è vera perché i numeri sono infiniti e si raggiungerà sempre un multiplo di 2 . come citato per fare calcoli così lunghi sono necessari computer di ultima generazione .

Ho riunito in una sola discussione i due interventi. A cosa ti riferisci? L'affermazione precedente matematicamente non ha molto senso. Inoltre ti ricordo che è vietato pubblicare risultati originali su wikipedia, quindi se ritieni di avere una dimostrazione per la congettura devi inviarla a una rivista di matematica specializzata.--Mat4free (msg) 18:53, 22 ott 2022 (CEST)[rispondi]

Ho notato che tra le denominazioni alternative in incipit compare "numeri di Hailstone", presente sin dalla prima versione delle pagina, risalente al 2004 e proveniente da enwiki. La cosa mi puzza abbastanza: il nome inglese "hailstone numbers" deriva dal fatto che le sequenze numeriche oscillino su e giù anche con notevole ampiezza, analogamente ai chicchi di grandine (hailstones) dentro alle nuvole. Non esiste nessun signor Hailstone. Mi è preso il forte sospetto che ci sia sotto una traduzione ingenua dall'inglese, e da una rapida ricerca su google non sembra un'idea peregrina: pochissime occorrenze di "numeri di Hailstone", quasi tutte provenienti da questa pagina (cosa non sorprendente, visto che appunto la denominazione è qui dal 2004). Da una parte sarei tentato di cancellare direttamente la denominazione in oggetto, ma dato che nel caso la boiata sarebbe rimasta qui per un ventennio, direi che posso prendermi il tempo di chiedere se qualcuno ha riscontri della denominazione "numeri di Hailstone" nella letteratura in italiano. --Daimona Eaytoy (Scrivimi!) 23:20, 10 mar 2024 (CET)[rispondi]

Sembrerebbe che sia proprio così, qui nel 1984 li chiamavano "hailstone numbers" con la minuscola. Potremmo fare una breve spiegazione del termine come su en.wiki. --ArtAttack (msg) 00:28, 11 mar 2024 (CET)[rispondi]

In effetti una breve spiegazione ci starebbe, precisando comunque che la denominazione è esclusiva alla lingua inglese (a quanto pare). --Daimona Eaytoy (Scrivimi!) 16:42, 11 mar 2024 (CET)[rispondi]