Indice articoli

Valutazione attuale: 5 / 5

Stella attivaStella attivaStella attivaStella attivaStella attiva
 
Collatz Conjecture




Congettura di Collatz

 

 

 

La procedura:

si prende un numero intero qualunque. Se è pari lo si divide per 2, se è dispari lo si moltiplica per 3 e si aggiunge 1. Al numero risultante si applica lo stesso ragionamento e il tutto termina quando si ottiene 1.

Un esempio:
X = 5
5 è dispari -> 3x + 1
1. 5 * 3 + 1 = 16 (pari -> x/2)
2. 16 / 2 = 8 (pari)
3. 8 / 2 = 4
4. 4 / 2 = 2
5. 2 / 2 = 1

stopping time = 5

Come si può notare tutta la procedura si basa sulla probabilità di incontrare, durante le iterazioni, una potenza di 2 (nell'esempio 16 = 2^4) che viene rapidamente ridotta a 1.

È lecito pensare che più X è grande, maggiore sarà lo stopping time. Questo è vero nella maggior parte dei casi, anche se ad esempio 27 necessita di oltre 111 iterazioni per completare il processo.
È anche lecito credere che prima o poi tutti i numeri convergano a 1.

In figura sono rappresentati tutti i valori dello "stopping time" per i numeri interi da 1 a 9999.

 

Per approfondimenti:

Congettura di Collatz su Wikipedia

 


Accedi per commentare

Articoli

Written on 17/01/2022, 14:43 by boboviz
rosetta-e-virtualboxDa un po' di tempo il progetto Rosetta@Home sembra aver decisamente puntato sull’applicativo VirtualBox (Phyton), lasciando spesso vuote le code per gli...

Ultime dal Blog

Written on 03/08/2021, 22:27 by boboviz
foldit-e-alphafoldLa "svolta" AlphaFold è una delle più importanti degli ultimi anni, motivo per cui ho deciso di tradurre l'articolo che parla della sua implementazione in...