Una congettura è una affermazione ritenuta probabilmente vera ma non ancora dimostrata. Una vota dimostrata la sua validità diviene un teorema. La Congettura di Goldbach è uno dei problemi più vecchi non ancora risolti, infatti risale al 1742, fu enunciata da Goldbach e riformulata da Euler nel seguente modo:

Ogni numero naturale pari maggiore di 2 puo' esere scritto come la somma di due numeri primi.

Ad esempio: 4 = 2 + 2 6 = 3 + 3 8 = 3 + 5 10 = 3 + 7 = 5 + 5 12 = 5 + 7 14 = 3 + 11 = 7 + 7 16 = 3 + 13 = 5 + 11

Proviamo a dimostrare la sua inesattezza

Su una congettura possiamo effettuare due tipo di dimostrazioni, possiamo dimostrare la sua correttezza o la sua inesattezza. Ovviamente l'una esclude l'altra. Tenteremo di dimostrare che la congettura è falsa, per fare ciò basta trovare un controesempio tele che l'enunciato risulti falso. Quindi nel nostro caso basta trovare un solo numero pari che non è la somma di due primi. Per trovare questo numero scriveremo un programma.

Alcune considerazioni

Tutti i numeri primi sono dispari ad eccezione di 2. Questo è vero per la definizione di numero dispari. Il numero primo 2 sommato ad un qualsiasi altro numero primo da come risultato un numero dispari. L'unico caso per cui 2 sommato ad un altro numero primo abbia come risultato un numero pari è 2 + 2. Da questo si deduce che il 4 è l'unico numero pari che si può scrivere come somma del numero primo 2 con un altro numero primo. Nel programma si considerano i numeri primi senza il 2 e tutti i numeri pari maggiori di quattro.

Scomponiamo il problema in sotto problemi

Le azioni che compie il programma possono schematizarsi in una succesioni di fasi distinte:

1. Trovare tutti i numeri primi da 3 ad n
2. Prendere tutte le coppie di numeri primi (p1, p2) tali che la loro somma non superi n (cioè p1 + p2 <= n) e se viene considerato (p1, p2) allora verrà scartato (p2, p1).
3. Marcare i pari da 6 ad n se essi sono il risultato di p1 + p2 per ogni coppia (p1, p2) trovata precedentemente.
4. Stampare tutti i numeri pari non marcati come somma di numeri primi.

Crivello di Eratostene

Per torvare tutti i numeri primi da 3 ad n esiste un metodo antichissimo noto come Crivello di Eratostene. Esso consiste nello scrivere tutti i numeri da 2 a n e cancellare successivamente tutti i multipli di 2(escluso), tutti i multipli di 3(escluso), tutti i multipli di 5(escluso) e così via. I numeri "sopravvissuti" saranno tutti e soli i numeri primi compresi tra 2 ed n.

Quindi utilizziamo un vettore di flag v, l'idea e' semplice, dobbiamo marcare tutti i numeri multipli di 2, 3, 5, ecc.. così i rimanenti sono primi. Per economizzare la memoria ho fatto partire il vettore da 3 ed esaminato solo i numeri dispari, esempio:

indice vettore(i): 0 1 2 3 4 5 6 informazione (j): 3 5 7 9 11 13 15 v[i] : T T T F T T F

per passare da i a j utilizzo la funzione j = 2*i + 3 viceversa i = (j - 3)/2 Nota: j - 3 da sempre un numero divisibile per due dato che i j sono tutti dispari.

void riempi_v(long int n) { int i, k; for (i = 0; i < Size(n); i++) { if (v[i] == TRUE) for (k = 3; (2*i + 3)*k < n + 2; k = k + 2) v[(2*i*k + 3*k - 3)/2] = FALSE; } }

Algoritmo di backtracking

Una volta ottenuto il vettore v sò quali sono i numeri primi fino ad n. Ora dovrò trovare tutte le coppie (p1, p2). Per fare questo utilizzo un algoritmo che sfrutta il metodo del backtracking. L'algoritmo "pota" l'albero delle ricorsioni in modo da non considerare affatto le coppie di numeri che non interessano. Così da essere il più ottimizzato possibile, ci accorgeremo che l'ottimizzazione di questo programma è fondamentale se vogliamo raggiungere buoni risultati.

/* trova e somma tutte le coppie di numeri primi trovati precedentemente */ void backtraking(long int n, int i, int p1, int p2) { int x; if (i == 2) { pari[(p1+p2)/2] = FALSE; /* printf("(%d,%d)\n",p1, p2); */ } else { if (i == 0) for (x = 3; x != -1; x = primo_successivo(n, x)) { backtraking(n, i + 1, x, p2); } else /** * Inizializzare x con p1 per verificare la congettura di Goldback. * Porre x = primo_successivo(n, p1) per trovare tutti i pari * dati da p1 + p2 con p1 != p2 */ for (x = p1; x != -1; x = primo_successivo(n, x)) { if (p1 + x <= n) backtraking(n, i + 1, p1, x); else break; } } }

Trovata la coppia (p1, p2) fa la somma e aggiorna il vettore pari. Il vettore pari ha dimensione n/2, ogni elemento corrisponde ad un numero pari.

Abbiamo sviluppato i punti 1, 2 e 3 del nostro problema, non ci resta che scorre il vettore dei pari e stampare solo l'indice in presenza di un numero pari che non è la somma di due primi.

for(i = 0; i < n/2; i++) if (pari[i] == TRUE) printf("%d:i = %d\n", pari[i], 2*i);

Risultati

Vi accorgerete effettaundo dei tests che all'aumentare di n aumenta anche il tempo di esecuzione. Con un computer ad un processore Intel da 5336.88 bogomips ho impiegato 5 giorni con n uguale a 100'000'000.

La congettura di Goldbach si suppone sia vera dal fatto che la probabilità per un numero pari di essere somma di due primi cresce al crescere del numero. Esiste un progetto di calcolo distribuito che ha finora verificato la congettura fino a 2 * 1017 (nel momento in cui scrivo.)

Un'altra congettura

Non voglio paragonarmi ad Euler o Goldbach ma forse troverete interessante anche quest'altra congettura che mi è passta per la mente durante la stesura del programma in questione. È un affinamento dell'enunciato di Goldbach.

Tutti i numeri naturali maggiori di 6 e pari possono essere scritti come somma di due primi p1 e p2 tali che p1 è diverso da p2

A voi la dimostrazione. Posso dirvi con certezza che fino a 108 risulta vera.