Come sapete, la costante ꬲ ≅ 2,71828… se la gioca alla pari con π nel campionato per il numero che appare più spesso nelle formule matematiche. A differenza del pi greco, però, ꬲ è più facile da gestire, non tanto perché è il limite per $n$ tendente all’infinito dell’espressione $(1 + 1/n)^n$ (la definizione usuale) quanto perché è la somma della serie $ \frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + \cdots $ che ha due vantaggi: è facile da scrivere e converge molto rapidamente. Ci sono anche altre rappresentazioni interessanti di ꬲ, come la forma in frazione continua [1, 2, 1, 1, 4, 1, 1, 6, 1, …] che ha permesso a Eulero di dimostrare che è un numero irrazionale. Non è però immediato ricavare questo sviluppo; in compenso esiste una dimostrazione relativamente semplice, dovuta a Joseph Fourier (sì, quel Fourier) dell’irrazionalità di ꬲ. Eccola qua.

Cominciamo a considerare queste due successioni infinite (o meglio, la collezione di successioni infinite per ogni valore di $n$):

$$ a_n = \frac{1}{n+1} + \frac{1}{(n+1)(n+2)} + \frac{1}{(n+1)(n+2)(n+3)} + \cdots $$
$$ b_n = \frac{1}{n+1} + \frac{1}{(n+1)^2} + \frac{1}{(n+1)^3} + \cdots $$

È immediato vedere che la successione $b_n$ è una progressione geometrica, e quindi il suo valore è $\frac{1}{n}$; d’altra parte, ogni termine di $a_n$ tranne il primo è minore a quello corrispondente di $b_n$ mentre il primo è uguale, e quindi $ 0 < a_n < \frac{1}{n} $. Adesso viene il bello. Prendiamo la definizione di ꬲ come somma infinita e moltiplichiamola per $n!$. I primi $n$ termini del risultato sono tutti interi, mentre la somma di quelli che rimangono, dopo avere tolto $n!$ a denominatore, corrisponde proprio a $a_n$ e quindi è compresa tra 0 e 1. Possiamo riscrivere questo risultato dicendo $$ a_n = n!ꬲ - \textrm{int}(n!ꬲ)$$ La dimostrazione è praticamente terminata. Supponiamo infatti per assurdo che ꬲ sia razionale, e quindi possiamo scrivere $ꬲ = \frac{k}{m}$, con $k$ e $m$ interi. Ma allora $m!ꬲ$ è intero, e dunque $ (m!ꬲ) = \textrm{int}(m!ꬲ)$, il che è impossibile perché sappiamo che tutti gli $a_n$ sono maggiori di zero. QED. Cosa possiamo ricavare da questa dimostrazione? Che Fourier era uno che ne sapeva: a me non sarebbe mai venuto in mente un percorso del genere. Col senno di poi però si può forse intuire cosa sia venuto in mente a Fourier. Il fatto che i termini della successione infinita tendono a zero molto, molto rapidamente ci fa capire che non hai spazio per riuscire a mettere insieme tutti i coefficienti dei denominatori per arrivare a un numeratore multiplo di essi; è un po’ la stessa idea che ebbe Liouville quando costruì esplicitamente il primo numero che si poteva dimostrare essere trascendente. Il bello di questa dimostrazione è comunque che possiamo tranquillamente spiegarla a uno studente liceale, una volta dato per assodato qual è lo sviluppo in serie infinita di ꬲ; non è che siano cose che capitino tutti i giorni!

Ultimo aggiornamento: 2025-12-03 13:32

Nel 1918 József Kürschák dimostrò che la somma di reciproci di due o più numeri consecutivi non può mai essere un intero. Come corollario, l’unico valore intero toccato calcolando la serie armonica $H_n = 1 + 1/2 + 1/3 + 1/4 + …$ è 1. Ci si può però oziosamente chiedere quanto vicino si può arrivare a un intero. John Cook in una successione di post ha mostrato che se ci limitiamo ai numeri da 1 a 100000 abbiamo che $$ \sum_{k=27134}^{73756} \frac{1}{k} \approx 1$$ con un errore dell’ordine di $10^{-11}$, e questa è la migliore approssimazione possibile a 1.

Limitandoci alle porzioni di serie armonica, si arriva rapidamente a un problema: i numeri in virgola mobile non sono abbastanza precisi per fare tutte le addizioni. Fortunatamente abbiamo a nostra disposizione un’approssimazione molto buona: $H_n \approx \log n + \gamma + \frac{1}{2n} – \frac{1}{12n^2}$, dove $\gamma$ è la costante di Eulero-Mascheroni pari a circa 0,57721. (Curiosità: non è noto se sia o no un numero irrazionale, ma tutti credono di sì, anche perché in caso contrario il suo denominatore dovrebbe avere almeno $10^{242080}$ cifre…). Notate come l’approssimazione usata da Cook sia molto più accurata di quella usuale $H_n \approx \log n + \gamma$, per andare più sul sicuro. Cook si è divertito a scrivere un programmino Python per trovare il termine della serie armonica più vicino a un numero (non necessariamente intero) dato, scoprendo per esempio che $H_12366 \approx 9,99996214846655$.

Ma anche questo programma, pur essendo ben fatto, ha dei problemi di arrotondamento se il numero cercato è molto grande. Per esempio dice che se vogliamo arrivare ad approssimare 100 dobbiamo sommare 15092688622113830917200248731913020965388288 termini, e l’errore relativo è dell’ordine di $3 \times 10^{-15}$. Ma usando Mathematica e l’approssimazione $n \approx \rm{exp}(m − \gamma)$, dove $m$ è il numero che vogliamo approssimare e $n$ il numero di termini richiesti, Cook mostra che la vera quantità di termini che dobbiamo sommare è 15092688622113788323693563264538101449859497; insomma i due numeri divergono dalla quattordicesima cifra, il che ha senso visto che siamo ai limiti della precisione dei numeri a 64 bit. Per curiosità, per arrivare a 1000 occorrono un bel po’ di termini, cioè

110611511026604935641074705584421138393028001852577373936470952377218354575172401275457597579044729873152469512963401398362087144972181770571895264066114088968182356842977823764462179821981744448731785408629116321919957856034605877855212667092287520105386027668843119590555646814038787297694678647529533718769401069269427475868793531944696435696745559289326610132208504257721469829210704462876574915362273129090049477919400226313586033

(un numero di 435 cifre). Che possiamo dedurre da tutto questo? Due cose. La prima è che la serie armonica cresce molto lentamente; la seconda è che bisogna sempre sapere qual è il modo migliore per fare un conto, tenendo conto delle limitazioni dei computer…

Ultimo aggiornamento: 2025-11-26 09:24

La successione infinita mostrata qui sopra è stata probabilmente la prima ad essere sommata. Naturalmente l’artefice di questo risultato è stato Archimede, l’unico matematico dell’antichità che non aveva paura di trattare con quantità infinite. Questo risultato gli serviva per quadrare la parabola; chiaramente la dimostrazione formale che fece per la quadratura sfruttò il metodo di esaustione di Eudosso, ma per quanto riguarda la somma il siracusano mostrò la figura qui raffigurata. Il quadrato grande di lato 1 è diviso in quattro parti uguali: una è colorata (e quindi ha area 1/4), due sono bianche, la quarta è divisa a sua volta allo stesso modo, con un quadrato colorato di area 1/16, due quadrati bianchi della stessa area e un quarto quadrato da dividere a sua volta. In definitiva, alla parte colorata corrispondono due parti identiche non colorate, e tutte assieme riempiono il quadrato: pertanto l’area complessiva delle parti colorate è 1/3.

Ok, in realtà non è proprio così: come spiega la voce di Wikipedia, Archimede dimostrò che la somma 3/4 + 3/16 + 3/64 + 3/256 + ⋯ si avvicina quanto si vuole a 1. (Sempre esaustione, claro). Nella sua dimostrazione il quadrato colorato e i due non colorati formano uno gnomone, cioè una figura a L; l’insieme di tutti gli gnomoni riempiono il quadrato.

Ma la cosa forse più bella è che non è necessario usare i quadrati per mostrare che la somma in questione vale 1/3. Come potete vedere nella figura qui a fianco, è possibile prendere un triangolo equilatero e scomporlo in modo tale da avere la stessa suddivisione. Quale delle due scomposizioni è la migliore? Per quanto mi riguarda, la risposta è “entrambe”; ciascuna costruzione è infatti interessante, e visualmente chiara. Il bello di queste dimostrazioni senza parole è proprio questo: capire un risultato senza dover fare conti (in questo caso bisogna saper contare fino a tre, ma direi che ce la possiamo fare…)

La scorsa settimana ho scritto che anche se la struttura logica dell’algoritmo RSA ha cinque parametri, la chiave di cifratura e è quasi sempre settata a 65537, per ragioni di efficienza computazionale e perché non dovrebbe dare problemi di sicurezza (almeno nei casi normali). Ma c’è anche un’altra modifica che è stata fatta negli anni, sempre per ridurre il costo computazionale (che nel caso della crittografia a chiave pubblica è molto più alto che nei sistemi di crittografia simmetrici).

Ricordo che nell’algoritmo RSA viene calcolato φ(n) = (p−1)(q−1), dove p e q sono i numeri primi di partenza, il cui prodotto è n, e φ(n) è la funzione φ di Eulero, cioè quanti sono i numeri minori di n e che non hanno fattori primi in comune con n. Nel nostro caso è facile calcolare il “toziente” (altro nome con cui è nota la funzione φ di Eulero), proprio perché p e q sono primi.

Non è però necessario usare φ(n) per scegliere un d tale che ed = 1 (mod φ(n)). È infatti sufficiente usare la funzione di Carmichael λ(n), definita come il più piccolo intero positivo m tale che a^m ≡ 1 (mod n) per ogni a coprimo con n. Si può dimostrare che λ(n) è un divisore di φ(n), e quindi è un numero più piccolo e pertanto le operazioni di computazione sono più brevi. Ma di quanto lo sono? Di un fattore MCD(p−1, q−1). Chiaramente entrambi i numeri sono pari e quindi c’è un fattore 2, ma si potrebbe sperare che ci sia qualcosa in più. John Cook ha fatto qualche prova, e ha trovato che su 100 coppie di numeri generati casualmente, la mediana del MCM è 2 (quindi in almeno metà dei casi il fattore è effettivamente 2); c’è stato un caso in cui si è arrivati a 2370, mentre il valore medio (poco utile in questo caso, perché a noi serve una sola coppia) è stato 35,44. In pratica, insomma, abbiamo quasi sempre 2 o 4 come fattore comune, In altri termini, se dobbiamo usare spesso una chiave può valer la pena di cercare una coppia di primi per cui λ(n) è effettivamente molto minore di φ(n), altrimenti possiamo far finta di niente.

Ultimo aggiornamento: 2025-11-05 15:33

Come probabilmente sapete, l’algoritmo RSA è uno dei più famosi algoritmi di crittografia a chiave pubblica: questo significa che chiunque può mandarci un messaggio cifrato, usando appunto la chiave pubblica, ma solo noi possiamo decodificarlo. L’algoritmo è tendenzialmente questo:

(a) Scegliamo due numeri primi molto grandi p e q.
(b) Calcoliamo n = pq e φ(n) = (p−1)(q−1).
(c) Scegliamo una chiave di crittazione e che sia un numero relativamente primo rispetto a φ(n). (La lettera “e” sta per “encryption”, se ve lo foste chiesti.)
(d) Calcoliamo la chiave di decrittazione d tale che ed = 1 (mod φ(n)).
(e) Pubblichiamo e e n, mantenendo segreti d, p e q.

La logica della crittografia RSA è che se conosciamo p e q possiamo calcolare “facilmente” n, φ(n) e d, ma non è possibile trovare d senza fattorizzare n, e almeno per il momento la fattorizzazione non è facile da fare, checché si dica delle meraviglie dei computer quantistici.

La cosa buffa è che di solito (pare nel 99,5% dei casi in un sondaggio compiuto da due ricercatori) i punti (b) e (c) si invertono: si sceglie prima e e poi si prendono i due primi, verificando che φ(n) sia primo rispetto a e. E soprattutto non si sceglie e a caso, ma si usa 65537. Come mai? John D. Cook lo spiega esaurientemente: è abbastanza grande perché φ(n) sia relativamente primo (se non lo è, bisogna trovare altri p e q) ed essendo uno più una potenza di 2 si risparmia sui calcoli. C’è addirittura chi ha usato e = 3, ma li si esagera. In realtà, continua Cook, usare un e troppo piccolo può far correre il rischio che qualcuno che ha accesso al computer dove sono stati fatti i conti riesce a trovare alcuni dei bit del numero, e in questo caso ci sono algoritmi più rapidi per decrittare a forza bruta. E scegliere un altro primo? Il punto è che e non è semplicemente una potenza di due più uno, ma un numero primo di Fermat: ne conosciamo solo 5 (3, 7, 17, 257, 65537), e anche se ce ne fosse un altro sarebbe così grande da risultare impraticabile…

Insomma, all’atto pratico abbiamo una semplificazione dell’algoritmo, visto che non scegliamo più e; ma la prossima volta vedremo che ce n’è un’altra.

Scrivendo il post di stamattina mi è venuto in mente un trucchetto che può permettervi di fare bella figura con poca fatica. Riuscite a calcolare a mente quant’è il 60% di 25?

Il calcolo è molto più semplice di quanto sembri a prima vista. Per definizione, una percentuale si calcola moltiplicando i due numeri presenti e dividento per 100, cioè 60×25/100 nel nostro caso. Questo equivale a 25×60/100, che è il 25% di 60. Ma il 25% è un quarto, quindi basta dimezzare due volte 60 e trovare il risultato che è 15. Semplice, no?

Vi siete mai chiesti come si suddividono i seggi in un sistema proporzionale? Un metodo abbastanza comune è quello dei resti. Se hanno votato 10000 persone e ci sono 15 seggi, si comincia a fare la divisione, ottenendo un quoziente di 666 e 2/3. Si dividono ora i voti presi dai partiti per quel quoziente, e si comincia ad attribuire un seggio per ogni quoziente. Tipicamente a ciascun partito avanzeranno dei voti, i “resti”; e parallelamente ci saranno dei seggi non assegnati: questi seggi verranno distribuiti ai partiti che hanno i resti più alti. Il metodo è a prima vista equo, ma non è proprio così: potrebbe darsi che assegnando un seggio in più in totale ci sia un partito che ne prenda uno in meno. Questo è il cosiddetto paradosso dell’Alabama: ne avevo parlato tanti anni fa sul Post, e qui trovate una copia di quel post. Vi svelo subito che non c’è un metodo perfetto per suddividere i seggi, ed è per questo che sono stati proposti vari sistemi.

Uno di questi, che ha avuto molta fortuna in Europa – in Italia lo si usava per le elezioni al Senato fino al 1992, e ancora adesso i seggi di minoranza nei consigli comunali si assegnano in quel modo – è il metodo d’Hondt, che prende il nome dallo studioso belga che l’ha formalizzato. In questo caso si prendono i voti ottenuti dai vari partiti e li si divide per 1, 2, 3, 4, … fino al numero n di seggi da assegnare (in genere non serve andare così avanti). Si prendono quindi gli n valori più alti, a cui sarà assegnato un seggio. Facciamo un esempio pratico. Abbiamo quattro partiti (A, B, C, D) che si contendono otto seggi. I voti totali sono stati 23000, e i singoli partiti hanno ricevuto rispettivamente 10000, 8000, 3000 e 2000 voti. La tabella che si costruisce è la seguente, dove per semplicità ho saltato le ultime colonne inutili:

$$
\begin{matrix}
\textrm{partito} & 1 & 2 & 3 & 4 & 5 & \textrm{seggi} \\
A & \bf{10000} & \bf{5000}& \bf{3333.3} & \bf{2500} & 2000 & 4 \\
B & \bf{8000} & \bf{4000} & \bf{2666.6} & 2000 & 1600 & 3 \\
C & \bf{3000} & 1500 & 1000 & 750 & 600 & 1 \\
D & 2000 & 1000 & 666.6 & 500 & 400 & 0 \\
\end{matrix}
$$

Il metodo d’Hondt non soffre del problema del paradosso dell’Alabama, ma in compenso indebolisce i partiti minori. Con i resti, infatti, il quoziente sarebbe stato 23000/8 = 2875 e avremmo avuto il seguente risultato: un seggio è stato spostato dal partito A al D.

$$
\begin{matrix}
\textrm{partito} & \textrm{voti} & \textrm{quoziente} & \textrm{resto} & \textrm{seggi} \\
A & 10000 & 3 & 1375 & \bf{3} \\
B & 8000 & 2 & \bf{2250} & \bf{3} \\
C & 3000 & 1 & 125 & \bf{1} \\
D & 2000 & 0 & \bf{2000} & \bf{1} \\
\end{matrix}
$$

Quello che non sapevo, e ho scoperto da questo articolo – ma Wikipedia lo diceva già… – è che un sistema equivalente era stato ideato da Thomas Jefferson e proposto a George Washington quando il presidente degli Stati Uniti d’America era quest’ultimo e non il primo. Jefferson divideva i voti ottenuti dai vari partiti per un numero, che chiamava “quota”, e prendeva i quozienti. Come nella fiaba di Riccioli d’oro, c’erano le quote troppo grandi, che non permettevano di assegnare tutti i seggi: nel nostro esempio, una quota di 3000 dà come risultato (3, 2, 1, 0) per un totale di 6 seggi assegnati. C’erano poi le quote troppo piccole: una quota di 2000 dà come risultato (5, 4, 1, 1) per un totale di 11 seggi. E infine c’erano le quote proprio giuste, come 2500 che dà come risultato (4, 3, 1, 0). Ecco dunque la ripartizione dei seggi: si prende la più grande quota che dia una suddivisione esatta dei seggi a disposizione.

Ma perché i due metodi sono esattamente gli stessi? Ci ho dovuto pensare un attimo, ma la cosa è davvero banale: se facciamo scendere man mano la quota, il valore finale di Jefferson è per definizione il primo per cui viene allocato l’ultimo seggio a disposizione. (nel nostro esempio al partito A, ma potrebbe essere uno qualunque). Ma dire con Jefferson che 10000/2500 = 4 è la stessa cosa che dire come d’Hondt che 10000/4 = 2500, no? E a questo punto tutti gli altri valori si ottengono automaticamente, perché aumentare o diminuire il numero di seggi agli altri partiti cambierebbe automaticamente il valore della quota.

Dobbiamo insomma cambiare nome al metodo d’Hondt? Secondo me no. Esso è sicuramente molto più facile da implementare di quello di Jefferson, e soprattutto quando i conti si dovevano fare a mano era fattibile. Insomma, teniamocelo così!

Ultimo aggiornamento: 2025-10-22 12:32