Algoritmo di Siracusa

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Algoritmo di Siracusa

Tratto da: David Wells - NUMERI MEMORABILI - Zanichelli - pag. 138

L'algoritmo di Siracusa inizia da un numero qualsiasi e poi lo divide per 2 se è pari, mentre invece lo moltiplica per 3 e vi somma 1 se è dispari. Il procedimento viene ripetuto.

Ecco la sequenza che comincia da 17:

17 --> 17*3+1=52 --> 52/2=26 --> 26/2=13 --> 13*3+1=40 --> 40/2=20 --> 20/2=10 --> 10/2=5 --> 5*3+1=16 --> 16/2=8 --> 8/2=4 --> 4/2=2 --> 2/2=1

STOP, altrimenti ripeterebbe la sequenza

4 --> 2 --> 1 --> 4 --> 2 --> 1 --> ...

all'infinito.

Tutti i numeri interi inferiori a 1.000.000.000 sono stati sottoposti a verifica e per tutti alla fine la sequenza termina con 4-2-1. Non è noto se tutti i numeri, alla fine, terminano con 1.

Soluzione

Se N è pari diventa N Div 2, se N è dispari diventa 3*N+1 e questo ripetuto mentre N <> 1.

while (N <> 1) do
   begin
      if(Odd(N)) then
         N:=3*N+1
      else
         N:=N Div 2;
      write(N:10)
   end;

Approfondimento

Alcuni numeri percorrono una "distanza" molto grande prima di giungere a 1, altri raggiungono valori molto "alti" prima di precipitare verso 1.

La sequenza

17 --> 52 --> 26 --> 13 --> 40 --> 20 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1

ha distanza = 12 e altezza = 52

La sequenza

167 --> ... --> 1

ha distanza = 67 e altezza =9232!

Applicazione MsDos e sorgente TurboPascal

Algoritmo di Siracusa - ApPuNtIdIuNiNfOrMaTiCo

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito