Se seguivate il mio vecchio blog sul Post (quando il Post aveva i blog…) sapete sicuramente della base di numerazione φ. Come in base 10 un numero come 42,5 equivale a 4×10¹ + 2×10⁰ + 5×10⁻¹, in base φ un numero come 1000.1001 equivale a φ³ + φ⁻¹ + φ ⁻⁴, che in base 10 equivale a 5. Ci sono molte rappresentazioni possibili per un numero in base φ; per convenzione si sceglie come forma canonica quella che non ha due cifre 1 consecutive (lo si può sempre fare, ricordando che $ \varphi^n + \varphi^{n+1} = \varphi^{n+2)}$).

Riguardo alla base φ, Richard Green segnala una curiosità, raccontata nel paper di Jeffrey Shallit e Ingrid Vukusic New properties of the φ-representation of integers. Consideriamo l’insieme degli interi che in base φ sono “antipalindromi”, dove cioè se c’è la cifra 1 in posizione $k$ c’è anche la cifra 1 in posizione $-k$. Per esempio, 1 è antipalindromo, perché $1_{10} = 1_{\varphi}$, e l’unica cifra 1 è in posizione 0 che è l’opposto di sé stessa; 2 non lo è, perché $2_{10} = 10,01_{\varphi}$ e anche se il numero pare simmetrico non lo è (le posizioni con 1 sono 1 e −2); 3 lo è perché $3_{10} = 100,01_{\varphi}$ e le posizioni con 1 sono la 2 e la −2. L’insieme dei numeri naturali che sono antipalindromi in base φ comincia con 1, 3, 4, 7, 8, 10, 11, 18, 19, 21, 22, 25, 26, 28, 29, 47, … e naturalmente si trova su OEIS, prendendo il nome di Vladimir Shevelev che l’ha studiato per primo nel 2010. Bene: due anni dopo Clark Kimberling si è accorto che i numeri nell’insieme di Shevelev avevano la proprietà che raddoppiando tutti gli esponenti nella sua notazione in base φ si otteneva un altro numero naturale, cosa che a prima vista non era ovvia: per esempio, 10 è $10100,0101+{\phi}$ e $10010000,00010001+{\phi}$ = 54. Allo stesso tempo, se un numero non è nell’insieme di Shevelev raddoppiando tutti gli esponenti non si ottiene un intero: per esempio 9 è $10010,0101_{\phi}$ mentre $10000100,00010001_{\phi} = (52 – \sqrt{5})_{10}$.

Bene: Shallit e Vukusic sono riusciti a dimostrare la congettura di Kinberling. La dimostrazione tra l’altro non è nemmeno troppo difficile. Hanno infatti sfruttato i numeri di Lucas (una variante dei numeri di Fibonacci, dove non si parte da {1,1} ma da {3,1} per la definizione ricorsiva) per dimostrare che i numeri antipalindromi sono tutti e soli quelli che hanno solo esponenti pari nella rappresentazione in base φ. Non so voi, ma tutto questo mi pare incredibile…

Ultimo aggiornamento: 2025-10-02 11:19

No, il maccartismo non c’entra. Questo McCarthy (John) è l’informatico che ha realizzato il Lisp, oltre che essere un pioniere dell’intelligenza artificiale. La “Funzione 91” è una funzione ricorsiva definita sugli interi in questo modo:

$$ M(n) = \left\{\begin{matrix} n – 10, & \mbox{se }n > 100\mbox{ } \\ M(M(n+11)), & \mbox{se }n \le 100\mbox{ } \end{matrix}\right. $$

Notate come la ricorsione non sia semplice, come per esempio nel caso del fattoriale che possiamo definire come $n! = n \times (n-1)!$ (e naturalmente $0! = 1$, per avere un punto in cui termina la ricorsione). Qui invece dobbiamo applicare due volte la definizione della funzione.

Chiaramente se $ n \gt 100 $ non ci sono problemi a calcolare $M(n)$: basta togliere 10. Anche per $n = 100$ facciamo in fretta: $ M(100) = M(M(100+11)) = M(M(111)) = M(101) = 91$. Il bello arriva quando proviamo a calcolare il suo valore per i numeri minori di 100. Proviamo per esempio con $ n = 42$: preparatevi a un ottovolante.

M(42) = M(M(42+11)) = M(M(53))
      = M(M(M(64))) 
      = M(M(M(M(75))))
      = M(M(M(M(M(86)))))
      = M(M(M(M(M(M(97))))))
      = M(M(M(M(M(M(M(108)))))))
      = M(M(M(M(M(M(98))))))
      = M(M(M(M(M(M(M(109)))))))
      = M(M(M(M(M(M(99))))))
      = M(M(M(M(M(M(M(110)))))))
      = M(M(M(M(M(M(100))))))
      = M(M(M(M(M(91)))))) (l'abbiamo visto sopra...)
      = M(M(M(M(M(M(102))))))
      = M(M(M(M(M(92))))))
      = M(M(M(M(M(M(103))))))
      = M(M(M(M(M(93))))))
      = M(M(M(M(M(M(104))))))
      = M(M(M(M(M(94))))))
      = M(M(M(M(M(M(105))))))
      = M(M(M(M(M(95))))))
      = M(M(M(M(M(M(106))))))
      = M(M(M(M(M(96))))))
      = M(M(M(M(M(M(107))))))
      = M(M(M(M(M(97))))))
      = M(M(M(M(M(M(108))))))

Toh. Avevamo già trovato $M(M(M(M(M(M(M(108)))))))$ con un livello di parentesi in più. Saltando un po’ di passaggi continuiamo con

M(42) =
      ...
      = M(M(M(M(M(M(M(108))))))) 
      ...
      = M(M(M(M(M(M(108))))))
      ...
      = M(M(M(M(M(108)))))
      ...
      = M(M(M(M(108))))
      ...
      = M(M(M(108)))
      ...
      = M(M(108))
      ...
      = M(98)
      = M(M(109))
      = M(99)
      = M(M(110))
      = M(100)
      = M(M(111))
      = M(101)
      = 91

È facile dimostrare per induzione (partendo dalla undicina $90 ≤ n \le 101$ e scendendo man mano di 11 in 11) che applicare $M$ a un qualunque numero intero minore di 100 porta a 91 (capito il perché del suo nome?). In pratica, la nostra funzione se ne sta piatta da meno infinito a 101, e poi diventa lineare. Strana, no?

Aggiungo solo che la funzione è usata come test per verificare i programmi automatici di verifica del software, proprio per la sua struttura così strana.

Ultimo aggiornamento: 2025-09-25 21:47

John D. Cook mostra alcuni metodi per generare punti casuali all’interno di un triangolo ABC dato. Possiamo immaginare di lavorare in coordinate cartesiane, per semplicità, e quindi avere A, B e C come coppie ordinate di valori.

Il metodo più semplice è quello di usare coordinate baricentriche: generate tre numeri casuali α, β e γ tra 0 e 1, normalizzateli per far sì che la loro somma sia 1, e date come risposta αA + βB + γC. Il metodo genera punti che stanno tutti all’interno del triangolo: ma non sono uniformi, come si vede dalla figura qui sotto presa dal blog di Cook. I punti centrali del triangolo sono più probabili di quelli vicino ai vertici.

Il secondo metodo è quello del rejection sampling. Costruite il rettangolo circoscritto al triangolo, generate due numeri casuali per la coordinata x e quella y, e controllate se il punto corrispondente sta all’interno del triangolo: se sì, bene, altrimenti lo buttate via. È evidente che in questo modo i punti generati e accettati sono distribuiti in modo casuale, perché tutti quelli nel rettangolo lo sono: il costo computazionale è di due insiemi di operazioni per numero scelto.

C’è poi un terzo metodo, quello del parallelogramma. Costruite un parallelogramma aggiungendo al triangolo una sua versione speculare, e generate punti a caso al suo interno, con la formula P = A + r₁·(B-A) + r₂·(C-A) dove r₁ e r₂ sono numeri casuali in [0,1]. Ora, se il punto generato si trova nel triangolo di partenza, e quindi r₁ + r₂ ≤ 1, bene; altrimenti prendete la sua immagine riflessa nel triangolo di partenza, usando (1-r₁, 1-r₂). Di nuovo, la casualità è assicurata. Il tutto è raccontato anche su Stack Overflow.

Quale conviene tra il secondo e il terzo metodo? Dipende. Se siete fanatici e sapete dove cercare – oppure siete molto intelligenti e l’avete trovato da soli – il parallelogramma è la scelta migliore. Ma se avete fretta di implementare una soluzione e dovete generare poche centinaia di punti il rejection sampling va più che bene: il costo è il doppio dell’altro metodo, e quindi sopportabile.

Due ultime note: nei commenti al post di Cook si fa notare come scegliere una distribuzione esponenziale anziché lineare dei numeri casuali fa funzionare anche il metodo delle coordinate baricentriche. Ma soprattutto ho provato a fare la domanda a Claude. Riporta i tre metodi (immagino perché addestrato su Stack Overflow) ma afferma che quello delle coordinate baricentiche è il metodo più elegante ed efficiente. Mai fidarsi degli LLM!

Come si può misurare la lunghezza di un arco di circonferenza? Semplice: si misura l’angolo al centro relativo e il raggio della circonferenza e si fa la proporzione, sapendo che tutta la circonferenza ha ovviamente lunghezza $2πr$.

Nel libro del 1803 di Peter Nicholson Carpenter’s New Guide viene però data una costruzione approssimata. Dato l’arco (non troppo grande) $\overset{ \huge\frown}{AB}$, si divida in quattro parti il segmento $AB$ con i punti $C_1, C_2, C_3$ come in figura. Se la circonferenza di centro $A$ che passa per $C_1$ interseca l’arco dato in $D$, allora il segmento $C_3D$ è approssimativamente lungo la metà dell’arco. Nicholson avverte che questa costruzione si può usare solo per archi inferiori a un quadrante.

In questo caso, come nel 1981 ha mostrato il matematico britannico Ian Cook, l’errore massimo che si commette è dello 0,6%, che per un carpentiere è ampiamente all’interno delle tolleranze ammesse. Il tutto senza goniometri. Niente male, no?

(fonte: Futility Closet)

Non avevo mai sentito parlare di questa funzione, il cui nome completo è “term frequency–inverse document frequency”. Eppure è una funzione del tutto naturale nel caso si voglia trovare documenti “simili” a quello di partenza in una collezione di testi.

L’idea sottostante è a posteriori ovvia. Se ho un documento in cui una parola appare molto spesso, altri documenti in cui questa parola compare spesso dovrebbero essere simili. Ma ci accorgiamo subito che questa euristica non funziona: connettivi come “che”, “perciò” oppure articoli e forme dei verbi ausiliari appariranno spesso in praticamente ogni documento. La funzione tf-idf relativa a una parola P tiene conto di tutto questo: è direttamente proporzionale alla probabilità che P appaia nel testo, ma inversamente proporzionale alla probabilità che P appaia nella collezione completa di testi. In altri termini, la funzione assume un valore tanto maggiore quanto la parola è in genere meno usata rispetto a quanto lo sia nel testo iniziale; una parola usata sempre più o meno allo stesso modo ha i due fattori che si elidono a vicenda.

In formule, abbiamo che tf-idf è il prodotto di due funzioni: tf, la frequenza del termine nel nostro documento, e idf, l’inverso della frequenza in tutti i documenti. Più precisamente,

$$\mathrm{tf_{i,j}} = \frac{n_{i,j}}{|d_j|},$$

dove $n_{i,j}$ è il numero di occorrenze del termine $i$ nel documento $j$ e il denominatore (il numero di parole nel documento) serve per perequare i valori per i documenti di lunghezza variabile, e

$$\mathrm{idf_{i}} = \log_{10} \frac{|D|}{|\{d: i \in d\}|},$$

dove $|D|$ è il numero di documenti nella collezione e al denominatore c’è il numero di documenti che contengono il termine $i$. (Per definizione ce n’è almeno uno, altrimenti non calcoleremmo idf, e quindi il denominatore non può mai essere nullo).

Il tutto funziona? Diciamo che funzionicchia. Già il concetto di idf è più euristico che altro, perché applica la legge di Zipf che come sappiamo non è scolpita nel granito; e visto che a quanto pare le raccomandazioni di libri simili nelle librerie online pare basarsi anche su tf-idf direi che ci sono ampi margini di miglioramento. Secondo Wikipedia in inglese la formula è stata anche applicata in altri campi, con risultati deludenti. Però è sempre meglio una cattiva formula che nessuna formula, e spesso si può usare il sistema “al rovescio”, per esempio cercando di scoprire se alcune delle lettere paoline siano o no state effettivamente scritte dall’apostolo. L’idea è che in questo modo brutale non si può riconoscere lo stile ma almeno si verifica che la terminologia non sia cambiata troppo, e si ha un punteggio numerico e non una sensazione come si faceva un tempo. Insomma, è comunque una freccia all’arco dei filologi.

Sappiamo che un numero è perfetto se è la somma dei suoi divisori propri. Per esempio, 496 è perfetto perché 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 = 496. Prendiamo ora il numero 10311: la somma dei suoi divisori è 1 + 3 + 7 + 21 + 491 + 1473 + 3437 = 5433 ≠ 10311. Ma se scriviamo questi divisori da destra a sinistra, otteniamo 7343 + 3741 + 194 + 12 + 7 + 3 + 1 = 11301 che è appunto 10311 scritto alla rovescia.

Numeri come questo si chiamano “Picture perfects numbers”, che io traduco come “numeri perfetti allo specchio”, e sono così poco noti che non hanno nemmeno una voce su Wikipedia in inglese :-), anche se OEIS ha una successione con l’elenco dei (sette…) numeri perfetti allo specchio conosciuti: 6, 10311, 21661371, 1460501511, 7980062073, 79862699373, 798006269373.

Una curiosità: Jens Kruse Andersen ha scoperto che se il numero p = 140z10n89 è primo, dove z è una stringa (anche nulla) di zero e n un’altra stringa (anch’essa eventualmente nulla) di 9, allora 57p è un numero perfetto allo specchio. Peccato che non si siano mai trovati numeri primi di questa forma…

Ultimo aggiornamento: 2025-08-27 22:35

Una corrente filosofica della matematica, l’intuizionismo, afferma che non possiamo usare l’infinito nei nostri teoremi, perché non potremmo mai ottenerlo. Un corollario di questa affermazione è che almeno ad oggi (e probabilmente per sempre, ma chi lo può sapere?) non possiamo dire “nello sviluppo decimale di pi greco c’è una successione di 1000 cifre 0 consecutive, oppure tale successione non c’è”: in altre parole, il principio del terzo escluso vale solo quando abbiamo un numero finito di possibilità, e quindi in linea di principio possiamo controllarle a una a una. Non sono moltissimi i matematici che seguono tale corrente, principalmente perché le cose che si possono dimostrare sono molte di meno: ma comunque è una posizione rispettata.

Leggo però da New Scientist che esiste una corrente filosofica ancora più talebana: gli ultrafinitisti. Per costoro, non solo l’infinito non esiste, ma non esistono nemmeno i numeri “troppo grandi”, nel senso di quelli che non potremo mai computare nemmeno in linea di principio, data la finitezza del nostro universo. Attenzione: questa teoria è del tutto diversa da quella del “grossone” di Yaroslav Sergeyev, dove si dà un valore specifico – diciamo N – all’infinito ottenuto con tutti inumeri naturali e a questo punto possiamo per esempio dire che i numeri pari sono N/2. Gli ultrafinitisti non solo non ammettono l’esistenza del grossone, ma affermano che non esiste nemmeno la parte intera del primo numero di Skewes, che è exp(exp(exp(79))). Questo numero non potremo mai calcolarlo non dico esattamente ma con una precisione inferiore all’unità, quindi la sua parte intera non esiste.

Detto tutto ciò, e aggiunto che credo che siano i fisici i più interessati, termino notando che anche Wikipedia segnala che le fondazioni dell’ultrafinitismi sono troppo vaghe per ottenere qualcosa di davvero utile…

Cominciamo con qualcosa di facile. Prendiamo i numeri naturali:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …
Cancelliamo ora ogni secondo numero:
1, 3, 5, 7, 9, 11, 13, …
Facciamo infine le somme parziali:
1, 4, 9, 16, 25, 36, 49, …
Abbiamo così ottenuto la successione dei quadrati perfetti. Nulla di strano: sappiamo che i quadrati sono la somma dei numeri dispari, lo si vede disegnando gli gnomoni.

Ma ora andiamo più in là. Ripartiamo dai numeri naturali:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …
ma stavolta togliamo ogni terzo numero:
1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, …
Facciamo anche stavolta le somme parziali:
1, 3, 7, 12, 19, 27, 37, 48, 61, 75, 91, 108, 127, 147, …
Togliamo ogni secondo numero:
1, 7, 19, 37, 61, 91, 127, …
E rifacciamo infine le somme parziali:
1, 8, 27, 64, 125, 216, 343, …
Abbiamo ottenuto la successione dei cubi!

Come arrivare alle quarte potenze? Semplice: aggiungiamo come passo iniziale quello di eliminare ogni quarto numero prima di sommare.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 , …
1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, …
1, 3, 6, 11, 17, 24, 33, 43, 54, 67, 81, 96, …
Ora si fa il passaggio di cancellare ogni terzo numero e poi fare le somme parziali:
1, 3, 11, 17, 33, 43, 67, 81, …
1, 4, 15, 32, 65, 108, 175, 256, …
E finalmente si cancella ogni secondo numero e si fanno ancora una volta le somme parziali:
1, 15, 65, 175, …
1, 16, 81, 256, …
Et voilà!

Questa struttura aritmetica è stata trovata da Alfred Moessner, che nel 1951 scrisse un articolo intitolato “Eine Bemerkung über die Potenzen der natürlichen Zahlen” (un’osservazione delle potenze dei numeri naturali) e dimostrato lo stesso anno da Oskar Perron. Non so chi abbia deciso di chiamarlo “la magia di Moessner”, e non più banalmente il teorema di Moessner – nome comunque usato, come si vede su Wikipedia – ma secondo me un po’ di magia c’è davvero…

PS: se si eliminano i numeri triangolari, si ottiene invece la successione dei fattoriali!