Visualizza il feed RSS

Titolo provvisorio...

La rivolta delle sette sette delle sette

Valutazione: 3 voti, con una media del 5.00.
di pubblicato il 26-03-2009 alle 01:57 (5356 Visite)
Prendo in prestito volentieri dal geniale Achille Campanile il titolo di questa entry, che mi è stata ispirata da un recente commento/recensione del nostro bottomap.

Si parla di numeri ciclici, argomento purtroppo non sempre affrontato nei licei. Ai miei tempi vi si accennava normalmente già al biennio, assieme ad altri numeri notevoli.
In breve, si tratta di numeri interi positivi che possiedono alcune interessanti proprietà:

- Sono generati da un numero primo, secondo la formuletta:

Formula LaTeX: C_b(p)=\frac{b^{p-1}-1}{p}
ove b è la base numerica prescelta e p è il numero primo dato, che non sia un divisore della base. Ovviamente non ogni numero primo genera un numero ciclico !

- Sono caratterizzati dall'essere sempre espressi con p - 1 cifre, il che spiega la loro strettissima correlazione con la rappresentazione e quindi la base numerica prescelta;

- Quando moltiplicati per il proprio primo generatore, danno come risultato una sequenza di cifre identiche, tutte pari a b - 1;

- Se moltiplicati per altri interi, presentano invece sempre esattamente le medesime cifre del valore di partenza, ma in un diverso ordine.

Il più noto di questi numeri, in base dieci, è 142857, generato appunto dal numero sette (da cui il titolo !). Si tratta anche del più piccolo numero ciclico in tale base.

Formula LaTeX: \mathrm{\begin{align*}142857 \cdot 1 &= 142857\\142857 \cdot 2 &= 285714\\ 142857 \cdot 3 &= 428571\\ 142857 \cdot 4 &= 571428\\ 142857 \cdot 5 &= 714285\\ 142857 \cdot 6 &= 857142\\ 142857 \cdot 7 &= 999999 \end{align*}}

Ma non basta. Spezziamo il numero in due parti uguali, e scriviamole adeguatamente incolonnate:

Formula LaTeX: \\142\\857

Cosa si nota ? Sommando le cifre in posizione corrispondente, si ottiene sempre 9: 1 + 8 = 4 + 5 = 2 + 7 = 9.

Ciò vale anche per tutti i multipli, eccetto ovviamente quelli caratteristici dati dal primo generatore e suoi multipli!

Non male, vero ?

Questi numeri possiedono ulteriori rilevanti proprietà, alle quali non vorrei però dedicare qui troppo spazio. Rimando invece alla picobibliografia che fornisco in calce, come anche alle varie e qualificate fonti che hanno a più riprese trattato l'argomento.

Quanto a noi, il sano divertimento per quest'oggi consiste nell'utilizzare - oltre al fido ed eccellente, nonché gratuito, BCC - una famosa libreria per il calcolo intero a precisione arbitraria, MIRACL (gratuita, dotata di sorgenti e di libero utilizzo per fini non commerciali) per fare un po' di number crunching casalingo.

Che ne direste se facessimo tirar fuori al nostro veloce stupidone da scrivania un po' di numeri ciclici... in base due, per poi osservarli con tutta calma?

Il cinquantesimo di codesti "numeretti" richiede 660 bit (ovvero 21 qword a 32 bit !) per essere espresso. Più in generale, dal diciottesimo numero binario ciclico in poi la dimensione è proibitiva per un trattamento con i tipi di default e gli strumenti standard dei linguaggi tradizionali, anche sulla più potente delle attuali workstation a 64 bit.

EDIT: Python potrebbe farlo senza battere ciglio, invece: ed ecco come !

#!/usr/local/bin/python
 
##
## Tabella dei numeri primi inferiori a 1000: viene utilizzata per verificare rapidamente
## se un dato primo risulta generatore di un numero ciclico.
##
## Lavorando in base due, l'unico numero primo pari è stato opportunamente omesso.
##
 
Primi = [3, 5, 7,  11,  13,  17,  19,  23,  29,  31,  37,  41,  43,  47,  49,  53,  59,  61,
          67,  71,  73,  79,  83,  89,  97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139,
         143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
         229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 289, 293, 307, 311, 313,
         317, 323, 331, 337, 347, 349, 353, 359, 361, 367, 373, 379, 383, 389, 397, 401, 409,
         419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
         521, 523, 529, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617,
         619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
         739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 841,
         853, 857, 859, 863, 877, 881, 883, 887, 899, 907, 911, 919, 929, 937, 941, 947, 953,
         961, 967, 971, 977, 983, 991, 997]
 
print "Abbiamo a disposizione", len(Primi), "primi come potenziali generatori ciclici."
 
## Si specifica la base numerica di lavoro
base = 2
 
## Totalizzatore dei numeri ciclici verificati
tot_cyclics = 0
 
for p in Primi:
    t = 0
    r = 1
    cyclic = 0
 
    while 1:
        t += 1
        x = r * base
        d, r = divmod(x, p)
        cyclic = cyclic * base + d
        ##print t, d, r, cyclic
        if r == 1:
            break
 
    if t == p -1:
        tot_cyclics += 1
        print "*************************************************************************************" 
        print "# Primo generatore = {0:3d} -> il corrispondente numero ciclico ha {1} cifre in base {2}".format(p, t, base)
        fmt = "{" + "0:0{0}b".format(t) + "}"
        print fmt.format(cyclic)
 
print "\n*************************************************************************************" 
 
print "Sono stati elaborati i primi {0} numeri primi dispari consecutivi".format(len(Primi))
 
print "per generare i primi {0} numeri ciclici in base {1}".format(tot_cyclics, base)
Ecco invece l'esempiuccio in C + MIRACL:

/*
**
** Codice di esempio per la ricerca di numeri ciclici.
** Fa uso della nota libreria MIRACL.
**
** Compilato con Borland C/C++ 5.5.1
**
*/
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <mem.h>
#include "miracl.h"
 
/*
** Chiediamo alla libreria di pregenerare tutti i numeri primi
** non superiori al valore qui definito
*/
#define PRIME_CEILING 1000
 
/*
** Ci accontentiamo di cercare i primi MAX_CYCLICS numeri ciclici
** Se chiediamo troppo, l'output diviene rapidamente illeggibile ! 
*/
#define MAX_CYCLICS 11
 
/*
** Dimensione, in bytes, riservata ad ogni singola variabile intera
** Inutile esagerare, per il momento
*/
#define MIRACL_SIZE 500
 
void display_num(big n, int wid, miracl *mip)
{
    cotstr(n, mip->IOBUFF);
 
    if (strlen(mip->IOBUFF) < (unsigned)wid -1)
    {
        int ds;
        ds = wid - strlen(mip->IOBUFF) -1;
        while (ds--)
        {
            putchar('0');
        }
    }
    puts(mip->IOBUFF);
}
 
int main(void)
{
    /*
    ** Lavoriamo in binario, dunque questa potrebbe essere una costante.
    ** Se desideriamo sperimentare con altre basi (es. ottale)
    ** ovviamente dobbiamo "filtrare" i primi generatori in modo da evitare eventuali 
    ** divisori della base prescelta.
    ** D'altro canto, in esadecimale non esistono numeri ciclici,
    ** per un noto teorema che ne esclude la presenza 
    ** nelle basi che siano quadrati perfetti.
    */
    unsigned int base;
 
    /*
    ** Totalizzatore per i numeri ciclici, avrà come limite la
    ** pseudocostante di preprocessore denominata MAX_CYCLICS
    */
    unsigned int total;
 
    /* Varie ed eventuali */
    unsigned int i, r, t;
 
    /* Ecco i numeri interi davvero grandi ! */
    big mx, x1, x2;
    miracl *mip;
 
    total = 0;
    i = 0;
    base = 2;
 
    mip = mirsys(MIRACL_SIZE, 10);
    mx = mirvar(0);
    x1 = mirvar(0);
    x2 = mirvar(0);
 
    mip->IOBASE = base;
    gprime(PRIME_CEILING);
 
    while(total < MAX_CYCLICS)
    {
        i++;
        if (mip->PRIMES[i] == 0)
            break;
        t = 0;
        r = 1;
        zero(mx);
        zero(x2);
 
        do
        {
            ++t;
            convert(r * base, x1);
            r = subdiv(x1, mip->PRIMES[i], x2);
            premult(mx, base, mx);
            add(x2, mx, mx);
        } while (r != 1);
 
        if (t == (unsigned)mip->PRIMES[i] -1)
        {
            /*
            ** Se giungiamo QUI, abbiamo un numero ciclico !
            */
            int j;
            fputs("*************************************************************************************\n", stdout);
            ++total;
            printf("# primo generatore = %d -> il corrispondente numero "
                   "ciclico ha %d cifre in base %d\n",
                   mip->PRIMES[i], mip->PRIMES[i] -1, base);
            display_num(mx, mip->PRIMES[i], mip);
            copy(mx, x1);
 
            /* Stampiamo i primi mip->PRIMES[i] multipli */
            for (j = 1; j < mip->PRIMES[i]; j++)
            {
                add(mx, x1, x1);
                display_num(x1, mip->PRIMES[i], mip);
            }
        }
    }
    printf("\n*************************************************************************************\n"
           "Sono stati testati i primi %d numeri primi dispari consecutivi\n"
           "per generare i primi %d numeri ciclici in base %d.\n\n",
           i, total, base);
    return (0);
}
Il codice è scritto nel modo più didattico e stimolante possibile, spero. Vi è ampissimo spazio per modifiche e personalizzazioni.

Quasi inutile rimarcare che esistono algoritmi maggiormente efficienti, e che questo genere di ricerche viene in realtà quasi sempre svolto tramite applicativi di calcolo numerico dedicati...

Attenzione alle costanti di preprocessore definite in testa al sorgente: sono interrelate in modo piuttosto sottile, dunque non cambiatele senza aver meditato (e letto la documentazione di MIRACL).

Il codice d'esempio viene fornito "as is" e l'unica garanzia è che, una volta debitamente compilato, l'eseguibile occuperà un po' di spazio sui vostri supporti di massa.

Buon divertimento...


Qualche libro di carta per chi volesse approfondire un po':
- Luciano Cresci, "I numeri celebri", Bollati Boringhieri
- Midhat Gazalé, "Il numero", Dedalo
- Andrew Hodges, "Il curioso dei numeri", Mondadori
- Georges Ifrah, "Enciclopedia Universale dei Numeri", Mondadori
- David Wells, "Numeri memorabili", Zanichelli
- Qualunque cosa porti la firma di Martin Gardner...

Commenti