mercoledì 26 dicembre 2018

Un generatore di numeri primi

“Ehi, guarda, ho scoperto un generatore di numeri primi!”.

“Uhm”.

“Come uhm? Guarda:”.

P(n) = n2 + n + 41

“Uhm”.

“Ma insomma, cosa c'è che non va? P(0) fa 41, che è un numero primo”.

“Questo è vero”.

P(1) fa 43, che è ancora primo”.

“Vero anche questo”.

P(2) fa 47, P(3) fa 53, tutti primi”.

“Certo”.

“E posso andare avanti così, i numeri successivi sono 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033”.

“Molto bene”.

“Quindi sto generando numeri primi”.

“Sì, certo. Hai calcolato P(41)?”.

“Aspetta che faccio i calcoli”.

“Forse non hai bisogno di fare tutti i conti per dire se è primo o no”.

“Perché?”.

“Beh, stai sommando tre numeri: 412 + 41 + 41”.

“Oh”.

“Come vedi, 41 è un fattore comune a tutti e tre”.

“Uffa, risulta un numero composto”.

“Sì, 41 × 43. Prova anche a calcolare P(40)”.

“Questo sarà primo, dai”.

“Prova”.

“Allora: 402 + 40 + 41”.

“Che, volendo, puoi scrivere come 402 + 80 + 1”.

“E perché questa scrittura dovrebbe essere meglio?”.

“Perché è uguale a (40 + 1)2, cioè 412”.

“Oh, è composto anche questo”.

“Già”.

“Ma ci sarà un polinomio che funziona, no?”.

“Cioè un polinomio P(n) a coefficienti interi in una variabile n che assuma valori primi per ogni n intero positivo?”.

“Uh, mamma mia, che pignoleria. Sì, un polinomio fatto così”.

“Certo, eccotene uno: P(n) = 2”.

“Eh? Ma no, che genera numeri primi diversi!”.

“Allora lo vuoi anche non costante”.

“Sì! Quanto sono noiosi questi Veri Matematici”.

“Capisci che bisogna esser precisi, altrimenti poi non si sa bene quello che si vuole”.

“Va bene, va bene. Esiste un polinomio così?”.

“No”.

“Ma come? Tra tutti gli infiniti polinomi che si possono costruire, non ce n'è nemmeno uno che genera solo numeri primi?”.

“Nemmeno uno”.

“Santo cielo. E perché?”.

“Immagina che ne esista uno, per esempio uno che assuma il valore 43 quando n = 1”.

“Come fa il mio”.

“Esatto: possiamo scrivere che P(1) = 43”.

“Bene”.

“Ora prova a calcolare P(1 + 43k)”.

“Cos'è k?”.

“Un qualunque numero intero”.

“Eh, ma come faccio a calcolare P(1 + 43k) se non so come sia fatto P?”.

“Allora, partiamo dall'inizio. Supponiamo che esista P, che sarà scritto in maniera molto generica in questo modo:”.

P(n) = anxn + an−1xn−1 + … + a1x + a0

“Gulp”.

“Prova a calcolare, adesso, P(1 + 43k)”.

“Vediamo, risulterà una cosa del genere:”.

P(1 + 43k) = an(1 + 43k)n + an−1(1 + 43k)n−1 + … + a1(1 + 43k) + a0

“Bene. Comincia a svolgere”.

“Stai scherzando?”.

“No, ma non devi svolgere tutto tutto. Per esempio, da tutte quelle parentesi del tipo (1 + 43k) elevate a una qualche potenza puoi estrarre il primo termine, che è 1”.

“Eh, ma poi c'è un sacco di altra roba”.

“Certo, cominciamo dal facile: ognuna di quelle parentesi genera sicuramente un 1”.

“Va bene. Ognuno di quegli 1 viene moltiplicato per un coefficiente diverso”.

“E quindi puoi cominciare a scrivere una cosa del genere:”.

P(1 + 43k) = an + an−1 + … + a1 + a0 + (altra roba)

“Non mi sembra una scrittura molto matematica, però va bene”.

“Ti ricordi quanto faceva P(1)?”.

“Abbiamo detto 43”.

“E, però, se sostituisci 1 nel tuo generico polinomio cosa ottieni?”.

“Ah, facile, ottengo an + an−1 + … + a1 + a0”.

“Benissimo. Quindi sai che an + an−1 + … + a1 + a0 = 43”.

“Ah. Ma allora posso scrivere così:”.

P(1 + 43k) = 43 + (altra roba)

“Certo. Adesso concentriamoci sull'altra roba”.

“E come facciamo? Dobbiamo svolgere tutte quelle potenze di binomio, non si finisce più”.

“Non facciamolo. Sarai d'accordo con me se ti dico che lo sviluppo di qualunque potenza del tipo (1 + 43k)n contiene un termine uguale a 1, e tanti altri termini che contengono, almeno una volta, il fattore 43?”.

“Eh, sì, giusto. Tutti i termini dopo il primo 1 contengono le varie potenze di 43k. Non ricordo bene il calcolo dei coefficienti, però”.

“Beh, non importa ai fini dei calcoli che stiamo facendo. Senza conoscere nessuna regola, puoi immaginare di dover calcolare quella potenza in questo modo:”.

(1 + 43k)n = (1 + 43k)(1 + 43k) … (1 + 43k)

“Ah, certo”.

“Quando ti calcoli tutti i prodotti, vedi che c'è un solo caso in cui fai 1×1×…×1, mentre in tutti gli altri casi almeno un termine del tipo 43k lo devi prendere”.

“Giusto, e quindi un 43 c'è sempre”.

“Ottimo. Ed ecco allora che possiamo semplificare ulteriormente il calcolo che stavamo facendo, mettendo in evidenza il fattore comune 43:”.

P(1 + 43k) = 43 + 43(altra roba ancora)

“Bene, e quindi?”.

“E quindi P(1 + 43k) è divisibile per 43”.

“E allora?”.

“E allora non è primo, dunque P(n) non può assumere valori primi per ogni valore di n”.

“Ah!”.

“Volendo essere più precisi, bisognerebbe distinguere due casi nell'espressione P(1 + 43k) = 43 + 43(altra roba ancora)”.

“Quali?”.

“Se la parentesi (altra roba ancora) fosse uguale a 0, allora il risultato sarebbe 43, che è effettivamente un numero primo”.

“Allora potrebbe succedere?”.

“Eh, questo significherebbe che P(1 + 43k) dovrebbe essere uguale a 43 per infiniti valori di k”.

“E questo non è possibile?”.

“Lo è, ma un polinomio che assume infiniti valori uguali è un polinomio costante”.

“Ah, il caso banale P(n) = 43”.

“Già. Se vuoi un polinomio non costante e in grado di generare solo numeri primi, non ce la fai. Non esiste. Naturalmente 43 è solo un esempio, puoi rifare tutta la dimostrazione sostituendo, al posto di 43, un qualsiasi numero p primo. Quindi, niente da fare: non esiste un polinomio P(n) non costante a coefficienti interi in una variabile n che assuma valori primi per ogni n intero positivo”.

“Oh. Peccato”.

“Già”.

7 commenti:

Ida Maiellaro ha detto...

Simpaticissimo !!! 🤓
I nostri alunni potrebbero dire... elucubrazioni mentali... ma forse non sanno cosa significhi elucubrazioni 😵🤔

Riccardo Di Sipio ha detto...

Hai mai sentito parlare della croce dei numeri primi?
https://wp.me/p3Tmf-ol

zar ha detto...

Non l'avevo mai vista presentata in quel modo, ma dovrebbe essere una conseguenza del fatto che i numeri primi sono congrui a 1 o a -1 modulo 6

Anonimo ha detto...

Bello!
Ancora!
Mi piace, come argomento: i numeri primi sono allo stesso tempo semplicissimi da spiegare ma anche un mistero enorme della matematica.
La croce dei numeri primi sarebbe interessante se TUTTI i valori nella croce fossero primi, invece così com'è è solo la dimostrazione che - tolti 2 e 3 - nessuno primo è divisibile per 2 o 3. Tra l'altro, proprio per la presenza di 2 e 3 la croce non è una "vera" croce, ma appare come un pattern solo se ci si allontana abbastanza da non notare la "sbavatura".

zar ha detto...

Sarebbe *molto* interessante, così :-)

Unknown ha detto...

Più che un commento una domanda.
Quali e quante formule come quella di Eulero sono state create per generare delle sequenze di numeri primi più o meno lunghe ?

Io conosco quella attribuita Legrenge 2x*x+29 che genera 29 numeri primi e poi tutte le altre che iniziano con un numero primo diverse ma ottenute da quelle di Eulero.
Grazie per l'attenzione.
bbornago

zar ha detto...

Eh, questo non lo so, non so nemmeno che teoria ci stia dietro.