Numeri primi fattoriali

Numeri primi fattoriali, merce rara!
È semplice raccontare cosa sono: si parte dal fattoriale di un numero (es.: 6! = 1 × 2 × 3 × 4 × 5 × 6 = 720) e si aggiunge o si sottrae 1 (continuando con l’esempio: 720 – 1 = 719, 720 + 1 = 721). Se il risultato è un numero primo, allora il numero è un  primo fattoriale.
Nel caso dell’esempio, 719 è primo, mentre 721 è un numero composto, il cui primo fattore è  7 (721 = 103 × 7).
La procedura per generarli è intuitiva: si calcola il fattoriale dei numeri naturali, si aggiunge o si sottrae 1 e si verifica se il risultato è o meno un numero primo.

Il problema è tutto nell’ultimo passaggio, perché il fattoriale cresce rapidamente e il tempo per analizzarne la primalità cresce con velocità ancora maggiore. Se, poi, si desidera conoscerne la scomposizione in fattori primi (nel caso che non sia primo), allora la complessità aumenta ulteriormente.
È un campo di enorme interesse scientifico, oltre che pratico. La sicurezza delle transazioni bancarie, ad esempio, si basa proprio nella difficoltà di scomporre in fattori primi un numero, prodotto di due primi sufficientemente grandi.
Rimanendo nella matematica del liceo, giochiamo un po’ con i fattoriali primi della forma n! + 1.

Un semplice algoritmo di fattorizzazione

In rete si trovano diverse implementazioni di algoritmi di scomposizione in fattori primi, basati sulla divisione del numero da fattorizzare con i possibili candidati. Un esempio in Python si trova su Wikipedia:

def is_prime(n: int) -> bool:
    """Primality test using 6k+-1 optimization."""
    if n <= 3: return n > 1
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i ** 2 <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

L’algoritmo si basa su due ottimizzazioni:

  1. se il numero da testare è composto, allora il suo più piccolo fattore non può essere maggiore della radice quadrata del numero stesso:
    • while i ** 2 <= n:
  2. se si escludono 2 e 3, i restanti numeri primi devono essere della forma 6i + 1, oppure della forma 6i – 1 (equivalente a 6i + 5):
    • gli altri casi possibili, infatti, sono multipli di 2 o di 3, o di entrambi (6i + 0, 6i +2, 6i + 3, 6i + 4).

Il nostro algoritmo può partire da qui.

Esiste una proprietà dei numeri primi gemelli che deriva direttamente dal fatto che ogni primo diverso da 2 e 3 è della forma 6i – 1 oppure 6i + 1. Infatti due numeri primi gemelli, P1 e P2, essendo numeri dispari consecutivi e primi, devono essere della forma rispettivamente (6i -1) e (6i + 1). Ne segue che il loro prodotto sarà della forma 36i2 – 1.
Da  P1 × P2 = 36i2 – 1 segue che P1 × P2 + 1 = (6i)2.
Quindi il prodotto di due numeri primi gemelli, aumentato di 1, è un quadrato perfetto.

Due piccole modifiche all’algoritmo di scomposizione in fattori primi

Sono stati ideati test di primalità molto sofisticati e di notevole efficienza. Volendo però limitare lo sforzo di comprensione e di programmazione, ho impiegato un semplice algoritmo di ricerca esaustiva dei fattori primi.
Devo quindi accettare che, al crescere dei numeri analizzati, non determino precisamente se un numero è primo, ma solo se è un possibile candidato alla primalità. In questo modo evito che, al primo numero primo abbastanza grande, il programma praticamente si blocchi.

Ho anche modificato il codice in modo da restituire non un valore booleano (Vero/Falso), ma un valore numerico: il primo fattore incontrato, nel caso di numero composto, il numero stesso, quando è primo, il valore 0 (zero) nel caso di uscita dall’algoritmo senza aver verificato se il numero è composto o primo.

Il codice che segue riporta l’algoritmo e la procedura di ricerca dei numeri primi fattoriali con numero di partenza da 2 a 120.

def prime(n):
    max_try = 10**8
    if n <= 3:
        return n
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    i = 5
    while (i * i <= n) and (i < max_try):
        if n % i == 0:
            return i
        if n % (i + 2) == 0:
            return i + 2
        i += 6
    if i < max_try:
        return n
    else:
        return 0
#
max_n = 120
fatt = 1
tipo = 1
for n in range(2,max_n+1):
    fatt *= n
    esito = prime(fatt+tipo)
    if esito == fatt+tipo:
        print (n, ",", fatt+tipo, ", primo")
    elif esito == 0:
        print (n, ",", fatt+tipo, ", ???")    
    else:
        print(n, ",", fatt+tipo, ",",esito)

Le regolazioni del codice

Il funzionamento del codice può essere regolato, modificando alcune impostazioni:

  • max_try = 10**8, fissa a 108 il massimo fattore per il quale si prova la divisibilità; il tempo di elaborazione rimane ragionevole, mentre occorrerebbe aumentare di ordini di grandezza per trovare qualche fattore in più;
  • max_n = 120, fissa a 120 il massimo valore di n che si testa come generatore di primi fattoriali;
  • tipo = 1, per esplorare i primi fattoriali della forma n! + 1; se, invece, si pone tipo = -1, allora si esplora la forma n! – 1.

L’output del codice

Il codice produce un output come riportato di seguito:

  • numero;
  • fattoriale;
  • esito [“primo” | un fattore (se non è primo) | “???” (se potenziale primo)].

Il formato è del tipo csv, comodo per importare i dati in un foglio elettronico (LibreOffice Calc o Excel).

2 , 3 , primo
3 , 7 , primo
4 , 25 , 5
5 , 121 , 11
6 , 721 , 7
7 , 5041 , 71
8 , 40321 , 61
9 , 362881 , 19
10 , 3628801 , 11
11 , 39916801 , primo
12 , 479001601 , 13
13 , 6227020801 , 83
14 , 87178291201 , 23
15 , 1307674368001 , 59
16 , 20922789888001 , 17
17 , 355687428096001 , 661
18 , 6402373705728001 , 19
19 , 121645100408832001 , 71
20 , 2432902008176640001 , 20639383
21 , 51090942171709440001 , 43
22 , 1124000727777607680001 , 23
23 , 25852016738884976640001 , 47
24 , 620448401733239439360001 , 811
25 , 15511210043330985984000001 , 401
26 , 403291461126605635584000001 , 1697
27 , 10888869450418352160768000001 , ???
28 , 304888344611713860501504000001 , 29
...
120 , 66895029134491270575881180540903725867527463331380298102956713523
      01633557244962989366874165271984981308157637893214090552534408589408121
      859898481114389650005964960521256960000000000000000000000000001 , 12149

Come si vede, i fattoriali crescono rapidamente, da qui la necessità, se si utilizza un algoritmo semplice, di limitare la profondità di ricerca dei fattori per tentativi. I numeri primi fattoriali trovati da questo programma sono i primi tre: 3, 7 e 39916801.

Il teorema di Wilson!

Scorrendo l’output si nota una curiosa ricorrenza:

...
4 , 25 , 5
...
6 , 721 , 7
...
10 , 3628801 , 11
...
12 , 479001601 , 13
...
16 , 20922789888001 , 17
...
18 , 6402373705728001 , 19
...
22 , 1124000727777607680001 , 23
...
28 , 304888344611713860501504000001 , 29

Nella terza colonna (primo fattore del numero composto n! + 1) compare la progressione dei numeri primi (5, 7, 11, 13, …) in corrispondenza del numero appena inferiore (4, 6, 10, 12, …).
Sembra, cioè, valere la relazione: p primo => p divide (p-1)! + 1.
Un modo alternativo di esprimere questa relazione è la seguente che utilizza l’aritmetica modulare: p primo => (p-1)! ≡ – 1 (mod p).

Ebbene, non è una sorpresa, ma la manifestazione del Teorema di Wilson, che stabilisce questa relazione per tutti i numeri primi, e come condizione non solo necessaria (se p è primo, allora …), ma anche sufficiente (se (p-1)! ≡ – 1 (mod p), allora p è primo).

Un teorema che apparentemente fornisce un potente utensile per trovare numeri primi, ma che in realtà è inutilizzabile per la complessità di calcolo, al crescere dei numeri analizzati. Basti pensare che, per verificare la primalità di 29 occorre dividere il numero 304888344611713860501504000001 per 29.

E adesso?

Le sequenza di numeri primi fattoriali sono sull’enciclopedia on line delle sequenze di numeri interi. Più precisamente si trovano la sequenza del tipo n! + 1 e quella del tipo n! – 1, con ben maggiore profondità di analisi di quella ottenuta con questo esercizio di programmazione. Un’analisi esaustiva, fino a 100! +1, si trova qui.
Ma, come sempre, il viaggio è spesso più interessante della destinazione. Il risultato ottenuto è modesto, mi sono computazionalmente arreso di fronte alla fattorizzazione di 27! + 1 (10.888.869.450.418.352.160.768.000.001) e ho trovato solo tre numeri primi fattoriali. Mi sono dato però una ripassata a un campo della teoria dei numeri, quello dell’analisi dei numeri primi, ricco di spunti di interesse e riflessione, oltre che un punto di partenza ideale per esplorazioni affascinanti.

Esempio: tra i numeri della forma n! + 1, per n da 2 a 120, ho trovato ben 6 valori che hanno 71 come divisore, in corrispondenza di: 7, 19, 51, 61, 63, 70. Da questo punto in poi non potranno esserci più fattoriali aumentati di 1 che abbiano 71 come divisore.
Da notare che, escluso 71, altri fattori sono presenti 3 volte o meno. È un fatto statisticamente insignificante o 71 ha qualcosa di speciale? Esistono fattori primi presenti più di 6 volte?

Varrebbe la pena di estendere la ricerca, abbassando il valore del max_try ed aumentando quello del max_n. Occorre poi modificare il codice, per stampare solo le ricorrenze risolte, che avranno tutte un fattore minore di max_try. Ci saranno altri primatisti?

Articoli correlati:

Scritto da:

Pasquale

Mi chiamo Pasquale Petrosino, radici campane, da alcuni anni sulle rive del lago di Lecco, dopo aver lungamente vissuto a Ivrea.
Ho attraversato 40 anni di tecnologia informatica, da quando progettavo hardware maneggiando i primi microprocessori, la memoria si misurava in kByte, e Ethernet era una novità fresca fresca, fino alla comparsa ed esplosione di Internet.
Tre passioni: la Tecnologia, la Matematica per diletto e le mie tre donne: la piccola Luna, Orsella e Valentina.
Potete contattarmi scrivendo a: p.petrosino@inchiostrovirtuale.it