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!

 

torna alla pagina iniziale

 

Copyright © 2017 prof. Giuseppe Balacco
Valid XHTML and CSS. UTF-8 encoding.