Tag Archives: teoria dei numeri

Numeri felici

Avete mai sentito parlare dei numeri felici? Io no, almeno fino alla settimana scorsa. La loro definizione è molto semplice. Prendete un numero intero positivo (in base 10), e calcolate la somma dei quadrati delle sue cifre, ottenendo un nuovo numero. Rifate la stessa operazione (che chiamerò per comodità f con il nuovo numero, e continuate così a piacere, fino a che succederà una di queste tre possibilità: i numeri ottenuti continueranno a crescere all’infinito; finite all’interno di un ciclo che evidentemente si ripeterà all’infinito; giungete a un numero tale che la somma dei quadrati delle sue cifre sia il numero stesso. I numeri in quest’ultima categoria sono i numeri felici, mentre gli altri sono evidentemente tristi. Il bello di questi numeri è che possono essere oggetto di una lezione di matematica non standard già alle scuole medie, se il professore sa gestire bene la classe. Nel seguito del post vi racconterò alcune di queste proprietà: per chi vuole la pappa fatta e se la cava con l’inglese, questo post di Evelyn Lamb ha un link a un pdf con le varie domande che si possono fare.

La prima cosa che si può vedere è che la prima categoria che ho ipotizzato (valori che crescono all’infinito) in realtà non esiste. Prendiamo infatti un numero di n cifre, con n maggiore o uguale a 4: la somma dei quadrati delle sue cifre sarà minore di 100n, e quindi inferiore a quello di partenza. Questo significa tra l’altro che se siamo armati di una calcolatrice possiamo trovare tutti i cicli possibili e quali sono i valori “di arrivo” per i numeri felici. Ma prima di fare i conti conviene come al solito usare il cervello per vedere se ne possiamo fare di meno! Innanzitutto se applichiamo f a due numeri con le stesse cifre in ordine diverso otterremo lo stesso risultato, quindi possiamo solo considerare i numeri le cui cifre siano in ordine non decrescente, ed evitare quelli che hanno degli zeri. È poi chiaro che almeno un numero felice esiste! Se partiamo da 1 otteniamo infatti ancora 1. Ma questo significa che i numeri felici sono infiniti, perché tutte le potenze di 10 dopo il primo passo danno 1. Ci saranno dei cicli? Beh, vediamo cosa succede applicando più volte f a partire da 2. Otteniamo 4, 16, 37, 58, 89, 145, 42, 20. Il valore successivo è 4, e quindi abbiamo trovato un ciclo. Andando avanti, possiamo scoprire facilmente che tutti i numeri felici raggiungono 1. Cercando un numero tale che f(n)=n, sappiamo che il numero ha al più tre cifre; ma allora deve essere al massimo 9²+9²+9² = 243; ma allora deve essere al massimo 1²+9²+9² = 163. Da qua non conosco vie rapide, ma il numero di controlli da fare non è molto alto, e quindi si trova facilmente che 1 è l’unica soluzione. Sempre facendo un po’ di conti, si scopre anche qualcosa di meno aspettato: il ciclo che contiene 4 è l’unico possibile. In definitiva, quindi, i numeri felici sono quelli per cui l’applicazione ripetuta di f li fa giungere a 1, mentre i tristi sono quelli per cui l’applicazione ripetuta di f li fa giungere a 4.

I numeri felici hanno anche un’altra caratteristica, che fa capire come non si possa fare matematica solo e unicamente con il calcolatore. Contiamo i numeri felici dino a 1, 10, 100, 1000, 10000, 100000, 1000000; sono rispettivamente 1, 3, 20, 143, 1442, 14377, 143071. Un fisico 🙂 salterebbe subito alla conclusione che la probabilità che un numero a caso sia felice tende al 14,3% circa. E invece non è così! La sempre benemerita OEIS ha una successione con qualche valore in più di numeri felici da 1 a una potenza di 10, da cui si vede che la percentuale comincia a scendere. Quello che in realtà capita è che non c’è una probabilità limite! La percentuale (i matematici in questo caso la chiamano densità asintotica) continua a oscillare. Un comportamento di questo tipo non è inusuale: prendiamo per esempio i numeri la cui prima cifra è 1. Se controlliamo la percentuale di tali numeri tra 1 e 999…..9, sarà evidentemente 1/9; ma se la calcoliamo tra 1 e 1999….9 sarà più o meno 5/9, pertanto non potrà mai esserci un limite. In quest’ultimo caso però il comportamento delle percentuali è abbastanza facile da visualizzare: nel caso dei numeri felici le cose sono più complicate, e al momento si sa solo che la percentuale scende infinitamente spesso sotto il 12% e sale infinitamente spesso oltre il 18%.

Come vedete, anche un concetto a prima vista banale e alla portata anche di un ragazzo delle medie può nascondere delle sorprese!

Congetture piuttosto inutili [Pillole]

John Horton Conway ha proposto cinque problemi, o se preferite cinque congetture, e ha promesso 1000$ a chi ne riesce a risolvere una. Essendo una persona furba, ha anche detto che le soluzioni devono essergli inviate per posta cartacea, ma questo esula dal contenuto del post. I curiosi possono leggere quali sono le congetture sul sito OEIS, dove si può vedere che l’ultima congettura è stata risolta.

Conway prendeva un numero e lo scomponeva in fattori nel modo “naturale”, scrivendoli tutti in ordine crescente e raggruppando tutti quelli uguali, oltre a eliminare il fattore 1. Quindi per esempio 60 = 2²·3·5. Ora Conway “appiattisce” il numero, abbassando gli esponenti e togliendo i segni di moltiplicazione; arriva così a 2235. Fattorizzato a sua volta, il numero si scompone in 3·5·149 che appiattito diventa 35149. Essendo quest’ultimo un numero primo, il giochino termina, perché si continuerà a ottenere lo stesso risultato. Conway era convinto che tutti i numeri sarebbero arrivati prima o poi a un primo, ma non riusciva a dimostrarlo: anzi non riusciva nemmeno a sapere cosa sarebbe successo con 20. (Per i numeri precedenti potete vedere qui quale numero viene raggiunto. Ovviamente i primi si fermano subito: è divertente vedere che sia 9 che 10 si fermano a 2213, perché il primo passa da 3²→32 e 25→25 e il secondo direttamente da 2·5→25; seguono 5²→52 e 2²·13→2213.

Bene: James Davis ha scoperto che la fattorizzazione di 13532385396179 è 13·53²·3853·96179 e quindi viene appiattita al numero stesso, trovando un controesempio e guadagnando 1000 dollaroni. Non si sa se ci siano numeri che formano dei cicli o proseguano all’infinito l’operazione. A che serve tutto questo? A nulla, ovviamente 🙂 se non a vedere quanto si è bravi. I matematici si divertono con poco…

Mersenne 50 e il controllo di primalità

A distanza di un paio d’anni dall’ultima volta è stato scoperto un nuovo primo di Mersenne, il cinquantesimo della serie. In un certo senso non è molto “più grande” del penultimo, che era M(74.207.281): stavolta abbiamo infatti M(77.232.917), e se vi limitate a guardare l’esponente vedete che la distanza dal penultimo è inferiore a quelle precedenti. (Nota: non sono ancora stati testati tutti gli esponenti inferiori, quindi la lista potrebbe non essere completa. È già capitato in passato che GIMPS, il programma distribuito per verificare la primalità di un numero di Mersenne, tirasse fuori un numero che non era il record di grandezza). Tutto è relativo, naturalmente: il numero in questione ha più di 23 milioni di cifre e se volete vedere com’è fatto vi serve scaricare 100 MB zippati.

Quello che vorrei farvi notare è però un’altra cosa. Come si può essere ragionevolmente certi che quel numero sia primo? Non è che uno si possa mettere a dividerlo per tutti i numeri primi, e anche i metodi più evoluti non sono trattabili a mano; quindi ci si deve fidare dei computer, un po’ come nella dimostrazione del teorema dei quattro colori. Gli amici di GIMPS hanno scelto un approccio molto pragmatico: sono stati usati quattro programmi diversi fatti girare su quattro architetture hardware diverse. A questo punto – dopo che i programmi hanno impiegato tra le 35 e le 83 ore di CPU: ve l’avevo detto che il numero era grande! – possiamo avere una certezza sufficiente.

A quando il prossimo primo di Mersenne? Chi lo sa.

Ancora un primo di Mersenne [Pillole]

In questi ultimi giorni avrete probabilmente letto che è stato scoperto il quarantanovesimo numero primo di Mersenne: M(74.207.281), cioè 2 elevato alla 74.207.281 meno uno. Essendo io notoriamente un pignuolo con la u, specifico che è il quarantanovesimo primo di Mersenne a essere stato scoperto, ma per come funziona la ricerca del progetto GIMPS è possibile che ne esistano di più piccoli non ancora scoperti; la cosa non mi stupirebbe troppo, guardando questo grafico.

Dal sito ufficiale ho anche scoperto che il programma aveva indicato la primalità di M(74.207.281) a settembre, ma per un baco software il risultato non era stato notificato. Non lamentatevi insomma delle nostre poste. Né venite a chiedere perché si cercano questi numeri, visto che la risposta non può che essere “per stabilire un nuovo record”. Ognuno si diverte come può e i matematici non fanno eccezione!