Don't take life too seriously: it's just a temporary situation

Sierpiński (numeri di) (II)

Teoria dei numeri 

Si chiamano “numeri di Sierpiński”, o più precisamente “numeri di Sierpiński del secondo tipo”, gli interi positivi dispari k tali che k2n + 1 sia composto per qualsiasi valore intero positivo di n.

 

Nel 1960 Wacław Franciszek Sierpiński (Varsavia, 14/3/1882 – Varsavia, 21/10/1969) dimostrò che esistono infiniti numeri con questa proprietà; in particolare dimostrò che k è un numero di Sierpiński se è dispari e dà resto 1 se diviso per 646(232 – 1) e 6700416 se diviso per 6700417, cioè se k ha la forma 36893488147419103230m + 15511380746462593381.

 

I numeri di Sierpiński noti inferiori a 106 sono: 78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431.

Si conoscono 6707470 numeri di Sierpiński inferiori a 1013.

Qui trovate i numeri di Sierpiński noti inferiori a 109 (T. D. Noe e Arkadiusz Wesolowski, The Online Encyclopedia of Integer Sequences http://oeis.org).

 

Un problema aperto è se 78557 sia effettivamente il minimo numero di Sierpiński, come lo stesso Sierpiński e Selfridge supposero nel 1967. Il lavoro di molti matematici (e di moltissimi calcolatori) ha permesso di escludere quasi tutti i numeri inferiori. Per dimostrare che un numero k non è di Sierpiński bisogna trovare un valore di n tale che k2n + 1 sia primo e questo può comportare l’esame di milioni di numeri di enormi dimensioni.

Nel 1996 rimanevano 35 candidati, ridotti a 17 nel 2002. Nel marzo di quell’anno K. Helm e D. A. Norris lanciarono un’iniziativa in rete, sollecitando volontari a concedere l’uso di tempo di calcolo altrimenti inutilizzato. Uno alla volta tutti gli interi inferiori a 78557 sono stati esclusi (v. numeri di Colbert), tranne 6 candidati: 10223, 21181, 22699, 24737, 55459 e 67607, per tutti i quali sono stati esaminati gli esponenti sino a oltre 17 milioni senza trovare numeri primi.

 

Nel 2016 una ricerca distribuita in rete ha scoperto che 10223 • 231172165 + 1 è primo; restano quindi da escludere 5 candidati.

 

E’ possibile dimostrare che un intero k è un numero di Sierpiński trovando un insieme di primi tali che si possa dimostrare che ogni intero della forma k2n + 1 è divisibile per almeno uno di essi.

Per esempio, John Selfridge dimostrò nel 1962 che 78557 è un numero di Sierpiński perché 78557 • 2n + 1 è sempre divisibile per almeno uno dei numeri 3, 5, 7, 13, 19, 37 o 73.

Per ogni insieme del genere si ottiene una progressione aritmetica infinita di numeri di Sierpiński.

Ognuno di tali insiemi permette anche di dimostrare che un intero (in generale diverso) è un numero di Riesel.

 

La tabella seguente riporta gli insiemi corrispondenti ad alcuni numeri di Sierpiński.

Numero

Insieme

78557

{ 3, 5, 7, 13, 19, 37, 73 }

271129

{ 3, 5, 7, 13, 17, 241 }

271577

{ 3, 5, 7, 13, 17, 241 }

322523

{ 3, 5, 7, 13, 37, 73, 109 }

327739

{ 3, 5, 7, 13, 17, 97, 257}

482719

{ 3, 5, 7, 13, 17, 241 }

575041

{ 3, 5, 7, 13, 17, 241 }

603713

{ 3, 5, 7, 13, 17, 241 }

903983

{ 3, 5, 7, 13, 17, 241 }

934909

{ 3, 5, 7, 13, 19, 73, 109 }

965431

{ 3, 5, 7, 13, 17, 241 }

1259779

{ 3, 5, 7, 13, 19, 73, 109 }

1290677

{ 3, 5, 7, 13, 19, 37, 109 }

1518781

{ 3, 5, 7, 13, 17, 241 }

1624097

{ 3, 5, 7, 13, 17, 241 }

1639459

{ 3, 5, 7, 13, 17, 241 }

1777613

{ 3, 5, 7, 13, 17, 19, 109, 433 }

2131043

{ 3, 5, 7, 13, 17, 241 }

11822359

{ 3, 5, 7, 13, 19, 73, 109 }

12756019

{ 3, 5, 7, 13, 19, 37, 73 }

37158601

{ 3, 5, 13, 17, 97, 241, 257 }

41134369

{ 3, 5, 7, 13, 17, 97, 673 }

57816799

{ 3, 5, 7, 13, 37, 73, 109 }

359292259

{ 3, 5, 13, 17, 97, 241, 673 }

425780911

{ 3, 5, 7, 13, 17, 257, 673 }

478078081

{ 3, 5, 7, 17, 97, 257, 673 }

597875869

{ 3, 5, 7, 17, 97, 241, 257 }

764612281

{ 3, 5, 7, 13, 97, 241, 257 }

879092101

{ 3, 5, 7, 13, 97, 241, 673 }

919128377

{ 3, 5, 13, 17, 97, 257, 673 }

1269436171

{ 3, 5, 7, 17, 97, 241, 673 }

4046512609

{ 3, 5, 7, 13, 241, 257, 673 }

5112582467

{ 3, 5, 7, 17, 241, 257, 673 }

7354973911

{ 3, 5, 7, 11, 13, 31, 61, 151, 331 }

7791902033

{ 3, 5, 7, 11, 13, 31, 41, 61, 151 }

11801652413

{ 3, 5, 7, 11, 13, 31, 41, 151, 331 }

12298364659

{ 3, 5, 13, 17, 241, 257, 673 }

23246795491

{ 3, 5, 7, 11, 13, 31, 41, 61, 331 }

36090391531

{ 3, 5, 7, 11, 13, 41, 61, 151, 331 }

39803042693

{ 3, 5, 17, 97, 241, 257, 673 }

45299429363

{ 3, 5, 7, 11, 13, 31, 41, 61, 1321 }

59150216933

{ 3, 5, 7, 11, 13, 31, 41, 151, 1321 }

191976083123

{ 3, 5, 7, 13, 31, 41, 61, 151, 1321 }

193636884083

{ 3, 5, 7, 11, 13, 61, 151, 331, 1321 }

204575287201

{ 3, 5, 7, 11, 13, 31, 61, 151, 1321 }

228919237553

{ 3, 5, 7, 13, 31, 41, 61, 151, 331 }

243698810449

{ 3, 5, 7, 11, 13, 31, 151, 331, 1321 }

311005640147

{ 3, 5, 7, 11, 13, 31, 41, 331, 1321 }

368666816041

{ 3, 5, 7, 11, 13, 41, 61, 151, 1321 }

596688750227

{ 3, 5, 7, 11, 13, 31, 61, 331, 1321 }

983548147697

{ 3, 5, 7, 11, 13, 41, 61, 331, 1321 }

1722422320457

{ 3, 5, 7, 11, 13, 41, 151, 331, 1321 }

1996943298451

{ 3, 5, 7, 13, 31, 41, 61, 331, 1321 }

3201918268463

{ 3, 5, 7, 13, 41, 61, 151, 331, 1321 }

3281241306713

{ 3, 5, 7, 13, 31, 61, 151, 331, 1321 }

3958265274739

{ 3, 5, 7, 13, 31, 41, 151, 331, 1321 }

10019542331573

{ 3, 5, 7, 11, 31, 41, 61, 151, 331, 1321 }

150870306352861

{ 3, 5, 11, 13, 31, 41, 61, 151, 331, 1321 }

15511380746462593381

{ 3, 5, 17, 257, 641, 65537, 6700417 }

1934207927446756722099

{ 5, 7, 11, 13, 17, 19, 31, 37, 41, 61, 73, 109, 151, 241, 331 }

1139634035240881514319907179

{ 5, 7, 11, 13, 17, 19, 31, 41, 61, 73, 97, 109, 151, 181, 241, 331, 673 }

4423988484893019254861842753686117

{ 5, 7, 11, 13, 17, 19, 31, 37, 41, 61, 73, 97, 109, 151, 181, 241, 257, 331, 673 }

29043303653060659151044147354251952120530050059153153041

{ 3, 5, 17, 257, 641, 65537, 6700417 }

 

In altri casi si dimostra che un numero è un numero di Sierpiński trovando un insieme di primi che dividano k2n + 1 per alcuni valori di n e una scomposizione per i restanti. Per esempio:

  • 4008735125781478102999926000625 = 447457554 è un numero di Sierpiński perché l’insieme { 3, 17, 97, 241, 257, 673 } garantisce la divisibilità, se n non è della forma 4m + 2, mentre in tal caso 4004365181040050 • 22m + 89491510 • 2m + 1 divide k2n + 1; lo stesso vale per tutti i numeri della forma (44745755 + 412417548294m)4 (Michael Filaseta, Carrie Finch e Mark Kozek, 2007);

  • 290433036530614504024730081259407069229771426966923250390625 = 7341106150007754 è un numero di Sierpiński perché l’insieme { 3, 17, 257, 641, 65537, 6700417 } garantisce la divisibilità, se n non è della forma 4m + 2, mentre in tal caso 1077836790113632192906501201250 • 22m + 1468221230001550 • 2m + 1 divide k2n + 1 (Anatoly S. Izotov, 1993).

Secondo alcuni matematici potrebbe non esistere un insieme finito di primi che permetta di dimostrare che numeri di questo genere sono numeri di Sierpiński, senza ricorrere a scomposizioni come quelle mostrate.

In pratica per alcuni numeri di Sierpiński l’insieme di primi necessario potrebbe essere infinito, contrariamente all’opinione espressa da Erdös. Una possibilità intermedia è che l’insieme possa essere infinito solo per i numeri di Sierpiński che sono potenze.

 

Erdös avanzò la congettura che se k è un numero di Sierpiński, il minimo divisore primo di k2n + 1 sia limitato per ogni valore di n, tuttavia A.S. Izotov nel 1995 avanzò dubbi sulla congettura, esaminando il caso di 734110615000774, perché il minimo fattore primo sembra crescere senza limiti. E’ possibile che la congettura di Erdös valga solo per i numeri di Sierpiński che non sono potenze.

 

Si può dimostrare che, fissato k, esiste un valore di n tale che 2n + 1 sia divisibile per tutti i numeri primi minori di k e di conseguenza al crescere di n il minimo fattore primo di 3 • 2n + 1, che non ha fattori primi comuni con 2n + 1, cresce senza limiti. Non è però stato stabilito se lo stesso valga per 5 • 2n + 1 e più in generale per sequenze come k • 2n + 1, per un valore dispari fissato di k maggiore di 3.

 

Nel 1979 Erdös e Odlyzko dimostrarono che esistono infiniti interi non di Sierpiński (v. numeri di Proth).

 

G. Jaeschke dimostrò nel 1983 che per ogni intero positivo r esistono infiniti valori di k per i quali r è il minimo valore per il quale k2r + 1 sia primo.

 

Y.-G. Chen avanzò nel 2003 la congettura che per ogni intero positivo r esistano infiniti valori di k tali che kr2n + 1 abbia almeno due fattori primi distinti per ogni valore di n; lo stesso Chen dimostrò che la congettura vale se r è dispari o il doppio di un numero dispari non multiplo di 3.

 

Michael Filaseta, Carrie Finch e Mark Kozek dimostrarono nel 2007 che per ogni intero r esistono infiniti interi k, tali che non solo le loro potenze k, k2, k3, … kr siano numeri di Sierpiński, ma che per ogni intero positivo n i numeri k2n + 1, k22n + 1, k32n + 1, …, kr2n + 1 abbiano almeno due fattori primi distinti.

I tre matematici dimostrarono anche che se esistono almeno r numeri di Fermat composti, esistono infiniti numeri dispari k tali che se t è un intero positivo non multiplo di 2r, kt è un numero di Sierpiński. Al momento sappiamo che r vale almeno 230, ma l’opinione corrente è che i numeri di Fermat composti siano infiniti.

 

Per quasi mezzo secolo sono stati conosciuti solo numeri di Sierpiński multipli di 3; l’opinione prevalente era che esistessero anche numeri di Sierpiński non multipli di 3, ma che fossero enormi. Infatti nel 2004 Wilfrid Keller dimostrò che 4423988484893019254861842753686117 è un numero di Sierpiński non multiplo di 3, grazie all’insieme { 5, 7, 11, 13, 17, 19, 31, 37, 41, 61, 73, 97, 109, 151, 181, 241, 257, 331, 673 }, e che la stessa proprietà vale per tutti i numeri della forma 4423988484893019254861842753686117 + 8098504028425981183736114374652670m.

Si aprì quindi la caccia al minimo numero del genere e sempre nel 2004 Thomas Masser dimostrò che 1139634035240881514319907179 ha la stessa proprietà, grazie all’insieme { 5, 7, 11, 13, 17, 19, 31, 41, 61, 73, 97, 109, 151, 181, 241, 331, 673 }, e poco dopo lo stesso Masser trovò 5785418219844359742627, dimostrato grazie all’insieme { 5, 7, 11, 13, 17, 19, 31, 37, 41, 61, 73, 109, 151, 241, 331 }. Arkadiusz Wesolowski migliorò nel 2010 il record con 1934207927446756722099, dimostrato grazie all’insieme { 5, 7, 11, 13, 17, 19, 31, 37, 41, 61, 73, 109, 151, 241, 331 }.

Da ogni numero k0 del genere si ricava una progressione aritmetica infinita di interi con la stessa proprietà, della forma k0 + 6Pm, dove P è il prodotto dei primi dell’insieme che permette di dimostrarne la proprietà.

 

E’ stato dimostrato che esistono infiniti numeri di Sierpiński primi; il minimo noto è 271129 (Nathan Mendelsohn, 1976); è in corso una vasta ricerca per escludere i 10 candidati inferiori rimasti: 22699, 67607, 79309, 79817, 152267, 156511, 168451, 222113, 225931 e 237019, per i quali sono stati esaminati gli esponenti sino a oltre 17 milioni senza trovare numeri primi.

Per dimostrare che 271129 è anche il secondo numero di Sierpiński restano anche da escludere 11 candidati composti: 91549, 99739, 131179, 163187, 193997, 200749, 202705, 209611, 227723, 229673 e 238411, per i quali sono stati esaminati gli esponenti sino a oltre 6870000 senza trovare numeri primi.

 

I numeri di Sierpiński primi noti inferiori a 107 sono: 271129, 322523, 327739, 482719, 934909, 1639459, 2131043, 2131099, 2576089, 3098059, 3608251, 4573999, 6678713, 6799831, 7523281, 7761437, 8184977, 8840599, 8879993, 8959163, 9208337, 9252323, 9930469, 9937637.

Qui trovate i numeri di Sierpiński primi noti inferiori a 109 (Ant KIng e Arkadiusz Wesolowski, The Online Encyclopedia of Integer Sequences http://oeis.org).

 

Nel 2003 Y.-G. Chen avanzò la congettura che per ogni intero positivo r esistano infiniti interi k tali che kr2n + 1 abbia almeno due fattori primi distinti per ogni valore di n.

Lo stesso Chen dimostrò la congettura per r dispari e per r della forma 2m, conms dispari e non multiplo di 3; nel 2007 Michael Filaseta, Carrie Finch e Mark Kozekchen dimostrarono che la congettura è vera per qualsiasi valore di r.

 

Esistono infiniti numeri che sono sia numeri di Riesel, sia numeri di Sierpiński, detti “numeri di Brier”.

 

Florian Luca e V.J. Mejía Huguet dimostrarono nel 2008 che vi sono infiniti numeri di Sierpiński tra i numeri di Fibonacci.

Daniel Baczkowski, Olaolu Fasoranti e Carrie E. Finch dimostrarono che vi sono infiniti numeri di Sierpiński tra i numeri di Lucas (I) e più precisamente Lk è un numero di Sierpiński se k diviso 55716312432816 dà resto 3563460609625, 5304045945961, 6380599390361, 6495898106089, 8121184726697, 8236483442425, 9313036886825, 9839994939145, 11053622223161, 11580580275481, 12657133719881, 12772432435609, 14397719056217, 14513017771945, 15589571216345, 17330156552681, 27462447337913, 29203032674249, 30394884834377, 32135470170713, 33738981667433, 35479567003769, 36671419163897, 38197925094889, 38412004500233, 39938510431225, 41130362591353, 42870947927689, 44474459424409, 46215044760745, 47406896920873 o 49147482257209.

 

Se si utilizzano interi gaussiani, è stato dimostrato che per k uguale a 10 + 3i, 25 + 3i e 40 + 3i non si hanno primi per nessun valore di n.

 

Dimostrazioni analoghe valgono anche per particolari categorie di primi: per infiniti valori di k, (k2n – 1, k2n + 1) non costituiscono mai una coppia di primi gemelli e (k2n – 1, k2n + 1 – 1) non costituiscono mai una coppia di primi di Sophie Germain.

Per la prima categoria Wilfid Keller trovò i seguenti valori di k:

  • 237, dimostrabile grazie all’insieme { 5, 7, 13, 17, 241 };

  • 807, dimostrabile grazie all’insieme { 5, 7, 13, 19, 37, 73 };

  • 4851, dimostrabile grazie all’insieme { 5, 7, 13, 17, 241 }.

Per dimostrare che 237 è il minimo intero con questa proprietà restano da escludere 111, 123, 153, 159, 171, 183, 189, 219 e 225, per i quali non sono state trovate coppie di primi gemelli per n fino a 140000.

I numeri noti con la stessa proprietà sono: 237, 807, 4581, 32469, 41091, 60981, 62637, 63351, 76593, 80979, 84387, 85047, 92343, 93621, 96891, 102183, 113679, 123609, 130629, 139647, 140571, 158883, 171837, 172857, 177201, 178401, 184251, 205347, 207243, 212547, 217011, 219291, 220851, 238779, 250401 (Arkadiusz Wesolowski The Online Encyclopedia of Integer Sequences http://oeis.org).

Per la seconda categoria il minimo valore di k noto è 807, dimostrabile sempre grazie all’insieme { 5, 7, 13, 19, 37, 73 }; per dimostrare che è il minimo restano da escludere: 39, 183, 213, 219, 273, 279, 333, 351, 387, 393, 399, 417, 429, 471, 531, 543, 561, 567, 573, 591, 597, 603, 639, 681, 687, 693, 699, 723, 753, 759, 771 e 795.

Il minimo intero noto appartenente a entrambe le categorie è 807 e resta da escludere solo 183.

 

Non esistono invece interi k tali che n2k + 1 sia primo per ogni valore di n, né tali che 2k + n sia primo per ogni valore di n, perché se p è un primo che divide n + 1, per k = p – 1, n2k + 1 e 2k + n sono multiplo di p.

 

Il minimo numero di Sierpiński palindromo noto è 196818691 il minimo numero di Sierpiński primo palindromo noto è 375656573.

Bibliografia

  • Klamkin, Murray S.;  USA Mathematical Olympiads 1972 – 1986, Washington, The Mathematical Association of America, 1988 -

    Raccolta di problemi stimolanti, alla portata di studenti delle medie superiori.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.