Alla caccia dei numeri primi lunghi
Ho preso spunto da questa pagina di un sito a me sinora ignoto che credo si chiami polimath. In quella pagina c'è un esercizio già risolto:
Un numero n si chiama primo lungo se il periodo di 1/n è di n-1 cifre. Trova i primi lunghi minori di 100.
Risposta: 7 17 19 23 29 47 59 61 97
Ovverosia:
1 / 7 = 0,142857...
1 / 17 = 0,0588235294117647...
1 / 19 = 0,052631578947368421...
(non so come inserire la sbarra sopra in HTML; comunque sia sono tutti numeri periodici semplici)
Mi sono chiesto: e quelli dopo il 100?
Ho scritto allora un programmino in ANSI C che sfrutta principalemte la forza bruta del computer e l'ho lasciato andare per qualche ora. Il programmino è talmente brutale che mi dovrei vergognare nel pubblicarlo. Per i curiosi ed i critici il codice è, ad ogni modo, il seguente:
#include <stdio.h>
#include <limits.h>
#define MAXIMUM INT_MAX
#define Lunghezza 23
// per esplorare i numeri ad una e due cifre porre MAXIMUM = 99 e Lunghezza = 1
// per esplorare i numeri piu' grandi porre MAXIMUM = INT_MAX e Lunghezza = 23
char map[MAXIMUM]; // spazio di lavoro
const int Lista[] = { 3, 5, 7, 11, 13, 17, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97
}; // lista dei numeri primi < 100 e ≠ 2
int PrimoLungo( int n ) // ritorna 1 solo se n e' un primo lungo
{
int i, m = 1, t;
for (i = 0; i < n; i++)
map[i] = 0;
for (i = 0; i < n; i++) // i conta quanti resti diversi fra loro vengono
{ // prodotti durante la divisione in colonna
m *= 10;
t = m / n;
m -= t * n; // resto della divisione
if (map[m]) break; // resto ripetuto
map[m] = 1; // memorizza il resto
}
return i == n - 1;
}
int main(int argc, const char * argv[])
{
int i, j;
printf("sto iniziando \n");
for (i = Lista[Lunghezza-1] + 2; i <= MAXIMUM; i += 2)
{
for (j = 0; j < Lunghezza; j++)
{
int t = i / Lista[j];
if (Lista[j] * t == i)
break; // questo stratagemma scarta i multipli di 3, 5, 7, 11 ecc.
}
if (j == Lunghezza && PrimoLungo( i ))
printf("%d\n", i);
}
return 0;
}
Dopo qualche ora il mio vecchio iMac aveva calcolato i primi 135.123 numeri primi lunghi. La lista richiede un Mb, pertanto l'ho salvata in un file a parte.
A questo punto mi mancava da fare una cosa: eseguire una divisione che generasse un periodo da record (ossia con almeno un milione di cifre che non si ripetano). Ho scelto dalla lista precedente il primo numero a 7 cifre. Questo era dunque il divisore. Come dividendo, al posto di 1, ho preferito un numero qualsiasi a 6 cifre, in modo tale da evitare troppi zeri all'inizio. Per eseguire i calcoli mi sono avvalso di un altro programmino:
#include <stdio.h>
int divisore = 1000171; // deve essere un primo lungo
int dividendo = 456789; // deve essere < divisore
int main(int argc, const char * argv[])
{
int i, t;
printf("%d / %d = 0,", dividendo, divisore );
for (i = 1; i < divisore; i++)
{
dividendo *= 10;
t = dividendo / divisore;
printf( "%d", t );
dividendo -= t * divisore;
}
printf( " periodico \n" );
return 0;
}
Anche questa volta é uscito fuori un file da 1 Mb che sono orgoglioso di pubblicare. Non capita tutti i giorni di calcolare un numero periodico del genere!