[HOME - BASE Cinque - Appunti di Matematica ricreativa]

Numeri invarianti perfetti

Chi ha paura delle enormi creature
che si trovano un po' al di là dei comuni territori numerici?

Ringrazio Enrico Delfini per questo intervento al Forum.

Numeri invarianti perfetti (o piucheperfetti) sono detti i numeri di n cifre uguali alla somma delle n-esime potenze delle singole cifre da cui sono composti.

Esempio:
153 = 1^3 + 5^3 + 3^3
Il classico 153 è formato da 3 cifre ed è uguale alla somma dei cubi delle sua cifre.
Esistono altri tre invarianti perfetti di tre cifre.

1634 ; 8208 e un altro che non vi dico sono quelli di 4 cifre.

Chi vuole fare qualche esperimento in javascript può andare a La pagina aperta del 153 di questo sito.

Esiste almeno un invariante perfetto di 5, di 6, di 7, di 8 cifre.

Non ne conosco di 9, ma
4 679 307 774
è l'unico invariante perfetto di 10 cifre, cioè, ripeto, pari alla somma delle decime potenze delle sue dieci cifre.

E ora,....tenetevi forte:
115 132 219 018 763 992 565 095 597 973 971 522 401
è uguale alla somma delle 39-esime potenze delle sue 39 cifre!!!!

Leggo (sul già citato libro dell'ing. Cresci) che è stata dimostrata l'impossibilità di numeri invarianti perfetti di oltre 60 cifre, ma per ora il record è il mostro di 39.

Una particolarità: nel "mostro" vi è una presenza "anomala" di cifre dispari (28 a 11); secondo voi è un caso o c'è una ragione?

Risposte & riflessioni

Gianfranco Bo
In fondo faccio una proposta, qui tengo degli appunti di lavoro.

Giorgio Dendi
Non so davvero come si faccia a trovare questi numeri senza un calcolatore. Ho visto che nessuno ha risposto alla domanda di Enrico sui numeri perfetti di tre cifre, e su quella mi sono cimentato. Ho fatto un'osservazione: ho scoperto che se c'è un numero perfetto con una certa caratteristica, allora si può scrivere subito un altro numero perfetto. Altre regole non ho trovato, e ho dovuto lavorare molto di penna e, dopo essermi scritto una tabellina, ho fatto molti calcoli. Ho trovato, oltre al 153, anche 370 e 407 e un altro, che, come dicevo sopra, si può trovare senza fare calcoli, ma con il semplice ragionamento a cui accennavo. Pensavo che Enrico non abbia citato l'ultimo numero perfetto di 4 cifre per lo stesso motivo per cui non cito io l'ultimo di 3 cifre: con una semplice osservazione si può ricavare, una volta che si sanno gli altri numeri perfetti? Io non ho trovato nulla.
Sarei curioso se qualcuno ha trovato qualche sistema per snellire la ricerca, se questa è fatta a mano, senza calcolatore. Ad esempio, pensavo di fare considerazioni su quante cifre pari e quante dispari c'erano, ma non mi ha aiutato molto. A questo punto non mi cimento di sicuro a cercare i numeri perfetti di 4 cifre.

Ecco la mia osservazione: se riesco a trovare un numero che sia uguale alla potenza n-esima delle sue cifre, nel caso che la sua ultima cifra sia 0, allora posso trovarne un altro con le stesse cifre, ma con in fondo 1 al posto di 0. Quindi avevo visto che 153, 370 e 407 sono tali che abc=a^3+b^3+c^3. Con l'osservazione appena fatta, posso dire che anche 371 godrà della stessa proprietà. Senza fare calcoli, ma avendo fiducia che qualcuno ha verificato la proprietà per il 370.

Utervis
Da questa si deduce anche che se l'ultima cifra è unitaria, come nel caso del 371, allora anche quello precedente deve essere un numero perfetto avendo accettato che il primo è stato già verificato! :-)))

Ma nel caso dei numeri a 4 cifre nessuno termina con zero od uno! :-(

Grazie a tale proprietà possiamo stabilire che anche:

115.132.219.018.763.992.565.095.597.973.971.522 400

deve essere un "mostro alla Enrico" nel senso che è un invariante perfetto uguale alla somma delle 39-esime potenze delle sue 39 cifre!

Tu che sai tutto sui numeri eri a conoscenza anche di tale guinnes?

Gianfranco Bo
Il MOSTRO di Delfini e la domanda di Peppe mi hanno notevolmente interessato e stimolato.
Perciò vorrei fare una proposta che è certamente nelle nostre capacità.

Possiamo trovare con il computer i numeri INVARIANTI PERFETTI fino all'esponente 60 ed oltre?
Possiamo poi chiederci: ci fidiamo del risultato? e se non ci fidiamo, come possiamo verificarlo?

VI RICORDO CHE:
Numeri invarianti perfetti (o piucheperfetti) sono detti i numeri di n cifre uguali alla somma delle n-esime potenze delle singole cifre da cui sono composti.
Esempio:
153 = 1^3 + 5^3 + 3^3
Il classico 153 è formato da 3 cifre ed è uguale alla somma dei cubi delle sua cifre.

Qualcuno ha detto che il computer è un cretino immensamente veloce.
L'uomo lo programma, creando degli algoritmi, e può sfruttare la sua velocità per ottenere risultati straordinari.
Però se anche gli algoritmi sono cretini, la velocità del computer è del tutto inutile. In certi casi avere un Commodore 64 (1 Mhz) o un Pentium x (1 Ghz) è praticamente la stessa cosa: il primo si siede al livello 6 e l'altro al livello 9. Mentre magari c'è bisogno di arrivare al livello 100.

Dunque l'equazione giusta è: genio lento + cretino veloce = buona matematica al computer

Da parte mia ho fatto un po' di ricerche in Internet e ho trovato un programma molto interessante:
è un interprete BASIC (implementato da un giapponese) che ha dell'incredibile.
Tra l'altro !!!!!LAVORA CON NUMERI razionali FINO A 10000 (dico diecimila) CIFRE!!!!!

Se vi interessa, lo potete scaricare a questo indirizzo.
ATTENZIONE: la prudenza non è mai troppa, NON sono in grado di verificare se contiene uno spyware, perciò l'ho caricato su un computer dove tengo del software in quarantena.

Copyright
SHIRAISHI Kazuo
e-mail kazuo.shiraishi@nifty.ne.jp
Web http://www.vector.co.jp/authors/VA008683/english

Qui sotto c'è il programma più ingenuo (per non dire cretino) del mondo che trova tutti i numeri invarianti perfetti.
L'unico input da dare è l'esponente, scrivendolo direttamente nel programma.

Il problema è che già per l'esponente = 7 il programma comincia a "sedersi", i tempi di attesa diventano lunghissimi.

Ecco una tabella degli esponenti e dei rispettivi tempi di calcolo.

esp - tempo (secondi)
2 - 0.11
3 - 0.38
4 - 3.63
5 - 44.27
6 - 520.53
7 - 6349

Ciò è dovuto all'ingenuità dell'algoritmo, che procede esaminando TUTTI i numeri dell'intervallo, e sommando le potenze ennesime di tutte le loro cifre.

Ad es. per n=7, esamina tutti i numeri da 1 000 000 a 9 999 999.

Immaginiamoci un po' quanti calcoli deve fare per n=39 o n=60.

Ho due domande da porre:

1) Come aumenta il tempo di calcolo in funzione di n, con questo algoritmo?

2) E' possibile migliorare drasticamente l'algoritmo in modo da rendere i tempi accettabili?

NOTA1: per migliorare l'algoritmo non c'è bisogno di conoscere né il BASIC né nessun altro linguaggio di programmazione.
NOTA2: a volte per migliorare un algoritmo bisogna farne uno completamente diverso
NOTA3: se conoscete un altro software specialista in grandi numeri, fatecelo sapere.

Ecco il programma

--------------------
DIM cifra(60)

LET t1 = TIME

PRINT "Inizio"

LET esponente = 7
LET inizio = 10^(esponente-1)
LET fine = 10^esponente-1

FOR i = inizio TO fine
LET somma=0
FOR j = 1 TO esponente
LET cifra(j) = VAL(mid$(STR$(i),j,1))
LET somma = somma+cifra(j)^esponente
NEXT j
IF somma = i THEN PRINT i
NEXT i

PRINT "Fine"

LET t2 = TIME
PRINT (t2-t1)

END
--------------------

Ecco i risultati con n = 2..7

n=2
nessun risultato

n=3
153
370
371
407

n=4
1634
8208
9474

n=5
54748
92727
93084

n=6
548834

n=7
1741725
4210818
9800817
9926315

Ringrazio Giovanni Macchia per il programma in C++
Giovanni Macchia
I tempi sono bassi (un programmino in C++ l'ho scritto io ed è ovviamente veloce) ma per n alto ci sono problemi di grandezza massima (anche se il programma l'ho scritto in 5 minuti e non ci ho perso molto la testa).

Ecco il programma; chiaramente, date le limitazioni dell'intero in C , per n maggiore di 10 dà problemi. Per il resto impiega pochi secondi. Devo risolvere il problema sostituendo ad int un double...
Non è granchè, ma per averlo scritto all'una di notte e in cinque minuti, va bene,,

#include <iostream>
#include <sstream>
#include <cstdlib>
using namespace std;

int power(long m, long n)
{
int k=1;
for (int i = 1;i<=n;i++)
k=k*m;
return(k);
}

void main ( )
{int esponente;
long j,m;char *p=new char;
int i, somma;
char *s=new char[80];
p[1]='\0';
cin >> esponente;
int min=power(10,(esponente - 1));
int max= power(10,esponente)-1;
i=min;
while(i<=max)
{
somma =0;
sprintf(s,"%d",i);
for (j=1;j<=esponente;j++)
{
p[0]=s[j-1];
sscanf(p,"%d",&m);
somma = somma + power(m,esponente);
}
if ((somma - i)==0) cout << i<<'\n';
i++;
}
cout << '\n'<< "Fine";
}

Ringrazio Pasquale per il meticoloso lavoro che ha fatto con il Decimal Basic. Copio qui sotto il suo programma e le istruzioni per utilizzarlo.
Pasquale
Come funziona:

-Metti "invaria1.bas" nella stessa directory di "Basic.exe"
-Lanci il Decimal Basic con Basic.exe o con un collegamento dal Desktop
-Clicchi sul pulsante 10/1000, altrimenti non funziona
-Apri il file "invaria1.bas"
-Clicchi sul pulsante RUN (freccia tipo play)
-Inserisci i dati che ti vengono richiesti (esponente, minimo e massimo)
-Aspetti e leggi gli invarianti con i singoli tempi ed al termine con il tempo totale, oppure leggi solo
  il tempo totale, il che vuol dire che non vi sono invarianti.

Il programma genera un file con dati stringa "invaria.txt" nel quale potrai leggere, a programma fermo, gli invarianti trovati (basta cliccare sul file o ti costruisci un piccolo programma di lettura).
Inoltre il programma genera i file numerici "conserva1.txt" e "conserva2.txt" nei quali vengono memorizzati i dati relativi al lavoro svolto: in caso di interruzione casuale o volontaria del lavoro,
al prossimo rilancio, questi file verranno letti ed il lavoro riprenderà da dove era stato interrotto.
Quando lanci il programma la prima volta per un nuovo esponente con nuovi minimo e massimo,
dovrai prima cancellare questi file manualmente.
Quando lanci il programma come prosecuzione di un lavoro interrotto, questi file devono esserci e per quanto riguarda i dati da inserire, che vengono richiesti al lancio del programma, questi devono essere gli stessi della prima volta.
Cosa sono minimo e massimo:
questi servono a restringere il campo della ricerca un po' ad occhio.
La ricerca degli invarianti viene effettuata sulla tipologia dei numeri generatori, i quali sono dei numeri per definizione con una quantità di cifre uguale all'esponente, che possono contenere le cifre dallo 0 al 9 in quantità variabili da 0 a B (esponente): però se prendiamo ad esempio l'esponente 39 già noto, vediamo che ogni cifra è presente almeno una volta ed al massimo 7 volte,
quindi in questo caso imponiamo il minimo a 1 ed il massimo a 7 (dovrebbero venir fuori i 2 invarianti già noti).
Certamente se non l'avessi saputo a priori, avrei potuto magari impostarli a 0 e 13, che mi sembra un range abbastanza congruo, oppure avrei potuto ampliare ancora di più l'intervallo allungando i tempi della ricerca, o volendo essere sicuri a 0 e 39.
Il programma è dotato comunque di filtri che scartano i numeri impossibili (quelli che non sono lunghi quanto l'esponente, quelli che contengono cifre in quantità non ammesse, quelli la cui somma delle potenze generano un numero di lunghezza diversa dall'esponente o generano un numero che contiene cifre in quantità diversa da quello generatore).
Insomma si tratta di vedere quanto tempo occorre per trovare gli invarianti da 39 già noti, che quindi devono venir fuori per forza, e poi passare agli esponenti superiori (come già detto attualmente non posso farlo a causa del p.c. che mi sta rompendo abbastanza).

Il programma funziona (lo puoi provare con gli esponenti bassi per sicurezza) e se avrai qualche dubbio, anche per quanto riguarda certe scelte che possono sembrare ridondanti, o per quanto riguarda l'uso del Decimal Basic, chiedimi delucidazioni.

!'Ricerca completa invarianti:genera tutte le combinazioni valide di
!' presenza cifre da 0 a 9 e le valuta direttamente.
!'Questa è una versione semplificata, per cui mancano i controlli relativi ad input
!'errati.
!'Prima di premere il pulsante di avvio per la prima volta che si sceglie un esponente,
!'cancellare dalla directory di lavoro in cui si trova "invaria1.bas" i file "conserva"
!'e "invar"

!' PRIMA DI AVVIARE SETTA IL PULSANTE 10/1000

OPTION BASE 0

DIM tabmax (9,3 TO 60) !'massimo consentito di presenze per ogni cifra
FOR m = 0 TO 9
FOR n = 3 TO 60
LET s1 = n*m^n
LET q = n
LET k = 0
DO
IF LEN(STR$(s1)) < n THEN
LET q = q - 1
LET k = k + 1
LET s1 = q* m^n
LET s2= k*9^n
LET s1 = s1 + s2
END IF
LOOP UNTIL LEN(STR$(s1)) >= n
IF LEN(STR$(s1)) =n THEN LET tabmax(m,n) = q ELSE LET tabmax(m,n) = q +1
NEXT n
NEXT m

DIM potenze(9,3 TO 60)

FOR m=1 TO 9 !'tabella delle potenze
FOR n= 3 TO 60
LET potenze(m,n)=m^n
NEXT N
NEXT M


INPUT PROMPT "inserisci esponente (min 3 - max 60) -> ":b
INPUT PROMPT "inserisci minimo presenza cifre -> ":mini
INPUT PROMPT "inserisci massimo presenza cifre -> ":maxi

DIM presenze1(9) !'presenza cifre in ogni combinazione
DIM presenze2(9) !'presenza cifre nella somma delle potenze delle combinazioni
DIM minix1(9)
DIM minix2(9)


OPEN #1:NAME "conserva1" !'valori di partenza memorizzati durante il lavoro
FOR m=0 TO 9
INPUT #1,IF MISSING THEN EXIT FOR:minix1(m)
NEXT M

OPEN #2:NAME "conserva2" !'valori di partenza memorizzati durante il lavoro
FOR m=0 TO 9
INPUT #2,IF MISSING THEN EXIT FOR:minix2(m)
NEXT M

OPEN #3:NAME "invar",ACCESS OUTPUT !'memorizza gli invarianti


LET cont1=0
LET cont2=0
FOR m = 0 TO 9
LET cont1 = cont1 + minix1(m)
LET cont2 = cont2 + minix2(m)
NEXT M

PRINT "inizio come da input -> ";
FOR m=0 TO 9
PRINT mini;
NEXT M
PRINT

!'per continuare il lavoro interrotto

LET flag=0
LET flag1=0
LET flag2=0
IF cont1>0 OR cont2>0 THEN
LET flag=1
FOR m=0 TO 9
IF minix1(m) > minix2(m) THEN
LET flag1=1
PRINT "continua lavoro da -> ";
FOR n=0 TO 9
PRINT minix1(n);
NEXT N
EXIT FOR
END IF

IF minix2(m) > minix1(m) THEN
LET flag2=1
PRINT "continua lavoro da -> ";
FOR n=0 TO 9
PRINT minix2(n);
NEXT N
EXIT FOR
END IF
NEXT M
if flag1=0 and flag2=0 then
flag1=1
flag2=1
PRINT "continua lavoro da -> ";
FOR n=0 TO 9
PRINT minix2(n);
NEXT N
end if

END IF

PRINT
PRINT
PRINT " N O N T O C C A R E"
PRINT
PRINT



LET t1 = TIME

FOR m0 = mini TO maxi
FOR m1 = mini TO maxi
FOR m2 = mini TO maxi
FOR m3 = mini TO maxi
FOR m4 = mini TO maxi
FOR m5 = mini TO maxi
FOR m6 = mini TO maxi
FOR m7 = mini TO maxi
FOR m8 = mini TO maxi
FOR m9 = mini TO maxi


LET cont = 0
LET cont = cont + m0
IF cont > b OR m0>tabmax(0,b)THEN GOTO 110
LET presenze1(0) = m0
LET cont = cont + m1
IF cont > b OR m1>tabmax(1,b)THEN GOTO 100
LET presenze1(1) = m1
LET cont = cont + m2
IF cont > b OR m2>tabmax(2,b)THEN GOTO 90
LET presenze1(2) = m2
LET cont = cont + m3
IF cont > b OR m3>tabmax(3,b)THEN GOTO 80
LET presenze1(3) = m3
LET cont = cont + m4
IF cont > b OR m4>tabmax(4,b)THEN GOTO 70
LET presenze1(4) = m4
LET cont = cont + m5
IF cont > b OR m5>tabmax(5,b)THEN GOTO 60
LET presenze1(5) = m5
LET cont = cont + m6
IF cont > b OR m6>tabmax(6,b)THEN GOTO 50
LET presenze1(6) = m6
LET cont = cont + m7
IF cont > b OR m7>tabmax(7,b)THEN GOTO 40
LET presenze1(7) = m7
LET cont = cont + m8
IF cont > b OR m8>tabmax(8,b)THEN GOTO 30
LET presenze1(8) = m8
LET cont = cont + m9
IF cont <>b OR m9>tabmax(9,b)THEN GOTO 20
LET presenze1(9) = m9


!'da qui la somma delle cifre è uguale all'esponente
!'quindi la combinazione è valida

IF flag=1 THEN
LET flag=0
IF flag1=flag2 OR flag1>flag2 THEN

LET m0=minix1(0)
LET m1=minix1(1)
LET m2=minix1(2)
LET m3=minix1(3)
LET m4=minix1(4)
LET m5=minix1(5)
LET m6=minix1(6)
LET m7=minix1(7)
LET m8=minix1(8)
LET m9=minix1(9)
FOR m=0 TO 9
LET presenze1(m)=minix1(m)
NEXT M

ELSE

LET m0=minix2(0)
LET m1=minix2(1)
LET m2=minix2(2)
LET m3=minix2(3)
LET m4=minix2(4)
LET m5=minix2(5)
LET m6=minix2(6)
LET m7=minix2(7)
LET m8=minix2(8)
LET m9=minix2(9)
FOR m=0 TO 9
LET presenze1(m)=minix2(m)
NEXT M

END IF
END IF

LET somma=0 !'fai la somma delle potenze
FOR m=1 TO 9 !'inutili le potenze di zero
LET somma=somma+potenze(m,b)*presenze1(m)
NEXT M


IF LEN(STR$(somma))<>b THEN GOTO 20 !'scarta la combinazione se il precedente risultato
!'non dà un numero lungo quanto l'esponente scelto (b)



ERASE #1
FOR x=0 TO 9
PRINT #1:presenze1(x)
NEXT X

ERASE #2
FOR x=0 TO 9
PRINT #2:presenze1(x)
NEXT X


MAT presenze2=ZER !'reinizializza presenze2()

FOR m=1 TO b !'e inserisci il numero risultante
!'espresso in quantità di cifre presenti

LET v=VAL(mid$(STR$(somma),m,1))
LET presenze2(v)=presenze2(v)+1
NEXT M

FOR m=0 TO 9 !'confronta con la combinazione
!'di partenza e scarta se non uguale

IF presenze1(m)<>presenze2(m) THEN GOTO 20
NEXT M

!'da qui la combinazione è valida ed è un invariante (somma)
!'memorizza, scrivi e calcola il tempo di elaborazione

LET t2 = TIME
LET tempo = (t2-t1)/3600
LET tempo=INT(tempo*1000)/1000
WRITE #3:STR$(somma)
PRINT "esp";b;" -> ";somma;" tempo in ore -> ";tempo

20
NEXT M9
30
NEXT M8
40
NEXT M7
50
NEXT M6
60
NEXT M5
70
NEXT M4
80
NEXT M3
90
NEXT M2
100
NEXT M1
110
NEXT M0

CLOSE #1
CLOSE #2
CLOSE #3

LET t2 = TIME
LET tempo = (t2-t1)/3600
LET tempo=INT(tempo*1000)/1000

PRINT "tempo totale: ore ="; tempo
END

Giovanni Sciortino
Non ho creato nulla di nuovo ho solo tradotto il tuo algoritmo in c ottenendo dei risultati migliori rispetto ai tempi che riporti.
Es: per trovare tutti i numeri invarianti perfetti di 4 cifre il mio programma impiega su un computer pentium 4 1400 mhz 30 millesimi di secondo, e lo stesso programma per lo stesso calcolo in un pentium 2 233 impiega 90 millesimi di secondo. Non so se ti può interessare, magari hai utilizzato computer meno veloci del mio per provare il programma comunque se t'interessa ecco il sorgente:

#include <windows.h>
#include <math.h>
#include <stdio.h>
#include <time.h>   #define interi unsigned __int64   char cifra[200];
 
 
int main(){
 unsigned char esponente;
 printf("inserisci il numero di cifre:");
 scanf("%d",&esponente);
 DWORD t1 = GetTickCount();
 interi inizio = (unsigned long)pow(10,esponente-1
  );
 interi fine = inizio*10;
 interi i = inizio;
 while (i < fine){
  interi somma=0;
  interi j = 0;
  sprintf(cifra,"%d",i);
  while (j < esponente){
   somma = somma+(int)pow((cifra[j]-'0'),esponente);
   ++j;
  }
  if (somma == i)
   printf("%d\n",i);
  ++i;
 }
 DWORD t2 = GetTickCount();
 double a = (t2-t1);
 printf("tempo impiegato(in millesimi di secondo): %f \n", a);
 return 0;
}

Questo può essere compilato senza errori con il compilatore visual c++,oppure con la maggior parte degli altri compilatori sostituendo la riga #define interi unsigned __int64 con #define interi unsigned long long

Sito Web realizzato da Gianfranco Bo