Una delle caratteristiche più sorprendenti, almeno per me, dei numeri naturali è il teorema di fattorizzazione unica. Nulla ci potrebbe fare immaginare a priori che un qualunque numero (e ce ne sono infiniti!) potrà sempre essere scritto in unico modo come prodotto di elementi di un insieme anch’esso infinito ma molto più “piccolo”: i numeri primi, i mattoni con cui si formano i numeri per mezzo della moltiplicazione. Certo, il fatto che possiamo moltiplicare il numero per 1 quante volte vogliamo ci rovina un po’ la festa; anzi, ce la rovina così tanto che a un certo punto i matematici hanno deciso di eliminare 1 dall’elenco dei numeri primi, mettendolo in una categoria a parte: quella delle unità, o se preferite degli invertibili. In effetti 1 è l’unico numero naturale il cui inverso è ancora un naturale: ed è questo che gli permette di essere presente in un numero di copie a piacere: tutte le volte che ce n’è uno basta moltiplicare anche per il suo inverso (che in questo caso è sempre 1) ed è come se non avessimo fatto nulla. In effetti se al posto dei numeri naturali usiamo gli interi succede che all’unità 1 si aggiunge il suo opposto -1 ma la fattorizzazione unica resta, mentre se passiamo ai numeri razionali, dove tutti gli elementi tranne 0 sono invertibili, non ha senso parlare di fattorizzazione.

Potrmmmo chiederci cosa succede se ampliamo la definizione di interi: sempre con una difficoltà geneale a trovare un inverso, ma su insiemi più ampi dei numeri interi. Il primo candidato che viene in mente è il campo dei numeri complessi, dove potremmo prendere i numeri della forma $a + bi$ dove $a$ e $b$ sono numeri interi. Questi numeri si chiamano interi di Gauss, l’insieme relativo si indica come $\mathbb{Z}[i]$ oppure $\mathbb{Z}[-1]$, dove si prender il numero tra parentesi quadre, si fa la sua radice quadrata e lo si aggiunge alla struttura numerica di $\mathbb{Z}$, e giocano appunto nel campo dei complessi lo stesso ruolo che gli interi giocano tra i reali. Cosa succede con questi numeri, almeno per quanto riguarda la fattorizzazione? Per esempio, 2 non è un numero primo: infatti è il prodotto $(1+i)(1-i)$. Anzi, è addirittura un quadrato: infatti i numeri invertibili negli interi di Gauss sono $1, -1, i, -i$ e abbiamo $i(1-i)^2 = 2$. Perché ci sono solo quei quattro invertibili? Semplice. Sappiamo che l’inverso di un numero complesso $a + bi$ ha a denominatore la sua norma $|a^2 + b^2|$, e l’unica possibilità per cui la norma sia 1 è che uno tra $a$ e $b$ valga 1 e l’altro valga 0. In compenso, 3 continua a non avere divisori, e quindi è un numero primo di Gauss (d’accordo, la fantasia nei nomi è poca). Ci sono poi numeri primi anche tra gli immaginari e i complessi: $3i$ è primo, perché il prodotto di un invertibile per un numero primo, e $1-i$ è anch’esso primo. Nella figura in cima alla pagina vedete una rappresentazione grafica dei primi di Gauss “piccoli”.

In definitiva, un intero di Gauss $a + bi$ è un primo di Gauss se:

• è un numero reale o immaginario puro, e il suo valore assoluto è un numero primo della forma $4k = 3$;
• è $\pm 1 \pm i$;
• $a$ e $b$ sono entrambi non nulli e $a^2 + b^2$ è un nuemro primo (e quindi della forma $4k + 3$.

In definitiva, pare che il concetto di numero primo sia comunque qualcosa di naturale anche se passiamo da una a due dimensioni numeriche. Sarà proprio vero?

Immagine di Dr Zibu, da Wikimedia Commons)

Ultimo aggiornamento: 2024-05-22 10:24

Quanti conti dovete fare per rispondere a queste domande? Ve le riporto direttamente nel testo:

Se 5/17 è 0,(2941176470588235), scrivete le seguenti frazioni come numeri decimali periodici:
– 12/17
– 1/34
– 27/34

Prendetevi un momento di tempo prima di continuare a leggere, ma non prendete carta e penna (e tanto meno una calcolatrice, che tanto non vi darebbe tutte le cifre volute! Se non lo sapeste, la notazione decimale con una parte tra parentesi indica che quello è il periodo della frazione.

Continua a leggere→

Domani l’idraulico passerà da me per una riparazione abbastanza urgente. Mi ha assicurato che arriverà in un qualche momento tra le 8 del mattino e le 4 del pomeriggio: a differenza del tipico idraulico posso essere certo che manterrà la parola. Mia moglie ha scommesso con me una settimana di pulizie in casa se l’idraulico arriverà prima o dopo mezzogiorno. In questo momento le mie probabilità a favore e contro sono le stesse; ma domani a una qualunque ora dopo le 8 del mattino, se l’idraulico non è ancora arrivato, la probabilità che arrivi di pomeriggio è maggiore, visto che l’intervallo di tempo è rimasto più ampio. Ma allora mi conviene direttamente puntare sul pomeriggio già adesso! Ma non avevo detto che era irrilevante per ora scegliere tra mattino e pomeriggio?

Questo paradosso è stato presentato nel 2005 da Alan Hájek in un paper intitolato “The Cable Guy paradox”. Il paradosso indubbiamente c’è, perlomeno se assumiamo che l’idraulico non arrivi alle 8 spaccate. In effetti, se arrivasse qualche millesimo di secondo dopo le 8 i miei neuroni probabilmente non sarei ancora riuscito a concepire il pensiero “adesso è meglio scegliere il pomeriggio” quindi potremmo dire che il paradosso sarebbe risolto: ma sappiamo che in questi problemi dobbiamo assumere una posizione molto teorica e distante dal mondo reale. In compenso, dice sempre Hájek, se mi dessero un incentivo per quanto piccolo se scegliessi il mattino allora in questo momento mi converrebbe farlo, salvo poi pentirmene amaramente dopo poco tempo (anche se magari poi vincerei lo stesso perché l’idraulico è arrivato alle 11:40).

Ma allora come si risolve il paradosso? Non lo si risolve. Hájek sostiene che il problema è psicologico: si sceglie il pomeriggio per evitare la frustrazione. Io – che comunque la frustrazione preferisco evitarla eccome! – parto semplicemente dal principio che non devo passare il tempo davanti all’orologio. Se stasera partissi, ingiungendo a mia moglie di non dirmi nulla fino a domani sera, potrei scegliere mattino o pomeriggio senza preoccuparmi; eppure le informazioni sono le stesse!
E voi che ne pensate?

(immagine di snoopingasusual, da OpenClipArt)

Negli anni ’90 del secolo scorso i personal computer cominciavano a essere una presenza usuale, e spuntavano i primi giochi grafici: il guaio è che per avere della bella grafica occorre fare tanti conti e la potenza di quei computer non era certo quella attuale, soprattutto se si dovevano usare le operazioni in virgola mobile e non quelle con gli interi. Occorreva dunque inventarsi i più strani metodi per eseguire le operazioni più complicate: ma l’algoritmo per la radice quadrata inversa veloce ha battuto ogni record.

Per prima cosa, che significa “Radice quadrata inversa”? È l’operazione che da x ottiene x^−½, cioè l’inverso della radice quadrata di x. Naturalmente “veloce” significa che l’algoritmo usato è più veloce di quello standard, probabilmente legato all’iterazione con il metodo di Newton a partire da una approssimazione. La prima implementazione per la radice quadrata inversa veloce prevedeva una tabella precompilata di dati da cui partire e migliorare il risultato approssimato; ma anche lo spazio a disposizione non era poi troppo. L’algoritmo che secondo Wikipedia fu ideato alla Silicon Graphics non aveva invece bisogno di una tabella, ma solo di una costante magica: 0x5f3759df. Come funzionava questo algoritmo? Si prendeva il numero x (float a 32 bit), e si salvava la sua metà x2 = x/2 per dopo. Poi si prendeva x, lo si leggeva come se la successione di bit rappresentasse un intero, si faceva uno shift logico a sinistra di una posizione (il primo bit veniva buttato via, gli altri scalavano di una posizione a sinistra, e si metteva uno zero in fondo), si sottraeva questo numero dalla costante magica e si leggeva il risultato y come fosse un float. Seguiva un’iterazione dove y veniva ricalcolato come 1,5 − (x2 × y²). Tutto qua.

Ma come è stata trovata questa costante? Non ho avuto voglia di leggermi tutta questa tesina, lo ammetto :-) Tanto ormai le CPU calcolano in virgola mobile a una velocità incredibile…

No, niente sesso. Molto più banalmente, calcolate l’area della parte colorata di questo triangolo.

Come racconta Presh Talwalkar, l’area colorata è uguale all’area del triangolo grande, cioè 32,5 cm², meno quella del triangolo non colorato, che è 8 cm² (la sua altezza è 5−2 cm e la sua base 13−5 cm); in tutto dunque 24,5 cm². Ma possiamo anche calcolarla direttamente, come la somma delle aree dei due triangoli colorati: quello rosso ha area 20 cm², mentre quello verde ha area 5 cm². Totale: 25 cm². Dove abbiamo sbagliato i conti?? Da nessuna parte!

Il trucco è esattamente quello del quadretto mancante, che vedete qui a destra. In pratica, quello che sembra un triangolo non lo è perché le due linee diagonali hanno una pendenza leggermente diversa, ed è proprio quella diversità che porta ad avere una differenza di un quadretto se sovrapponessimo le due figure.

I lettori più interessati si saranno chiesti se è un caso che le misure che abbiamo nel problema sono dei numeri di Fibonacci. La risposta è ovviamente no, non è un caso; dati tre numeri di Fibonacci consecutivi $ F_{n-1}, F_n, F_{n+1} $ vale sempre la relazione $ (F_n)^2 = (F_{n-1})(F_{n+1}) \pm 1 $ , con i più e i meno che si alternano se $ n $ è pari o dispari.

Quando ho scritto Chiamatemi pi greco, ho mostrato una formula che permetteva di calcolare l’n-sima cifra esadecimale della nostra costante preferita senza dovere calcolare quelle precedenti. Terminavo scrivendo

Chissà, magari in futuro qualcuno troverà una formula simile in base 10… La cosa non è impossibile, e per qualche altra costante matematica una formula di quel tipo esiste davvero, ma almeno per il momento non pare che ci siano buone notizie su quel fronte.

Le bozze del libro mi sono arrivate il 28 gennaio 2022. Il giorno dopo Simon Plouffe, uno degli scopritori della formula che avevo citato, ha pubblicato un preprint dove ha mostrato una formula per trovare l’n-sima cifra decimale di π. Come indovino ho ancora qualche margine di miglioramento…

Potete vedere qui sotto (oltre che nella figura iniziale…) la formula in questione. Prima si definisce il numero

$ \pi_n = \left( \frac{2(-1)^{n+1}(2n)!}{2^{2n}B_{2n}(1-2^{-n})(1-3^{-n})(1-5^{-n})(1-7^{-n})} \right)^{1/(2n)} $

e poi si calcola l’n-sima cifra decimale di pi greco come

$ d_n = \textrm{int} ( 10 \textrm{ frac} (10^{n-1} \pi_{n-1})) $

dove int() e frac() calcolano rispettivamente la parte intera e frazionaria di un numero.

So che ve lo state chiedendo: i B_n sono i numeri di Bernoulli. Plouffe spiega che a partire dal decimo numero di Bernoulli l’approssimazione

$ \pi \approx \left( \frac{2n!}{B_n2^n} \right )^{1/n} $

per n pari è molto precisa. (Se n è dispari i numeri di Bernoulli tranne il primo valgono tutti zero, quindi non funzionano). Preso per esempio $ n = 1000 $, l’errore che si commette è minore di $ 2^{-1000} $. I prodotti che vedete a denominatore arrivano infine dall’approssimazione della zeta di Riemann, scritta come produttoria infinita usando la formula di Eulero. È noto (l’ha dimostrato Eulero) che $ \zeta(2n) $ è un multiplo razionale di $ \pi^{2n} $; sostituendo il valore e prendendo i primi quattro valori della produttoria si arriva al risultato mostrato in cima.

Tutto bello, in teoria: peccato che la formula richieda di computare i numeri di Bernoulli, e per farlo in genere si usano formule che partono da un’espressione con pi greco. Insomma questo risultato è carino, ma assolutamente inutile in pratica!