La sequenza 3n + 1¶

Questa sequenza ha affascinato i matematici per molti anni. La regola per creare la sequenza è la seguente:

cominciamo con un dato numero n, e
per generare il successivo della sequenza da n:
- dimezziamo n, se n è pari,
- altrimenti moltiplichiamo per tre e aggiungiamo 1.
La sequenza termina quando n raggiunge 1.

La seguente funzione Python implemente questo algoritmo.

def seq3np1(n):
    """ Print the 3n+1 sequence from n, terminating when it reaches 1."""
    while n != 1:
        print(n)
        if n % 2 == 0:        # n is even
            n = n // 2
        else:                 # n is odd
            n = n * 3 + 1
    print(n)                  # the last print is 1

seq3np1(3)

(ch07_indef1)

Dal momento che n qualche volta aumenta e qualche volta diminuisce, non c’è una dimostrazione ovvia che n raggiungerà 1, ovvero che il programma termina.
Per particolare valori di n, possiamo dimostrare la terminazione.
Per esempio, se il valore di partenza fosse pari, allora il valore di n sarebbe sempre pari e verrebbe dimezzato ogni volta fino a raggiungere 1.

La domanda interessante riguarda la possibilità di dimostrare che questa sequenza termina per tutti i valori di n. Fino adesso, nessuno è stato in grado di dimostrarlo o dimostrare il contrario!

Con il computer siamo stati in grado di dimostrare che la sequenza converge a 1 fino a valori molto alti, provandoli uno per uno. Ma potrebbe esistere un numero gigantesco per cui ancora non abbiamo fatto le prove per cui questo non vale.

E’ possibile notare che se non ci fermiamo quando raggiungiamo 1, possiamo ottenere un ciclo: 1, 4, 2, 1, 4, 2, 1, 4, and so on. Potrebbe esistere un numero per cui avviene un ciclo prima che si raggiunga 1.

Scegliere tra for e while

E’ preferibile usare un ciclo for se conosciamo il massimo numero di volte che abbiamo bisogno di eseguirlo. Per esempio, se stiamo attraversando i valori di una lista ottenuta con range.

Invece, se dobbiamo ripetere il corpo fino a che incontriamo una certa condizione, come abbiamo visto nel caso del problema 3n + 1, avremo bisogno di un ciclo while.

Next Section - Il Metodo di Newton