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

Minimali (numeri) (II)

Rappresentazione dei numeri 

Per spiegare cosa siano i numeri minimali servono due definizioni preliminari:

  • una stringa a si dice sottosequenza di un’altra b se tutti i caratteri di a compaiono in b nello stesso ordine, non necessariamente consecutivi (una definizione alternativa è che si può ricavare a da b cancellando alcuni caratteri); per esempio, 135 è sottosequenza di 1234567;

  • due stringhe sono comparabili se una è sottosequenza dell’altra.

 

Un risultato sorprendente della teoria dei linguaggi è che ogni insieme di stringhe non comparabili a coppie costruito su un alfabeto finito è finito (G. Higman, 1952 e L.H. Haines, 1969).

In un insieme di stringhe, finito o meno, si dicono minimali quelle che non contengono sottosequenze appartenenti all’insieme.

Dato che le stringhe minimali non sono comparabili a coppie, l’insieme di stringhe minimali è necessariamente finito.

In altri termini, un insieme anche infinito di stringhe contiene un insieme di stringhe minimali, almeno una delle quali è contenuta in ogni stringa dell’insieme di partenza: le stringhe minimali sono in un certo senso inevitabili all’interno delle stringhe dell’insieme di partenza.

 

Nel 1996 Jeffrey Shallit propose di considerare le stringhe che rappresentano i numeri primi in notazione decimale e determinò l’insieme di 26 stringhe minimali, che rappresentano i primi minimali: 2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049.

Un modo alternativo di definire questo insieme è: i primi tali che cancellando una qualsiasi combinazione di cifre non si ottengono mai numeri primi. Di conseguenza, a parte quelli di una sola cifra, sono costituiti esclusivamente da 0, 1 e cifre che rappresentano numeri composti.

 

L’idea è stata successivamente generalizzata a basi diverse da 10 e ad altre categorie di numeri: fissata la base, per qualunque insieme anche infinito di interi esiste un sottoinsieme minimale finito. In generale però trovare tale sottoinsieme non è un’impresa semplice, perché in linea di principio il problema è indecidibile, ossia non esiste un algoritmo valido in tutti i casi; in particolare bisogna determinare se esistano o meno numeri appartenenti alla categoria, che terminino con una sequenza fissata di cifre e questo può essere un compito molto gravoso. In casi specifici, come i numeri primi, si può arrivare a dimostrare che l’insieme di primi minimali trovato è completo, ma persino questo caso particolare è complicato. Per esempio, nel caso dei numeri primi in una base fissata, bisogna determinare il minimo primo pluriunitario in quella base o stabilire che non esiste, e può essere necessario esaminare numeri con moltissime cifre: in base 17 il massimo primo minimale noto ha 111334 cifre, che diventano 136991, se lo si rappresenta in base 10 e in base 19 il massimo primo minimale noto ha 110986 cifre, che diventano 141924, se lo si rappresenta in base 10.

 

Il numero primo 1235607889460606009419 è il minimo che possa essere trasformato in ciascun primo minimale con opportune cancellazioni di cifre (Andrew Rupinski).

 

In base 10 i primi minimali della forma 4n + 1 sono: 5, 13, 17, 29, 37, 41, 61, 73, 89, 97, 101, 109, 149, 181, 233, 277, 281, 349, 409, 433, 449, 677, 701, 709, 769, 821, 877, 881, 1669, 2221, 3001, 3121, 3169, 3221, 3301, 3833, 4969, 4993, 6469, 6833, 6949, 7121, 7477, 7949, 9001, 9049, 9221, 9649, 9833, 9901, 9949, 11969, 19121, 20021, 20201, 21121, 23021, 23201, 43669, 44777, 47777, 60493, 60649, 66749, 80833, 90121, 91121, 91921, 91969, 94693, 111121, 112121, 119921, 199921, 220301, 466369, 470077, 666493, 666649, 772721, 777221, 777781, 779981, 799921, 800333, 803333, 806033, 833033, 833633, 860333, 863633, 901169, 946369, 946669, 999169, 1111169, 1999969, 4007077, 4044077, 4400477, 4666693, 8000033, 8000633, 8006633, 8600633, 8660033, 8830033, 8863333, 8866633, 22000001, 40400077, 44040077, 60000049, 66000049, 66600049, 79999981, 80666633, 83333333, 86606633, 86666633, 88600033, 88883033, 88886033, 400000477, 400444477, 444000077, 444044477, 836666333, 866663333, 888803633, 888806333, 888880633, 888886333, 8888800033, 8888888033, 88888883333, 440444444477, 7777777777921, 8888888888333, 40000000000777, 44444444400077, 40444444444444477, 44444444444444477, 88888888888888633, 999999999999999121, 8888888888888888888888888888888888888888888888888888888888888888888888888888833 (Walter A. Kehowski e Curtis Bright).

 

In base 10 i primi minimali della forma 4n + 3 sono: 3, 7, 11, 19, 59, 251, 491, 499, 691, 991, 2099, 2699, 2999, 4051, 4451, 4651, 5051, 5651, 5851, 6299, 6451, 6551, 6899, 8291, 8699, 8951, 8999, 9551, 9851, 22091, 22291, 66851, 80051, 80651, 84551, 85451, 86851, 88651, 92899, 98299, 98899, 200891, 208891, 228299, 282299, 545551, 608851, 686051, 822299, 828899, 848851, 866051, 880091, 885551, 888091, 888451, 902299, 909299, 909899, 2000291, 2888299, 2888891, 8000099, 8000891, 8000899, 8028299, 8808299, 8808551, 8880551, 8888851, 9000451, 9000899, 9908099, 9980099, 9990899, 9998099, 9999299, 60000851, 60008651, 60086651, 60866651, 68666651, 80088299, 80555551, 80888299, 88808099, 88808899, 88880899, 90000299, 90080099, 222222899, 800888899, 808802899, 808880099, 808888099, 888800299, 888822899, 992222299, 2222288899, 8808888899, 8888800099, 8888888299, 8888888891, 48555555551, 555555555551, 999999999899, 88888888888099, 2228888888888899, 9222222222222299, 2288888888888888888888899, 888888888888888888888888888888888888888888899, 86666666666666666666666666666666666666666666666651 (Walter A. Kehowski e Curtis Bright).

 

In base 10 i primi palindromi minimali sono: 2, 3, 5, 7, 11, 919, 94049, 94649, 94849, 94949, 96469, 98689, 9809089, 9888889, 9889889, 9908099, 9980899, 9989899, 900808009, 906686609, 906989609, 908000809, 908444809, 908808809, 909848909, 960898069, 968999869, 988000889, 989040989, 996686699, 996989699, 999686999, 90689098609, 90899999809, 90999899909, 96099899069, 96600800669, 96609890669, 98000000089, 98844444889, 9009004009009, 9099094909909, 9600098900069, 9668000008669, 9699998999969, 9844444444489, 9899900099989, 9900004000099, 9900994990099, 900006898600009, 900904444409009, 966666989666669, 966668909866669, 966699989996669, 999090040090999, 999904444409999, 90000006860000009, 90000008480000009, 90000089998000009, 90999444444499909, 96000060806000069, 99900944444900999, 99990009490009999, 99999884448899999, 9000090994990900009, 9000094444444900009, 9666666080806666669, 9666666668666666669, 9909999994999999099, 9999444444444449999, 9999909994999099999, 9999990994990999999, 900000000080000000009, 900999994444499999009, 90000000009490000000009, 90909444444444444490909, 98999999444444499999989, 9904444444444444444444099, 999999999844444448999999999, 90944444444444444444444444909, 99999999999944444999999999999, 99999999999999499999999999999, 9999999999990004000999999999999, 900000000999999949999999000000009, 989999999999998444899999999999989, 9000000999999999994999999999990000009.

 

Il caso dei numeri composti è molto più semplice, perché un numero composto minimale in base b ha al massimo b + 2 cifre (Curtis Bright, Raymond Devillers, Jeffrey Shallit, 2015).

I numeri composti minimali in base 10 sono: 4, 6, 8, 9, 10, 12, 15, 20, 21, 22, 25, 27, 30, 32, 33, 35, 50, 51, 52, 55, 57, 70 72, 75, 77, 111, 117, 171, 371, 711, 713, 731 4, 6, 8, 9, 10, 12, 15, 20, 21, 22, 25, 27, 30, 32, 33, 35, 50, 51, 52, 55, 57, 70 72, 75, 77, 111, 117, 171, 371, 711, 713, 731. Escludendo quelli di una sola cifra, questi devono contenere solo cifre che siano numeri primi, 0 o 1.

 

Gli interi minimali in base 10 sono: 1, 2, 3, 4, 5, 6, 7, 8, 9; in generale in base b sono gli interi da 1 a b – 1.

 

I quadrati maggiori di zero minimali noti in base 10 sono: 1, 4, 9, 25, 36, 576, 676, 7056, 80656, 665856, 2027776, 2802276, 22282727076, 77770707876, 78807087076, 7888885568656, 8782782707776, 72822772707876, 555006880085056, 782280288087076, 827702888070276, 888288787822276, 2282820800707876, 7880082008070276, 80077778877070276, 88778000807227876, 782828878078078276, 872727072820287876; potrebbero essercene altri, maggiori di 1018 (M. Fiorentini, 2017).

 

I cubi maggiori di zero minimali in base 10 minori di 109 sono: 1, 8, 27, 64, 343, 729, 3375, 4096, 35937, 39304, 46656, 50653, 79507, 97336, 300763, 405224, 456533, 474552, 493039, 636056, 704969, 3307949, 4330747, 5545233, 5639752, 5735339, 6539203, 9663597, 23393656, 23639903, 29503629, 37933056, 40353607, 45499293, 50243409, 54439939, 57066625, 57960603, 70444997, 70957944, 73560059, 76765625, 95443993, 202262003, 236029032, 350402625, 377933067, 379503424, 445943744, 454756609, 537367797, 549353259, 563559976, 567663552, 773620632, 907039232; ve ne sono probabilmente altri, maggiori di 109 (M. Fiorentini, 2017).

Qui trovate i cubi maggiori di zero minimali in base 10 minori di 1018 (M. Fiorentini, 2017).

 

I biquadrati maggiori di zero minimali in base 10 minori di 109 sono: 1, 256, 625, 4096, 20736, 65536, 456976, 4477456, 8503056, 9834496, 59969536, 78074896, 84934656, 303595776, 362673936, 688747536.

Qui trovate i biquadrati maggiori di zero minimali in base 10 minori di 1018 (M. Fiorentini, 2017).

 

Le potenze maggiori di zero minimali in base 10 sono: 1, 4, 8, 9, 25, 27, 32, 36, 576, 676, 3375, 7056, 7776, 50653, 20226200; se ce ne sono altre, sono maggiori di 1018 (M. Fiorentini, 2017).

 

Shallit congetturò che i numeri di Fibonacci minimali siano: 1, 2, 3, 5, 8, ossia che ogni numero di Fibonacci contenga una di queste cifre. Sfortunatamente non basta un semplice esame di poche cifre finali, periodiche, per verificare la congettura; per esempio, F98 = 135301852344706746049 termina con 11 cifre finali diverse da queste.

 

Shallit congetturò che le potenze di 2 minimali siano: 1, 2, 4, 8, 65536. Per dimostrare la congettura, bisognerebbe dimostrare che ogni potenza di 2 con esponente maggiore di 16 contiene una delle cifre 1, 2, 4 o 8, come tutti gli esperti ritengono.

Bibliografia

  • Shallit, Jeffrey;  "Minimal primes" in Journal of Recreational Mathematics, n. 30:2 (1999 – 2000) pag. 113 – 117.

Contattami

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