Come ho già menzionato, ho scoperto con non poca sorpresa che a scuola non insegnano piú la prova del nove, e benché la pagina Wikipedia dica già tutto quello che c'è da dire, ho deciso di inaugurare proprio con questa la mia serie sulla “scuola dimendicata”.

Cos'è

Cos'è quindi la prova del nove? È un meccanismo semplice e veloce per verificare la correttezza di un'operazione. La verifica non è completa (nel senso che non coglie alcuni errori: ha falsi positivi), ma se fallisce siamo sicuri di aver commesso uno sbaglio (non ha falsi negativi).

Come funziona

La prova del nove funziona sommando tra loro le cifre di ciascun operando, eliminando i 9, fino ad ottenere due numeri ad una cifra (riduzione che rappresenteremo con il simbolo $\equiv$). Se l'operazione tra questi operandi ridotti dà un risultato diverso dalla riduzione del risultato originale, abbiamo commesso un errore, altrimenti il risultato è probabilmente giusto (ma potrebbe essere comunque sbagliato).

Esempio

Abbiamo provato a calcolare $1024\times 768$ e ci è venuto $785432$.

Come prima cosa, riduciamo gli operandi ed il risultato.

Riduzione di 1024:

$$1024\equiv 1+0+2+4=1+2+4=3+4=7.$$

Riduzione di 768 (qui sfruttiamo il fatto che possiamo fare riduzioni parziali intermedie, trasformando il $13$ in $1+3=4$):

$$768\equiv (7+6)+8=13+8\equiv 4+8=12\equiv 3.$$

Riduzione di 785432 (qui sfruttiamo il fatto che nelle riduzioni parziali possiamo direttamente eliminare 0 e 9):

$$785432\equiv (7+8)+5+4+(3+2)=15+5+(4+5)=20+9\equiv 2.$$

(Notate come avremmo potuto anche continuare $20+9=29\equiv 11\equiv 2$, facendo però piú operazioni.)

Se moltiplichiamo i nostri operandi ridotti otteniamo $7\times 3=21$, che ridotto ulteriormente viene $3$: sappiamo quindi che abbiamo commesso un errore, perché la riduzione del risultato ($2$) è diversa dal risultato applicato agli operandi ridotti ($3$). La prova ci dice anzi qualcosa di piú: probabilmente l'errore che abbiamo commesso è una sottostima di una delle cifre, poiché $2<3$. (Il risultato corretto della moltiplicazione è infatti $786432$, non $785432$.)

Rappresentazione

Convenzionalmente, la prova del nove viene rappresentata in uno schemino con quattro numeri “in croce”: si traccia una croce (＋), nelle caselle superiori si mettono le riduzioni degli operandi, in quella in basso a sinistra la riduzione del risultato, ed in quella in basso a destra il risultato ottenuto operando sulle riduzioni:

Alle quattro operazioni

La prova del nove può essere applicata ad addizione, moltiplicazione, sottrazione e divisione. Per le due operazioni inverse (sottrazione e divisione) conviene però applicarla al contrario.

Invece di verificare una sottrazione, verificate se la somma della riduzione di differenza e sottraendo vi dà la riduzione del minuendo. Ad esempio per verificare se $1024-768=256$ (ridotti: $7-3=4$) controllate se $256+768=1024$ (ridotti: $4+3=7$).

Questo è particolarmente importante per la divisione con resto. Abbiamo infatti che $2048:768=2$ con resto $512$, ma se facciamo l'operazione sulle riduzioni degli operandi ($5:3$) otteniamo $1$ con resto di $2$, che sembrerebbe indicare un errore1, mentre se verifichiamo che $768\times 2+512=2048$ in forma ridotta abbiamo

$$3\times 2+8=6+8=14=5,$$

che corrisponde alla riduzione del dividendo $2048$.

Nessuno è perfetto

Si può sbagliare anche nella prova del nove. Errare è umano, e anche sommando tanti numeri piccoli si può sbagliare. Ad esempio, mentre scrivevo il paragrafo di esempio sulla moltiplicazione avevo inizialmente sbagliato a fare la riduzione del risultato, ed ero arrivato ad una riduzione di $5$: in questo caso avrei comunque osservato una discrepanza, ma sarebbe stato un caso (e mi sono accorto dell'errore perché avendo costruito io l'esempio sapevo già che la riduzione del risultato errato doveva darmi $2$, avendo intenzionalmente cambiato una cifra in difetto).

Quindi in caso di discrepanza, come prima cosa ricontrollate le riduzioni! Sono piú facili da ricontrollare dell'operazione originale (soprattutto nel caso della moltiplicazione).

Ma soprattutto, ricordatevi che la prova del nove non trova tutti gli errori. Se avessimo sbagliato la nostra moltiplicazione ottenendo $768432$ invece del risultato corretto $786432$, non ci saremmo accorti di aver sbagliato, poiché:

$$7+6+8+4+3+2=7+8+6+4+3+2,$$

per la proprietà commutativa dell'addizione.

BONUS: la prova dell'undici

Esiste una prova simile alla prova del nove, e che non insegnavano a scuola nemmeno ai miei tempi, che è la prova dell'11.

Se vi ricordate il criterio di divisibilità per 9, questo consisteva nel sommare tutte le cifre, ripetutamente, fino ad ottenere un numero che fosse un multiplo di 9, o per il quale fosse facile verificare che non era un multiplo di 9. Il parallelo tra il criterio di divisibilità per 9 e la riduzione dei numeri nella prova del nove non è un caso, ed è legata all'aritmetica modulare, che sta alla base della prova e che non andrò qui a spiegare.

Piuttosto, se vi ricordate, esiste anche un criterio di divisibilità per 11, che consiste nell'alternare somme e differenze, partendo dalla cifra meno significativa: bene, sulla stessa falsariga si può fare una prova dell'undici.

Torniamo al nostro esempio di $1024\times 768$. In questo caso le nostre riduzioni vanno fatte in questa maniera alternata, e bisogna ricordarsi, nel caso in cui un numero venga negativo, di prendere il suo complementare con (ovvero aggiungere) $11$.

La riduzione di $1024$ è $4-2+0-1=4-3=1$.

La riduzione di $768$ è $8-6+7=2+7=9$.

Il prodotto dei numeri ridotti è $1\times 9=9$.

La riduzione di $785432$ è2:

$$785432\equiv 2-3+4-5+8-7=14-15=-1\equiv 10,$$

dove abbiamo applicato la correzione per il numero negativo. Sapevamo già che questo risultato era sbagliato dalla prova del nove, e questo lo conferma.

La riduzione del risultato corretto $786432$ è:

$$786432\equiv 2-3+4-6+8-7=14-16=-2\equiv 9,$$

che corrisponde al prodotto dei fattori ridotti.

Infine, se controlliamo la riduzione del risultato errato $768432$, che la prova del nove dava come falso positivo, abbiamo:

$$768432\equiv 2-3+4-8+6-7=12-18=-6\equiv 5,$$

che è diverso dal prodotto dei fattori ridotti: la prova dell'undici riconosce un errore che la prova del nove non può riconoscere.

Quale prova?

Esistono errori che la prova del nove trova e la prova dell'undici non trova?

Tecnicamente è possibile: può succedere ad esempio se sbagliamo due cifre consecutive (o comunque una di posto pari ed una di posto dispari) della stessa quantità. Un esempio di risultato errato che il 9 trova e l'11 no è il seguente, costruito “ad arte”:

Prendiamo $11\times 171=1771$ invece del corretto $1881$.

Nella prova del nove abbiamo: $2\times 0=0$ e $1771$ riduce a $7$, quindi sappiamo che è sbagliato.

Nella prova dell'undici, la riduzione di $11$ è 0, e la riduzione di $171$ è $1-7+1=-5\equiv 6$, quindi abbiamo: $0\times 6=0$, ma la riduzione di $1771$ è $1-7+7-1=0$: la prova dell'undici non trova l'errore.

Detto questo, è molto difficile che errori simili si verifichino in calcolo manuali, per cui alcuni considerano la prova del nove “superflua” avendo a disposizione la prova dell'undici, che trova piú errori “comuni” di quella del nove.

D'altra parte, è anche vero che la prova del nove è molto piú semplice (tutte somme, non bisogna alternare con il segno, non bisogna “correggere” eventuali risultati negativi, è facile eliminare i 9); e questo è il motivo per cui la prova del nove veniva insegnata a scuola, ai miei tempi fin dalle elementari, senza dovercisi preoccupare di spiegare i numeri negativi o l'aritmetica modulare.

Quesito

Primus inter pares

Risposta

Il numero due

Introduzione

In risposta ad un sondaggio semiserio che chiedeva quanti venti si conoscessero, ho fatto un mio sondaggio ancora meno serio su quanti “venti” si conoscessero; per limiti della piattaforma (Mastodon) su cui ho il mio account, il sondaggio prevedeva solo quattro possibili risposte, a cui ho poi aggiunto altri due “pezzi” del sondaggio (a risposta multipla), portando il numero di possibili risposte a dodici:

• 14
• 20
• 24
• XX
• 10100
• 202
• 1T1T
• 1000010.010001
• 40
• 1T0
• 26
• 3T

Di queste, tutte hanno ricevuto almeno una risposta, con l'eccezione di $1000010.010001$ e $3T$. In molti hanno “capito” il gioco, e qualcuno ha anche “svelato” il segreto (dietro opportuna copertura), ma ritengo sia opportuna una mia spiegazione.

Il gioco consisteva nello scrivere il numero venti in tanti modi diversi, e capire come fosse scritto. I modi proposti possono essere grossolanamente raccolti in quattro gruppi, che richiedono ciascuno la sua spiegazione:

1. il primo gruppo ha come unico membro la forma: XX
2. il secondo gruppo ha come membri: 14, 20, 24, 10100, 202, 40, 26
3. il terzo gruppo ha come membri: 1T1T, 1T0, 3T
4. il quarto gruppo ha come unico mebro: 1000010.010001

Andiamoli dunque a vederli in dettaglio.

Primo gruppo: i numeri romani

Immagino che per il mio pubblico italiano non avrò particolare bisogno di “spendermi” sul sistema di numerazione romano.

Brevemente, ricordo che esso è composto dai simboli

I, V, X, L, C, D, M

o piú propriamente

Ⅰ, Ⅴ, Ⅹ, Ⅼ, Ⅽ, Ⅾ, Ⅿ

se avete un font che supporta abbastanza Unicode (ed è possibile che non vediate la differenza), del valore rispettivamente di uno, cinque, dieci, cinquanta, cento, cinquecento, mille.

Gli altri numeri sono composti per “accostamento”, con fino a 3 simboli uguali consecutivi (in realtà, si trovano anche scritte con 4 simboli consecutivi uguali) i cui valori vanno sommati; un singolo simbolo di valore inferiore viene invece premesso per indicare che il valore va sottratto. Abbiamo cosí che i numeri da uno a dodici sono scritti come:

I, II, III, IV, V, VI, VII, VIII, IX, X, XI, XII

ovvero

Ⅰ, Ⅱ,Ⅲ, Ⅳ, Ⅴ, Ⅵ, Ⅶ, Ⅷ, Ⅸ, Ⅹ, Ⅺ, Ⅻ

usando Unicode (curiosità: lo Unicode ha codici per i numeri romani da uno a dodici, e poi per cinquanta, cento, cinquecento e mille, piú qualche variante, ma non per altre combinazioni, come quella per il venti).

Il numero venti, di nostro interesse, sarà quindi scritto come

XX

ovvero

ⅩⅩ

al solito (ma ora basta perdere tempo con i numerali romani Unicode perché mi pesa scriverli, e la maggior parte dei miei lettori non vedrà la differenza).

Secondo gruppo: una questione di base

Il lettore attento avrà notato che finora, parlando di numeri, ho preferito scriverne il valore in lettere. Il motivo —abbastanza ovviamente— è che affidarmi alla comune grafia “in cifre” avrebbe completamente fatto saltare il banco per questo secondo gruppo, dove il gioco è proprio il fatto che lo stesso valore può essere rappresentato con combinazioni di cifre diverse a seconda della base di numerazione.

L'idea del sistema di numerazione arabo è quello di adottare dieci simboli, che nell'era moderna sono per il mondo occidentale

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

con valore crescente da zero a nove. Queste cifre possono essere combinate in sequenze come ad esempio 1234 che noi leggiamo «mille duecento trenta quattro»: il valore di una cifra in un numero dipende dalla sua posizione, ed in questo esempio abbiamo quattro unità (4 nella posizione meno significativa), tre decine (3 nella posizione successiva, da destra verso sinistra, in ordine di valore), due centinaia (ovvero decine di decine, nella posizione successiva), ed infine un migliaio (ovvero decina di centinaia, nella posizione piú significativa).

Il motivo per cui si parla di decine (e decine di decine, etc) è che il sistema di numerazione arabo è un sistema decimale, con dieci cifre, che quindi richiede uno spostamento di posizione ogni dieci.

Nello stesso modo si possono avere sistemi di numerazione in qualunque base intera maggiore di uno (esiste il sistema numerico unario ma non è posizionale, quindi non ne parliamo).

L'idea è che data una base $b$ (con $b$ un qualunque intero maggiore di uno) e date $b$ cifre, una combinazione di cifre andrà letta da destra verso sinistra considerando unità, multipli della base, multipli del quadrato della base, multipli del cubo della base, e cosí via. Se la base $b$ è non superiore a dieci, per convenzione si usano i simboli da 0 alla cifra precedente il valore della base; per basi maggiori di dieci (le piú comuni sono sedici e dodici) si usano spesso delle lettere; nell'esadecimale, ad esempio, i simboli

A, B, C, D, E, F

rappresentano le cifre con valori da dieci a quindici; per le possibili scelte adottate nel sistema dozzinale, rimando alla relativa pagina Wikipedia.

Facendo un esempio concreto, in un sistema di numerazione in base cinque, con i soliti simboli (0, 1, 2, 3, 4), il numero 1234 rappresenta quattro unità, tre cinquine, due venticinquine ed una centoventicinquina, rappresentando in numeri romani il numero:

IV + III × V + II × XXV + CXXV = CXCIV

ovvero il numero centonovantaquattro. Se indichiamo la base in pedice, come consuetudine, ma rappresentandola con i numeri romani per evitare confusione sui simboli, abbiamo quindi

$${1234}_V={194}_X$$

Il nostro “gioco del venti” sarà quello di indovinare in quale base ciascuna delle combinazioni di cifre proposte rappresenta il numero venti (due decine).

Ricordiamo che a questo gruppo appartengono le combinazioni:

14, 20, 24, 10100, 202, 40, 26

e che la seconda è ovviamente quella con cui abbiamo tutti familiarità (20 è il numero venti in base dieci).

Anche chi non ha troppa dimestichezza con il binario (sistema di numerazione in base due, che ha come unici simboli 0, 1) può facilmente sospettare che 10100 possa essere il venti in base due. La cosa può essere confermata ricordando che venti si può scomporre in sedici piú quattro, dove sedici è la quarta potenza di due, e quattro la seconda potenza: nel sistema binario, avremo quindi “una quarta potenza di due” (un 1 in quinta posizione da destra, perché la prima posizione rappresenta le unità, ovvero la potenza zero della base), ed “una seconda potenza di due” (un 1 in terza posizione da destra), ovvero proprio 10100.

Per la base di rappresentazione delle altre potremmo andare cosí a tentativi, ricordandoci che se il numero sembra piú “piccolo” la base è maggiore, e viceversa. Possiamo quindi ipotizzare che il 14 sia in una base maggiore di dieci, e tutti gli altri in una base minore.

C'è in verità un trucchetto che può tornarci utile per capire qual è la base, poiché sappiamo qual è il valore: scomporre il numero nelle sue componenti posizionali e risolvere l'equazione che pone il tutto uguale a venti.

Applichiamo per cominciare (e come esempio) la procedura al 14. Usando i numeri romani per indicare i valori senza confonderci con le basi:

$$14=XX\Rightarrow I\times b+IV=XX\Rightarrow b=XX-IV\Rightarrow b=XVI$$

ovvero: 14 è venti in base sedici. Analogamente:

$$24=XX\Rightarrow II\times b+IV=XX\Rightarrow II\times b=XX-IV\Rightarrow b=\frac{XVI}{II}=VIII$$

ovvero: 24 è venti in base otto.

Per quanto riguarda il 202, dobbiamo considerare che qui abbiamo cifre in terza posizione, che rappresentano la base al quadrato. Quindi:

$$202=XX\Rightarrow II\times b^{II}+II=XX\Rightarrow b^{II}+I=X\Rightarrow b^{II}=IX\Rightarrow b=III$$

ovvero: 202 è venti in base tre.

È cosí molto facile vedere che 40 è venti in base cinque (quattro volte la base dà venti, quindi la base è un quarto di venti, cioè cinque), ed infine il 26 non può che essere venti in base sette (metà di quattordici, che è venti meno sei).

Una tabella riepilogativa, ordinata per base ed aggiungendo qualche base mancante che potrebbe comunque essere interessante abbiamo quindi che:

Per ovvie ragioni non continuiamo con basi maggiori di venti, dove vi sarebbe una cifra dedicata specificamente a questo valore.

Una curiosità: in tutte le basi da due a venti, il numero venti può essere rappresentato con le sole cifre decimali, anche in basi maggiori di dieci. Ed interpretando il numero come se fosse un numero decimale si vede come questo scenda inizialmente molto velocemente (da 10100 a 202 è un fattore cinquanta), poi piú lentamente (un fattore circa due fino a 40), poi di un semplice otto, poi di un sei, e poi ripetutamente di un due fino a 20 (in base dieci), e poi ancora di uno per base fino al 10 in base venti.

Terzo gruppo: bilanciamoci

Per introdurre il terzo gruppo, i cui membri sono —ricordiamo—

1T1T, 1T0, 3T

bisognerebbe capire cosa rappresenta quel simbolo T.

Abbiamo osservato come per i sistemi posizionali in una data base $b$ siano necessari $b$ simboli. Tipicamente, questi hanno valori che vanno da zero (0) al valore immediatamente precedente la base (ad esempio, in base dieci da zero a nove, in base tre da zero a due). Tuttavia, nel caso in cui la base sia dispari, oltre allo zero abbiamo un numero pari di simboli. Cosa succede allora se invece di distribuirli tutti “dallo stesso lato” (rispetto allo zero) li distribuiamo “metà prima e metà dopo”?

Si ottiene cosí una rappresentazione in una base detta “bilanciata”, e la peculiarità è che in questo caso metà dei simboli avranno valori negativi. Cosí ad esempio nel sistema numerico ternario bilanciato avremo simboli che rappresentano i valori “da meno uno a piú uno”, nel sistema quinario bilanciato avremo simboli che rappresentano i valori “da meno due a piú due” in quello undecimale (base undici) bilanciato avremo simboli che rappresentano i valori “da meno cinque a piú cinque” e cosí via.

Il problema grosso diventa qui di tipo tipografico: come rappresentare facilmente le cifre con valore negativo? Alcune convenzioni sono di utilizzare le medesime cifre positive, ma riflesse verticalmente o ruotate “a testa in giú”, oppure con una barra sopra (integrandovi cosí il segno meno). Nel caso specifico del sistema ternario bilanciato, la convenzione piú comune è di utilizzare il simbolo T per rappresentare “meno uno”.

Come si dovrebbe quindi scrivere venti in ternario bilanciato? Ricordiamo che nel sistema ternario “normale” (non bilanciato) il numero venti si scrive 202 (due unità, piú due quadrati di tre). Ma il simbolo 2 non esiste nel ternario bilanciato: invece di avere due unità, avremo una terzina meno una unità: 1T. Allo stesso modo, non potremo avere due nove (quadrati di tre): avremo invece un cubo di tre meno un quadrato di tre: 1T00 (ventisette meno nove fa infatti diciotto). Il nostro 202 in ternario non bilanciato diventa 1T1T in ternario bilanciato: laddove il non bilanciato scompone il venti in diciotto piú due, il bilanciato lo scompone in ventisette meno nove piú tre meno uno.

Sembra strano? È ventisette meno sette, dove sette è sei piú uno, dove sei è nove meno tre:

$$1000-((100-10)+1)=1000-100+10-1$$

e nel ternario bilanciato, l'opposto si ottiene semplicemente scambiando 1 e T.

Cosa succede nelle altre basi dispari? Vediamo ad esempio in base cinque bilanciata: ricordiamo che in questo caso non possiamo avere piú di due di qualcosa. Il nostro venti dovrebbe essere quattro cinquine, ma questo non è possibile: dovremo quindi partire da una venticinquina (cinque al quadrato) e poi togliere una cinquina: possiamo ancora riciclare la T per rappresentare “meno uno”, ed il nostro venti diventa 1T0.

Ed in base sette? Stavolta non possiamo avere piú di tre di qualcosa, quindi non possiamo scomporre il venti in due volte sette piú sei: dovremo scomporlo in tre volte sette (ventuno) meno uno: 3T.

Curiosamente, in base nove bilanciata la rappresentazione rimane 22, poiché sono entrambe cifre presenti nella versione bilanciata.

La questione si fa piú spinosa nel caso della base undici: nel caso bilanciato, le cifre avranno valori “da meno cinque a piú cinque”, quindi non potremo rappresentare il venti come “undici piú nove”: dovremmo rappresentarlo come due volte undici meno due. E non esiste una convenzione grafica normale per la cifra con valore meno due. Potremmo però inventarne una sul momento, adottando la Z per rappresentare “meno due”, sicché venti diventerebbe 2Z.

L'unica vera rogna è la base tredici: in base bilanciata avremo cifre con valori da meno a piú sei, sicché il venti dovrebbe essere scritto come due volte tredici meno sei, ma che simbolo adottare per la cifra “meno sei”? Per questo motivo, nella tabella seguente ci affideremo invece alla convenzione di soprasegnare le cifre negative:

(non mi è chiaro perché vengono formattati in maniera diversa i blocchi con cifre negative, ma questo non è un problema da risolvere alle 11 di sera, quindi sarà per un'altra volta).

Quarto gruppo: il mistero del punto

L'ultimo venti da studiare (per oggi) è lo stranissimo

1000010.010001

che in Italia ed altri paesi dove si predilige l'uso della virgola come separatore “decimale”, sarebbe meglio scritto come

1000010,010001

o ancor meglio come

1 000 010,010 001

per aumentarne la leggibilità.

Ma cos'è questa follia? Come può un numero intero richiedere una parte frazionaria per essere rappresentato?

Il segreto è nella “magica” sezione aurea. Vi ricordate “il medio proporzionale tra il tutto e la parte rimanente”? Dalla proporzione

$$1:\Phi =\Phi :(1-\Phi )$$

si ottiene l'equazione

$${\Phi }^2=1-\Phi$$

che ha soluzione, espressa in base dieci:

$$\Phi =\frac{\sqrt{5}-1}{2}.$$

La sezione aurea è proprio il rapporto $\varphi =1:\Phi$ (il valore Phi è detto coniugato della sezione aurea) e vale (ancora espressa in base dieci):

$$\varphi =\frac{2}{\sqrt{5}-1}=\frac{2(\sqrt{5}+1)}{5-1}=\frac{\sqrt{5}+1}{2}=1+\Phi .$$

L'aspetto particolare di $\varphi$ è che soddisfa l'equazione

$${\varphi }^2=1+\varphi$$

da cui, piú in generale

$${\varphi }^{n+1}={\varphi }^n+{\varphi }^{n-1}$$

ovvero: la somma di due potenze consecutive di $\varphi$ equivalgono alla potenza successiva (proprietà di normalizzazione).

Una delle tante peculiarità di $\varphi$ è che è possibile esprimere ogni numero intero come somma di sue potenze positive e negative (ovvero potenze di $\varphi$ e potenze di $\frac{1}{\varphi }=\Phi$).

Come? Facciamo qualche esempio.

Abbiamo ovviamente ${\varphi }^0=1$ (è vero per ogni numero diverso da zero, e quindi anche per $\varphi$).

Per le proprietà di $\varphi$ e $\Phi =\frac{1}{\varphi }$ abbiamo

$${\varphi }^2=1+\varphi$$

$${\Phi }^2=1-\Phi$$

e quindi

$${\varphi }^2+{\Phi }^2=2+\varphi -\Phi$$

da cui

$$2={\varphi }^2-\varphi +\Phi +{\Phi }^2=1+\Phi +{\Phi }^2={\varphi }^0+{\varphi }^{-1}+{\varphi }^{-2}=\varphi +{\varphi }^{-2}$$

dove l'ultima uguaglianza viene dalla proprietà di normalizzazione applicata alla potenza $n=0$.

Cosí procedendo possiamo continuare per i successivi numeri naturali:

$\begin{array}{ll}3=2+1& =\varphi +{\varphi }^{-2}+1={\varphi }^1+{\varphi }^0+{\varphi }^{-2}={\varphi }^2+{\varphi }^{-2}\\ 4=2^2& ={\varphi }^2+2\varphi {\varphi }^{-2}+{\varphi }^{-4}={\varphi }^2+(\varphi +{\varphi }^{-2}){\varphi }^{-1}+{\varphi }^{-4}=\\ & ={\varphi }^2+1+{\varphi }^{-3}+{\varphi }^{-4}={\varphi }^2+{\varphi }^0+{\varphi }^{-2}\\ 5=4+1& ={\varphi }^2+1+{\varphi }^{-2}+1={\varphi }^2+2+{\varphi }^{-2}={\varphi }^2+\varphi +{\varphi }^{-2}+{\varphi }^{-2}=\\ & ={\varphi }^3+2{\varphi }^{-2}={\varphi }^3+(\varphi +{\varphi }^{-2}){\varphi }^{-2}={\varphi }^3+{\varphi }^{-1}+{\varphi }^{-4}\end{array}$

e cosí via.

Questa particolarissima proprietà della sezione aurea permette di definire quella che si chiama la base aurea, un sistema di numerazione posizionale in cui la base è $\varphi$ e i simboli ammessi sono solo 0 (come coefficiente delle potenze della base che mancano nella rappresentazione) e 1 (dove invece la base è presente), con il separatore decimale a separare le potenze positive da quelle negative.

Dall'espansione in somme di potenze di $\varphi$ dei primi cinque numeri abbiamo quindi la loro rappresentazione aurea (permettetemi qui di usare il punto come separatore decimale, e la virgola come separatore della successione):

1, 10.01, 100.01, 101.01, 1000.1001

Abbiamo ora tutti gli elementi per calcolarci la rappresentazione aurea del venti. Abbiamo infatti:

$\begin{array}{ll}20=4\cdot 5& =({\varphi }^2+{\varphi }^0+{\varphi }^{-2})\cdot ({\varphi }^3+{\varphi }^{-1}+{\varphi }^{-4})=\\ & ={\varphi }^5+\varphi +{\varphi }^{-2}+{\varphi }^3+{\varphi }^{-1}+{\varphi }^{-4}+\varphi +{\varphi }^{-3}+{\varphi }^{-6}=\\ & ={\varphi }^5+{\varphi }^3+2\varphi +{\varphi }^{-1}+{\varphi }^{-2}+{\varphi }^{-3}+{\varphi }^{-4}+{\varphi }^{-6}=\\ & ={\varphi }^5+{\varphi }^3+2\varphi +{\varphi }^0+{\varphi }^{-2}+{\varphi }^{-6}=\\ & ={\varphi }^5+{\varphi }^3+{\varphi }^2+{\varphi }^{-1}+{\varphi }^0+{\varphi }^{-2}+{\varphi }^{-6}=\\ & ={\varphi }^5+{\varphi }^4+\varphi +{\varphi }^{-2}+{\varphi }^{-6}=\\ & ={\varphi }^6+\varphi +{\varphi }^{-2}+{\varphi }^{-6}\end{array}$

da cui la rappresentazione aurea 1000010.010001 con la sua affascinante quasi simmetria.

(Non) finisce qui

Ovviamente quelli presentati qui sono solo una misera frazione di tutte le rappresentazioni possibili per il numero venti. Esistono dopo tutto una miriade di sistemi di numerazioni e di simbologie per la rappresentazione delle cifre (anche già solo i famosi numeri arabi hanno una controparte “orientale” le cui cifre, pur avendo lo stesso valore, hanno una diversa veste grafica (٠١٢٣٤٥٦٧٨٩). A questi possiamo aggiungere i sistemi di numerazione passati e presenti di ogni parte del globo, dal greco antico all'ebraico, dal glagolitico al cinese, dal cistercense al giapponese.

Ma s'è fatta una certa, e qui si rischia di non finire piú.

I recently came across this interesting article (blog post?) from the Fediverse showing a nifty trick to compute multiples of π by relying on only two products: by 3, and by 14. I encourage you to read the article if you're interested in the method because it's crystal clear, whereas I'm going to muddy the waters a bit, throwing my considerations at it.

The reason why the proposed idea works is that the first digits of the fractional part of the decimal expansion of $\pi$ can be expressed as multiples of 14. Indeed, the fractional part of $\pi =3.14159265359...$

This effectively means that

$$\pi =3.14159265359...=3+14\cdot {10}^{-2}+14\cdot {10}^{-4}+14\cdot {10}^{-5}+...$$

and thus

$$k\cdot \pi =3k+14k\cdot ({10}^{-2}+\cdot {10}^{-4}+\cdot {10}^{-5}+...)$$

which is interesting because ${10}^{-x}$ means “shifting your results right by $x$ digits”, which is particularly nice if $k$ is an integer up to 7, and thus $7k$ has two digits, and the first two terms in the expansion are shifted by two and four digits (no need to take any actual summation).

Let's make the example with $k=7$, and try to compute

$$7\pi =21.991148575...$$

This may seem to be an arbitrary divergence from Cook's example, but is actually needed to discuss one of the limitations of the approach: spillover. We have $3k=21$, $14k=98$, and thus the first terms (up to what Cook's calls the simplest approach) are:

$$7\pi \approx 21.9898$$

(relative error is $<6.2\cdot {10}^{-5}$ —note that this is the same found by Cook, even though he discusses the absolute error instead)

Things get a bit hairier on the first refinement, because the value of $14k$ now needs to be shifted by one more digit, not two. And while in Cook's example with $k=4$ he has $14k=56$ and $560+56=616$ (remove the last two digits, replace with the new three digits) in our case there's a bit of a spillover: $980+98=1078$, so this refinement doesn't lend itself to a simple substitution of the last two digits:

$$7\pi \approx 21.99078$$

(relative error $<1.7\cdot {10}^{-5}$.)

The next refinement is a bit more involved, because (you may notice the $7$ in the tableau at the top of this article) it involves halving our $14k$ —which, coincidentally, is always possible because $14$ is even— and adding it in the same place. In our case, this means adding another $49$ to the last two digits, and once again we have a small spillover (luckily into a $0$):

$$7\pi =21.99127.$$

The relative error is now $<5.6\cdot {10}^{-6}$, more than order of magnitude better than the initial result, and —interestingly— it is now an overestimation.

Alternatives

If you go read the Fediverse thread, you'll notice that I raised the question of the comparison with approximations compute from the well-known rational approximations of $\pi$, i.e.

$$\frac{22}{7}=3+\frac{1}{7}$$

and

$$\frac{355}{113}=3+\frac{16}{113}=3+\frac{1}{7}-\frac{1}{791}$$

Aside from the somewhat contrived case of $k=7$ I'm using here an example, multiples of these fractions would be harder to compute, as observed by Bill Ricker, although the multiple of $355/113$ would still be more accurate.

What is interesting is that the second refinement presented by Cook can be further refined, e.g. by replacing the last “half $14k$” contribution with a “3/8th of $14k$” contribution. This is less trivial to compute, unless we consider that $3/8=1/2-1/8$, so we can correct Cook's refinement by subtracting the “half $14k$ divided by 4”, which in our case is $49/4=12.25$.

Even if we truncate this to $12$, the fixup gives us

$$7\pi \approx 21.99115$$

with a relative error that is now $<6.5\cdot {10}^{-8}$, which is now two orders of magnitude lower. (The actual correction would be $7\pi \approx 21.9911475$ with a relative error $<5\cdot {10}^{-8}$.)

What is impressive about this particular result is that the relative error is not only of the same order as the one given by the $355/113$ approximation, but actually slightly better (the relative error for $355/113$ is closer to $8.5\cdot {10}^{-8}$).

A summary

To get a good approximation of a multiple of $\pi$:

1. multiply by 3 (call this $u$);
2. multiply by 14 (call this $f$);
3. add: $u$,
   $f$ shifted by 2 digits,
   $f$ shifted by 4 digits,
   $f$ shifted by 5 digits;
4. bonus: add
   $f/2$ shifted by 5 digits;
5. extra: subtract
   $f/8$ shifted by 5 digits
   (note that $f/8$ can be computed as $\left(\frac{f}{2}\right)/4$).

An alternative to the last two points, getting to the same results, would be to add $f/4+f/8$ (this time computing $f/8$ as half of $f/4$) shifted by 5 digits.

Let's apply to this to Cook's example for $4\pi$:

1. $4\times 3=12$;
2. $4\times 14=56$;
3. $12+0.56+0.0056+0.00056=12.56616$;
4. bonus: $56/2=28\Rightarrow 12.56644$
   (note that Cook's post has a couple of typos in this line; absolute error is still $<7\cdot {10}^{-5}$);
5. extra: $28/4=7\Rightarrow 12.56637$
   (absolute error is now $<6.2\cdot {10}^{-7}$; note that the extra division by 4 is particularly easy to do in Cook's example).

with the possibility to replace 4. and 5. with

$$\frac{56}{4}=14,\frac{14}{2}=7\Rightarrow 12.56616+0.00014+0.00007=12.56630+0.00007=12.56637.$$

Note however that $12.5663$ is slightly worse than $12.56644$ as an approximation (error $7.1\cdot {10}^{-5}$ rather than $<7\cdot {10}^{-5}$, in addition of being of the opposite sign.) Note also that the best approximation we've discussed so far ($12.56637$) is also the midpoint of these two.

Smallest doesn't mean easier to handle

I believe that one of the most important discoveries to which this trick has led me is the importance of the difference between the compactness of the (approximating) fraction and how easy it is to handle.

This isn't something entirely new to me (I've always known that in computing there are several series that help find out new digits of $\pi$ faster), but what I learned this time is how this maps to “human computing”.

If we write the full mathematical expression of the $\pi$ approximant that leads to the algorithm we just described we have:

$$\pi \approx 3+\frac{14}{100}\cdot (1+\frac{1}{100}+\frac{1}{1000}\cdot (1+\frac{1}{2}\cdot (1-\frac{1}{4}))) (\star )$$

which is considerably more complex than the expressions we have from the continued fraction expansion,

$$\pi \approx \frac{22}{7}=3+\frac{1}{7}$$

or even my beloved Milü

$$\pi \approx \frac{355}{113}=3+\frac{16}{113}=3+\frac{1}{7}-\frac{1}{791}=3+\frac{1}{7}\cdot (1-\frac{1}{113}).$$

Yet, except for particular cases, the divisions by $7$ and $113$ involved in the latter expressions are likely to be more complex than the “multiply by $14$, divide by $100$”, because the division by $100$ in the decimal system is a simple shift by two digits.

To wit, if we have computed $1/7$ for the $22/7$ approximation, it would be simpler to approximate $\pi$ as

$$\frac{2199}{700}=3+\frac{1}{7}-\frac{1}{700}=3+\frac{1}{7}\cdot (1-\frac{1}{100})$$

than with the $355/113$ expansion, since the last term is obtained simply by shifting by two digits the already computed division by $7$. Even $3+1/7-1/800$ (more accurate, but still not as much as $355/113$) would be faster than the full $355/113$ contribution.

Sevenths

Incidentally, here's an interesting fact:

$$\frac{1}{7}=0.\left(142857\right)=\frac{14}{100}+2\cdot \frac{14}{{100}^2}+4\cdot \frac{14}{{100}^3}+8\cdot \frac{14}{{100}^4}+...$$

and if we factor $14/100$ (recognize it yet?)

$$\frac{1}{7}=\frac{14}{100}\cdot (1+\frac{2}{100}+\frac{4}{{100}^2}+\frac{8}{{100}^3}+\cdots )=\frac{14}{100}\cdot \sum _{i=0}^{\infty }\frac{2^i}{{100}^i}.$$

Now, if we compute $1/7(1-1/100)$ as discussed above, we get

$$\frac{1}{7}(1-\frac{1}{100})=\frac{14}{100}\cdot (1+\frac{1}{100}+\frac{2}{{100}^2}+\frac{4}{{100}^3}+\cdots )$$

and you may notice that the first two terms are the same as the ones in the mind trick formula $(\star )$. Where they start to diverge is on the third term, which is $2/10000=1/5000$ here, but (after simplifications) $11/8000$ in the mind trick formula.

This divergence should not surprise, since $1/7-1/700$ is actually a pretty poor approximation for $\pi -3$. If we try $1/7-1/800$, the first terms are a bit more complex to compute:

$$\frac{1}{7}-\frac{1}{800}=\frac{1}{7}\cdot (1-\frac{7}{8}\cdot \frac{1}{100})=\frac{14}{100}\cdot (1+\frac{9}{8}\cdot \frac{1}{100}+\frac{25}{8}\cdot \frac{1}{{100}^2}+...)$$

but we can make it easier to compare with $(\star )$ by rearranging the terms as

$$\frac{1}{7}-\frac{1}{800}=\frac{14}{100}\cdot (1+\frac{1}{100}+\frac{1}{8}\cdot \frac{1}{100}+\frac{25}{8}\cdot \frac{1}{{100}^2}+...)$$

so that the third term would be:

$$\frac{100}{8}\cdot \frac{1}{{100}^2}+\frac{25}{8}\frac{1}{{100}^2}=\frac{125}{8\cdot 10000}=\frac{1}{8\cdot 80}=\frac{1}{640}$$

(compare $125/80000$ to the mind trick's $110/80000$.)

Speed versus accuracy

One of the key point in determining the approach to use to find approximate values to multiples of $\pi$ is to take into account the accuracy of the multiplier.

As an example, assume we want to compute the circumference of the Earth, knowing that the radius is approximately $r=6500$ km. We want to compute $2\pi r$ or $13000\pi$.

One would be tempted to use the magic algorithm that has been the main topic of discussion of this article, but that would actually be a waste of brainpower in this case, since the approximation for the radius is quite large already: there's no need to compute $13000\pi$ to particularly high accuracy, and in fact in this case the $3+1/7$ approximation of $\pi$ is sufficient: the first part is trivial, $3\times 13000=39000$, and the rest is

$$\frac{13000}{7}=\frac{14000}{7}-\frac{1000}{7}\approx 2000-140$$

(the next term from $1/7$ would be $140/100$, already too precise) which gives us a circumference of some $40960$ km.

The attentive reader who remembers when the meter was defined as the 40-millionth part of the circumference of the Earth, will have noticed that we're way over the expected $40000$ km, which is due to the fact that the (average) Earth radius is actually less than $6400$. If we want to redo these computations, this time with $12800\pi$, we have:

$$3\times 12800=38400$$

and leveraging the approximation $200/7\approx 28$:

$$\frac{12800}{7}\approx 1828$$

giving us a circumference of $38400+1828=40228$, which is still too large (and for the curious: no, using a more accurate approximation wouldn't solve the issue, dropping it only to around $40212$.)

Reciprocal problem

Maybe it would be better to work things the other way: assuming we know that circumference is $40000$ km, can we work out a more accurate value of the radius? This means computing $20000/\pi$. This is actually another one of those cases where the simpler, harder to manipulate fractions are easier to use, since their reciprocal is $1/\pi$.

In our case

$$\frac{20000}{\pi }\approx 20000\cdot \frac{7}{22}=\frac{70000}{11}\approx 6364$$

(the division by $11$ is easy to do in mind: $66$ from $70$ is $4$, $33$ from $40$ is $7$, and then it repeats). This is actually a pretty good approximation to the actual Earth radius, that is closer to $6371$ km. (Note also that using actual $\pi$ here would only give marginally better results with an integer part of $6366$: our approximation is accurate enough.)

So this got me wondering: could we build an approximant to $\frac{1}{\pi }$ that is as easy to handle as $(\star )$ and the corresponding algorithm? From a quick look, the answer seems to be … “ish”. We have

$$\frac{1}{\pi }=0.318309886...$$

so from a cursory look the best candidate to replace the $14/100$ in $(\star )$ is $318/1000$, and our shifts will be of three rather than two digits:

$$\frac{1}{\pi }\approx \frac{318}{1000}\cdot (1+\frac{1}{1000}\cdot (1-\frac{3}{100}))$$

which is considerably less manageable than $(\star )$, especially after the second term, because of the three-digit numbers, although it does give us pretty low relative errors right from the start, approximately $9.74\cdot {10}^{-4},2.55\cdot {10}^{-5},4.48\cdot {10}^{-6}$ at the first, second and third term.

A more manageable candidate may seem like $32/100$, since

$$\frac{1}{\pi }\approx \frac{32}{100}\cdot (1-\frac{1}{2}\cdot \frac{1}{100}-3\cdot \frac{1}{{100}^2}+\frac{2}{10}\cdot \frac{1}{{100}^2})$$

with relative errors of approximately $5.4\cdot {10}^{-3},2.8\cdot {10}^{-4},1.8\cdot {10}^{-5},1.6\cdot {10}^{-6}$ respectively for the first, second, third term, and fourth term. The big nuisance of this building block is that it seems to be built primarily around subtraction rather than addition, something which is harder to manage mentally compared to the “add by shift” of $(\star )$.

To compare let's try to compute the same $20000/\pi$ with the two approximations.

We have $2\cdot 318=636$, so the first two terms of using the $318/1000$

$$\frac{20000}{\pi }=10000\cdot \frac{2}{\pi }\approx 10000\cdot 0.636636=6366.36$$

(compare with actual result $6366.19772...$ to show the excellent result of this approximation.)

For $32/100$, we have $2\cdot 32=64$ and $3\times 64=252$, but:

$$\frac{20000}{\pi }=10000\cdot \frac{2}{\pi }\approx 10000\cdot (0.64-0.0032-0.000252+0.0000128)$$

that is:

$$\frac{20000}{\pi }=10000\cdot (0.64-0.003452+0.0000128)$$

and finally:

$$\frac{20000}{\pi }=6400-34.52+0.128=6365.48+0.128=6365.608$$

Ultimately, the fact that the expressions in this case are uglier and less manageable may just be the sign that computing the reciprocal of $\pi$ is an inverse problem. Or that I suck at these kind of things, especially at this hour.

Introduction

I first heard about this problem from the Stand-up Maths video on the topic and I found it utterly fascinating. I'm going to present here the problem, the solution, and finally discuss a more general version.

The problem

The problem is quite simple. Find the length of the perimeter of the following plane figure:

The shape is obtained by folding an A4 piece of paper (whose sides have lengths in a ratio of $1:\sqrt{2}$) two times: on one corner until the short side reaches the adjacent long side, and then again on the corner of the leftover rectangle, until the leftover on the long side touches the folded short side. Check Matt's video if you're confused, or consider the following picture: from the initial rectangle, fold diagonally to bring $U$ to $H$ and then $V$ to $K$:

The solution

The solution to the problem is quite straightforward: we simply need to add up the lengths of the segments composing the perimeter of our figure.

We'll take as reference for the length the short side of the sheet of A4 paper, so the bottom segment $AD$, which is the long side of the sheet, has length $\overline{AD}=\sqrt{2}$.

The long diagonal segment $AB$ is the diagonal of a square $AUBH$, whose side is the short side of the sheet: the side has length $\overline{AU}=\overline{UB}=\overline{BH}=\overline{AH}=1$, and therefore the diagonal length is $\overline{AB}=1\cdot \sqrt{2}=\sqrt{2}$.

The short diagonal $BC$ was obtained folding the $V$ angle of the leftover rectangle $HBVD$, so let's focus for a moment on this rectangle. The long side of $HBVD$ is the short side of the original A4 paper sheet, and is thus of length $\overline{BH}=\overline{VD}=1$; the length of the short side of this rectangle, on the other hand, is equal to the difference in length between the long and short sides of the A4 paper sheet, and is thus $\overline{BV}=\overline{HD}=\overline{AD}-\overline{AH}=\sqrt{2}-1$.

By folding the corner of this rectangle, the resulting side is the diagonal of the $BVCK$ square, whose side is the short side of $HBVD$, and its length is thus

$$\overline{BC}=(\sqrt{2}-1)\cdot \sqrt{2}=2-\sqrt{2}.$$

The last segment $CD$ is the long side of the rectangle $KCDH$, which is the “leftover of the leftover” after the second fold: its length is thus the difference between the long and short sides of the leftover rectangle $HBVD$:

$$\overline{CD}=\overline{VD}-\overline{VC}=\overline{VD}-\overline{BV}=1-(\sqrt{2}-1)=2-\sqrt{2}.$$

(Notice how, curiously, this last segment is equal in length to the previous, diagonal segment! We have $\bar{BC} = \bar{CD}, which will come in handy next.)

We now have the lengths of all the segments:

and the length of our perimeter can then be computed as:

$$\overline{AB}+\overline{BC}+\overline{CD}+\overline{AD}=\sqrt{2}+\sqrt{2}+(2-\sqrt{2})+(2-\sqrt{2})=2+2=4.$$

Generalization

The beauty of the problem obviously comes from the fact that the cancelling square roots give us a nice and clean integer despite the original piece of paper having an irrational aspect ratio, thus resulting in irrational lengths for all sides. But what happens if we don't start from an A4 (or more in general, from an A-series) sheet? What if the original rectangle has a different aspect ratio?

So let's assume now that we're starting from a rectangle with aspect ratio $1:a$ with $a\ge 1$.

The bottom segment now has length $\overline{AD}=a$.

The long diagonal segment still has length $\overline{AB}=\sqrt{2}$, since the short side of the original rectangle still has length $1$.

Let's now look at the leftover rectangle. The long side still has length $1$, and the other has length $a-1$.

We must now be careful, since the second fold gives us the behavior we have already seen for the A4 sheet only as long as the short side of the leftover rectangle is not longer than the other side, i.e. only if $\overline{BV}\le \overline{VD}$, i.e. if $a-1\le 1$, i.e. only if $a\le 2$.

In this case, the second fold thus gives us a short diagonal of length

$$\overline{BC}=(a-1)\sqrt{2},$$

and the remaining segment has length

$$\overline{BC}=1-(a-1)=2-a.$$

We have lost the beautiful relationship between the last two segments, but we can still compute the final perimeter, with length

$$\overline{AB}+\overline{BC}+\overline{CD}+\overline{AD}=a+\sqrt{2}+(a-1)\sqrt{2}+2-a=2+a\sqrt{2}.$$

We can thus see that the only case where we can a nice integer value for the length of the perimeter is when $a\sqrt{2}$ is an integer, which can only happen when $a=n\sqrt{2}$ for some integer $n$, but since it must be $1\le a\le 2$, the case $n=1,a=\sqrt{2}$ is the only possible case.

In the extreme case where $a=1$, the second fold produces a diagonal of length 0, and we get an isosceles triangle obtained by halving the square, with length $2+\sqrt{2}$.

In the extreme case where $a=2$, the second fold matches the first one, and we get another isosceles triangle, this time with two sides of length $\sqrt{2}$, and the other with length 2, and thus a perimeter of length $2+2\sqrt{2}=2\cdot (1+\sqrt{2})$.

Thin stripe case

We can, in fact, also do the case $a>2$, i.e. the case when the original rectangle is a “thin stripe” (long side more than twice longer than short side). In this case, the second fold would stop when the (now short) right side $VD$ of the leftover rectangle $HBVD$ meets the base, giving us a trapezium:

We still have $\overline{AD}=a$, $\overline{AB}=\sqrt{2}$, and this time also $\overline{CD}=\sqrt{2}$. Finally, the short base $BC$ is obtained subtracting from the long base the short sides of the original rectangle (due to the folds), and thus $\overline{BC}=a-2$.

The perimeter of the figure is therefore

$$\overline{AD}+\overline{BC}+\overline{CD}+\overline{AD}=a+a-2+2\cdot \sqrt{2}=2\cdot (a-1+\sqrt{2}).$$

(Note that for the extreme case $a=2$ we obtain again $2\cdot (1+\sqrt{2})$.)

If we want the perimeter of the new figure to be an integer $n$, we need first of all that $a+\sqrt{2}-1$ to be rational, and thus $a=q-\sqrt{2}$ for some rational $q$. Then $n=2\cdot (a-1+\sqrt{2})=2\cdot (q-1)$, hence $q=1+\frac{n}{2}$, and thus finally

$$a=1+\frac{n}{2}-\sqrt{2}.$$

Observe that since this was done under the hypothesis $a\ge 2$, from this we also get $\frac{n}{2}\ge 1+\sqrt{2}$ whence $n\ge 2+2\sqrt{2}$, and since $n$ must be integer, $n\ge 2+3=5$.

The smallest integer perimeter we can get for the “thin stripe” case is $5$, achieved with $a=\frac{7}{2}-\sqrt{2}$ (for the curious, this is barely more than $2$, as $a=2.0857864376...$ —and yes, it's the trapezium in the figure). Subsequent integer perimeters are obtained by incrementing $a$ in steps of $\frac{1}{2}$.

.mau. propone per oggi un quizzino della domenica di stampo geometrico: calcolare l'area del quadrato blu in figura, sapendo che prolungando i lati questi intersecano l'asse delle ascisse a 3, 5, 7, 13:

Per risolverlo, chiamiamo $l$ il lato del quadrato. Se trasliamo il quadrato finché il vertice inferiore si trova al punto $(5,0)$, ci ritroveremo con un triangolo rettangolo (rosso in figura) la cui ipotenusa è lunga 2 (dal punto $(3,0)$ al punto $(5,0)$), ed il cateto maggiore è lungo $l$:

Effettuando invece la traslazione dall'altro lato, portando il medesimo vertice al punto $(7,0)$, ci ritroveremo con un triangolo rettangolo (verde in figura) la cui ipotenusa è lunga 6 (dal punto $(7,0)$ al punto $(13,0)$), ed il cateto minore è lungo $l$:

Osserviamo infine che i due triangoli in questione sono simili (essendo creati da rette rispettivamente parallele), per cui il cateto maggiore del triangolo verde è lungo $3l$ (essendo la sua ipotenusa lunga 3 volte l'ipotenusa del triangolo rosso, ed avendosi la medesima proporzione tra i cateti maggiori).

Il triangolo verde ha quindi lati $l,3l,6$, da cui segue, per il teorema di Pitagora, che $l^2+9l^2=36$ ovvero $10l^2=36$ e quindi $l^2=\frac{36}{10}$ che è l'area del quadrato.

Here's an interesting question: given a target integer $n$, what's the smallest number of (significant) digits an integer must have in a given base so that it contains as substrings all integers from $0$ to $n$?

Let's clarify with some examples, and assume for simplicity that we're working in base 10.

Obviously, for $n<10$, the minimum number of digits to have all numbers from $0$ to $n$ is $n+1$, since all numbers from $0$ to $n$ are (distinct) single-digit numbers, so, for example, for $n=9$ you need a $10$-digit number at least ($9876543210$ would do, but so would $1023456789$; the actual number doesn't matter, we only care about the number of digits).

With two-digit numbers, things become more interesting. For example, the same $9876543210$ also has $10$ as a substring, so it works for $n=10$ too. It doesn't work for $n=11$ though —and for that you can prove that you need at least an $11$-digit number because you need a repeated digit (for example, $98765432110$). With $n=12$ you want to have substrings $10,11,12$, and while the $11$ can share its final digit with either the $10$ or the $12$, it can't do both, so it will need to be something like $987654312110$, a 12-digit number.

The same argument can be repeated up to $n=19$ ($1918171615141312110$), a 19-digit number, and even for $n=20$ you'll need to at least add a $0$ after the existing 2 ($19181716151413120110$) since you can't share the 0 used for $0$ and $10$ … which is a pity, because this splits the $2$ from the $1$ that could be otherwise be used for $n=21$, so we need an extra digit ($191817161514131202110$). Similarly, we can't easily recycle the two $2$s we have to get to $n=22$ (we need $20$, $21$ and $22$), so we'll need another digit ($1918171615141312022110$, a 22-digit number), but then for $n=23$ we can't just add one digit, because we need both another 2 and another 3: $n=23$ needs a 24-digit number, and the same “+2” growth is needed for all numbers up to $n=29$, leading to the monstrous 36-digit number $191817161514131202211023242526272829$.

Things then slow down again: for $n=30$ we just need to add a single digit, $1918171615141312022110230242526272829$, and this same number works for $n=31$, but not for $n=32$ because we split the 3 from the 2 again …

How does the pattern flow then as $n$ grows larger? On the one hand, there should be more opportunities to use digits for multiple purposes: on the other, you need more combinations.

Is there some kind of law that can describe the pattern? Are there more opportunities to find numbers with less digits if they are rebuilt from scratch for the target $n$, or if they are built with small changes from the previous one(s)?

UPDATE #1: a discussion thread on the Fediverse with @mau@frenfiverse.net mentions that the number of digits needed is monotonic non-decreasing. This is obvious, but just in case here's a short proof.

Let ${\sigma }_b$ be the function that maps the target number $n$ to the minimum number of digits needed in bases $b$. This means that if $k={\sigma }_b\left(n\right)$ then there is an integer with $k$ (significant) digits in base $b$ that includes as substrings all integers from $0$ to $n$. Let's call such a number a $k$-digit representative of the target $n$ in base $b$. (Note that as exemplified in the beginning, there may be multiple representatives.)

Now consider $k_1={\sigma }_b(n+1)$. If must be $k_1\ge k$ because by definition of $\sigma$ there is an integer with $k_1$ significant digits in base $b$ that includes as substrings all integers from $0$ to $n+1$, which includes all integers from $0$ to $n$: if $k_1$ was strictly less than $k$, we could use the $k_1$-digit representative of $n+1$ also for $n$.

@mau also provides an example sequence of representatives in base 2, but I think it can be improved a little. Remember that the integers in base 2 go: 0, 1, 10, 11, 100, 101, 110, 111, 1000, … and a sequence of representatives could be: 0, 10, 10, 110, 1100, 101100 (@mau proposes 110100) 101100 (ditto), 1011100, 10111000, …

It doesn't look like OEIS has anything like this, so it might be really worth exploring this better.

The one thing that seems to emerge at least with small numbers and bases 2 and  10 is that $\sigma \left(n\right)\ge n$. Does this hold for larger targets? Does it all in all bases? (I'm particularly curious about the latter for odd balanced bases.)

And for those that enjoy pure math the most when it doesn't seem to have any applications, I strongly doubt somebody will ever find a practical application to this, other than in the game I play with my kids to avoid car boredom.

UPDATE #2: new discussion thread on the Fediverse. @wqferr@mathstodon.xyz points out that this problem may be related to (generalized) superpermutations, especially when $b=2$, and @mrdk@mathstodon.xyz relates it to de Bruijn sequences. There are are still some significant differences in the rules that the representative should follow that have a significant impact on the number of digits, but we seem to be getting somewhere.

.mau. propone per oggi un quizzino della domenica di stampo geometrico: è piú lunga la linea blu o quella rossa nel disegno seguente?

La spezzata blu seguete il bordo superiore del rettangolo ed il lato destro, mentre la spezzata rossa è formata da tre segmenti uguali. Essendo il rettangolo formato da quattro quadrati, la spezzata blu ha lunghezza $(4+1)l=5l$ dove $l$ è il lato del quadrato. La domanda quindi è: quanto è lunga la spezzata rossa? La risposta è ovviamente $3s$ dove $s$ è la lunghezza del singolo segmento.

Osserviamo che i segmenti da cui è composta la spezzata rossa sono le diagonali di altrettanti rettangoli (uguali poiché uguali sono i segmenti) la cui unione è il rettangolo originario.

Prendiamo uno di questi sotto-rettangoli ed osserviamo che per costruzione il lato lungo è $\frac{4}{3}$ di $l$, e per evitare di lavorare con le frazioni, poniamo $l=3u$.

Abbiamo quindi che la spezzata blu ha lunghezza $5l=15u$, mentre un singolo segmento $s$ della spezzata rossa è la diagonale di un rettangolo di lati $3u$ (lato corto) e $4u$ (lato lungo). Per il Teorema di Pitagora (o semplicemente ricordando che $(3,4,5)$ è una terna pitagorica) ne segue che $s$ ha lunghezza $5u$, e quindi la spezzata rossa ha lunghezza $3\times 5u=15u$.

Le due spezzate hanno la medesima lunghezza.

(Curiosità: siamo abituati a “tagliare in diagonale” per accorciare la strada, questo è un curioso esempio di un modo di farlo lasciando invariata la lunghezza complessiva del percorso.)

Introduction

You can find an introduction to the legendary “Question Six” in this Numberphile video. This article is my attempt at providing a “simple” answer to the problem, sketched from the hints provided in this more detailed insights video.

To be clear this isn't my personal “best effort” at trying to solve the problem (I did give it a quick try, starting from an intuition that induction would be the key, but I didn't get very far in). I also have no idea if this is how it was solved by any of the candidates that did provide the correct answer to the problem.

No, this is just a formalization into an actual proof of the hints provided by Simon Pampena in the second video. The proof should still be easy to follow even with only a basic knowledge of algebra.

The problem

Let $a$ and $b$ be positive integers such that $ab+1$ divides $a^2+b^2$. Show that

$$\frac{a^2+b^2}{ab+1}$$

is the square of an integer.

The solution

Let

$$f(x,y)=\frac{x^2+y^2}{xy+1}.$$

We want to show that if $a,b$ are positive integers and $f(a,b)$ is an integer, then $f(a,b)$ is a square.

Observe first that if $a,b$ are non-negative integers, and one of them is 0, then the statement is trivially true, since $f(a,0)=a^2$ and $f(0,b)=b^2$.

Assume now that $a_0,b$ integers with $0<a_0<b$ are such that $f(a_0,b)$ is an integer. We want to show that there exist a non-negative integer $a_1<a_0$ such that $f(a_1,a_0)=f(a_0,b)$. Note that with this proven, we can apply the result iteratively, constructing a sequence $\left\{a_i\right\}$ with $0\le a_{i+1}<a_i$ and such that $f(a_{i+i},a_i)=f(a_0,b)$. Given the strictly decreasing nature of the sequence and the non-negativity of the values, the sequence will terminate in $k<a_0$ steps, with $a_k=0$, leading to $f(a_0,b)=f(0,a_{k-1})=a_{k-1}^2$, proving that $f(a_0,b)$ is the square of an integer.

Let us then prove the existence of $a_1$. Let $N=f(a_0,b)$. By hypothesis, $N$ is an integer and we have

$$\frac{a_0^2+b^2}{a_{0}b+1}=N$$

that with simple algebra can be rearranged into

$$b^2-N{a}_{0}b+a_0^2-N=0. (\star )$$

This implies that the quadratic equation

$$x^2-N{a}_{0}x+a_0^2-N=0$$

has the solution $x=b$. Dividing the polynomial

$$x^2-N{a}_{0}x+a_0^2-N$$

by $x-b$ gives us1 the second root, $a_1=N{a}_0-b$, which again is an integer.

We need to show that $a_1<a_0$, i.e.

$$N{a}_0-b<a_0$$

or equivalently

$$N{a}_{0}b-b^2<a_{0}b.$$

Note that by bringing the leftmost two terms in the right-hand side of equation $(\star )$ to the left-hand side and flipping the equation, we have

$$N{a}_{0}b-b^2=a_0^2-N$$

but since $a_0<b$, this implies:

$$N{a}_{0}b-b^2=a_0^2-N<a_{0}b-N<a_{0}b$$

and thus

$$N{a}_{0}b-b^2<a_{0}b,$$

quod erat demonstrandum.

xmau propone per oggi un quizzino della domenica che consiste nel “risolvere” una semplice somma espressa utilizzando i numerali romani (I, V, X) in maniera impropria: invece di rappresentare addendi e risultato semplicemente esprimendo i numeri con il meccanismo romano, i numeri sono espressi nel sistema decimale posizionale che ci è familiare, ma ciascuna delle cifre è espressa con i numerali romani1: I per 1, II per 2, III per 3, IV per 4, V per 5, VI per 6, VII per 6, VIII per 8, IX per 9, con l'aggiunta difficoltà dell'assenza di spazi tra le cifre.

L'esposto del problema è il seguente:

IVIIIIIVIII +
IIVIIIII    =
-------------
VIIXIVI

L'assenza di spazi è proprio ciò che rende questa una “crittosomma”: è infatti impossibile, con un semplice colpo d'occhio, capire ad esempio se una sequenza come III rappresenta la cifra 3 o una delle coppie di cifre 21 e 12.

L'unica “sequenza” di cui possiamo essere sicuri è IX, giacché X rappresenta il valore 10 secondo il sistema di numerazione romano, e nel sistema posizionale da noi adottato non esiste una cifra con questo valore, per cui IX è sicuramente 9. Possiamo quindi “semplificare” la nostra crittosomma in:

IVIIIIIVIII +
IIVIIIII    =
-------------
VI9IVI

Rimangono da interpretare le due sequenze di numerali romani nella somma finale: VI, che può essere 6 o 51, e IVI che può essere interpretata in tre modi diversi: 151, 41, e 16.

Un dubbio

Un problema aperto (che speriamo non sia determinante per la soluzione) è la lettura delle cifre: le piú significative saranno scitte a destra, come vuole la convenzione che abbiamo ereditato dagli arabi, o saranno scritte a sinistra, come sembra suggerire l'allineamento?

Alla prova del 9

Per cercare di limitare le possibili interpretazioni possiamo osservare che non tutte le interpretazioni hanno la stessa congruità modulo 9. Specificamente, mentre le sequenze “additive” (simbolo di valore maggiore seguito da simboli di valori non inferiori) hanno tutte lo stesso valore modulo 9, quelle potenzialmente sottrattive (simbolo di valore inferiore seguito da simbolo di valore maggiore) possono avere due possibili interpretazioni, con valori modulo 9 che differiscono di un valore pari alla differenza tra il valore additivo e quello sottrattivo del simbolo di valore inferiore.

Nel nostro caso, le uniche coppie ambigue sono IV per cui la differenza di valore sarà 2. Come esempio, vediamo che VI alla “prova” del 9 darà sempre 6 (sia che venga letto come 6, sia che venga letto come 51), per IV abbiamo due valori diversi a seconda che IV abbia valore “additivo” (15 = 6) o “sottrattivo” (4).

Per la somma finale, alla prova del 9 abbiamo quindi due possibili valori: 4 (interpretazione additiva di IV) oppure 2 (intepretazione “sottrattiva” di IV).

Il secondo addendo ha pure un'unica sequenza IV, e quindi due interpretazioni: 3 (additiva) e 1 (sottrattiva).

Il primo degli addendi ha invece due sequenze IV , e quindi ha tre possibili valori (a seconda che le due sequenze siano entrambe additive, entrambe sottrattive, o una additiva ed una sottrattiva, indipendentemente da quale sia quale): i valori associati sono 1 (additive), 6 (sottrattive) e 8 (mista).

Alla prova del nove, le possibili combinazioni dei due addendi sono: $1+1=2$, $1+3=4$, $6+1=7$, $6+3=8+1=0$, $8+3=2$. Poiché la somma è congrua 4 o 2 modulo, possiamo scartare per il primo addendo l'interpretazione sottrattiva: quindi o entrambe le sequenze del primo addendo vanno lette additivamente, oppure la lettura del primo addendo è mista, e quella del secondo è additiva (caso $8+3=2$).

La cifra piú a sinistra

La cifra piú a sinistra della somma è 5 o 6, e quindi le cifre piú a sinistra dei due addendi devono arrivare almeno a 4 o 5, piú un opzionale riporto dalle due cifre successive (supponendo che la notazione metta a sinistra le cifre piú significative).

Osserviamo subito che questo non è possibile se per il primo addendo si utilizza la lettura puramente additiva: in tal caso infatti la cifra piú a sinistra del primo addendo è 1, mentre quella del secondo è al piú 2, arrivando a 3, che è insufficiente.

Ne segue che per il primo addendo si deve usare la lettura mista, con la prima sequenza IV interpretata sottrattivamente (ed a fortiori la seconda interpretata additivamente). Questo ci porta quindi nel caso $8+3=2$ della prova del9, che implica un'interpretazione additiva del secondo addendo, e sottrattiva della somma: la sequenza IVI con cui termina quest'ultima può pertanto essere letta solo come 41.

Possiamo quindi ulteriorimente semplificare la nostra crittosomma in

4IIIIIVIII +
IIVIIIII   =
------------
VI941

Dei rimanenti simboli V sappiamo che vanno interpretati additivamente, e quindi o avranno valore 5 (a sé stanti) o saranno parte di sequenze per 6, 7 oppure 8.

Il lungo problema dell'1

Un terzo aiuto nel vincolare le interpretazioni ci viene dal possibile numero di cifre. Per la somma abbiamo solo due possibili interpretazioni: 6941 e 51941, di lunghezza rispettivamente 4 e 5. Nessuno dei due addendi può avere una lunghezza superiore (potrebbero avere una lunghezza inferiore se le cifre meno significative fossero a sinistra ed avessimo un riporto tra quelle piú significative, a destra).

Questo vincolo risulta particolarmente potente in congiunzione con il problema dell'1: un interessante corollario dell'uso del sistema numerico romano per la rappresentazione delle cifre è l'assenza di un modo per rappresentare lo 0: questo ci aiuta perché, non potendovi essere 0 negli addendi, l'unica cosa che può fare spuntare la cifra 1 nella somma è una coppia di cifre con riporto.

Guardando alla somma, abbiamo due possibili interpretazioni rimaste: 6941, e 51941. La seconda, in particolare, ha un 1 in seconda posizione (non sappiamo ancora se per le decine o per le migliaia), e questo non è ottenibile in alcun modo.

Supponiamo infatti che la lettura corretta della somma sia 51941. La cifra piú a sinistra del secondo addendo dovrà quindi essere 1, poiché se dovessimo leggere la sequenza iniziale II come 2, avremmo $4+2=6$. (L'alternativa per arrivare a 5 come cifra piú a sinistra piú significativa richiederebbe un riporto dalle cifre precedenti, che però possono essere lette al massimo come $5+2=7$, e non potremo mai avere un riporto di $4$ dalle cifre ancora precedenti per arrivare ad un riporto dalle seconde.)

Saremmo quindi a

4IIIIIVIII +
11VIIIII   =
------------
51941

ma diventa a questo punto impossibile ottenere un 1 in seconda posizione, non potendo esserci uno zero nel primo addendo, o un riporto tale da lasciare un 1.

L'unica lettura possibile per la somma è quindi 6941, e questo richiede (sempre per una questione di riporti) che la cifra piú a sinistra del secondo addendo sia un 2: la nostra crittosomma è ora parzialmente risolta come

4IIIIIVIII +
2VIIIII    =
------------
6941

e possiamo affermare che tutti e tre i termini sono composti da 4 cifre: potrebbero essere 3 con un opportuno riporto dalla somma delle cifre piú significative, ma il primo addendo non può avere solo 3 cifre.

Il vincolo sulle lunghezze è particolarmente importante per l'interpretazione del secondo addendo, per il quale rimangono 6 simboli per 3 cifre, con poche letture possibili: 811; 721 o 712; 631, 622 o 613, ed infine 532 o 523.

Anche qui ci viene in aiuto la questione dell'1 (terminale, stavolta), che risolve, insieme al vincolo delle lunghezze, anche la questione dell'ordine delle cifre: l'unico modo per ottenere un 1 come cifra piú significativa sarebbe un riporto da due addenti con tre cifre, e come già detto il primo addendo non può avere solo 3 cifre.

Da questo si deducono due fatti importanti: le cifre meno significative sono a destra (quindi alla fine otterremo numeri con le cifre ordinate secondo la convenzione cui siamo abituati), e per gli addendi queste sono rispettivamente 8 e 3, le uniche letture possibili per ottenere un riporto che ci lasci indietro l'1 della somma:

4IIIII8 +
2VII3   =
---------
6941

che lascia come possibili letture per il secondo addendo solo 2613 o 2523. E poiché dobbiamo arrivare a 9 come seconda cifra da sinistra, ed abbiamo al piú 3 dal primo addendo, e nessun riporto, la cifra dopo il 2 deve essere un 6, con un 3 in sua corrispondenza sul primo addendo, che ci permette una completa risoluzione del problema:

4328 +
2613 =
------
6941

xmau propone per oggi un quizzino della domenica che consiste nel trovare la singola cifra (di quelle da 1 a 9) che rimane fuori inserendo nelle caselle del seguente schema le altre otto:

Il quiz chiede di trovare la cifra “in piú”, e per farlo è sufficiente (ma, come vedremo, non necessario) risolvere lo schema.

Cominciamo dalla riga superiore: abbiamo una divisione $a:b=c$ in cui i tre numeri $a,b,c$ devono essere tutti distinti tra loro e compresi tra 1 e 9. Questo ci aiuta ad escludere, come valori possibili di $a$, sia l'1, sia i numeri primi (2, 3, 5, 7) sia i quadrati (4, 9), ciascuna con motivazioni diverse:

• se $a=1$, allora deve essere $b=c=1$, e quindi abbiamo ripetizioni;
• se $a$ è primo, dovendo essere $b\ne a$ dovrebbe essere $b=1$ (poiché $a$ non ha altri divisori, essendo primo), e quindi $c=a$ (ripetizione);
• se $a$ è un quadrato, come divisori ha solo $1,a$ (esclusi), o un terzo valore $b\ne a$ per cui $a:b=b$, nuovamente una ripetizione.

Gli unici valori possibili per $a$, ovvero per la casella in alto a sinistra dello schema, sono quindi 6 oppure 8, per cui gli unici valori possibili per le altre due caselle della prima riga sono 2, 3 oppure 4.

Osserviamo ora che la colonna di destra di fatto è analoga alla riga superiore, poiché $a:b=c$ è equivalente a $c\times b=a$: la casella in basso a destra vale quindi 6 oppure 8, e la casella centrale della colonna vale pure 2, 3 oppure 4.

Quindi o la casella in alto a sinistra vale 6, e quella in basso a destra vale 8, oppure è al contrario. In entrambi i casi, possiamo osservare che la casella in alto a destra deve essere il divisore comune a 6 ed 8, e quindi deve essere 2.

Usando una notazione simil-sudoku possiamo scrivere:

e la presenza delle coppie 3/4 e 6/8 ci permette di escludere questi 4 valori dalle tre caselle mancanti, che possono quindi solo contenere i valori 1, 5, 7 e 9.

Soluzione del quiz

Osserviamo che già ora, senza completare lo schema, possiamo dire quale valore sarà escluso: nessuna delle tre caselle rimanenti, infatti, può avere valore 9, giacché questo renderebbe impossibili le operazioni necessarie per arrivare rispettivamente a 6 o 8.

La risposta al quiz è quindi: il 9 è la cifra mancante.

Completamento dello schema

Come per il lato superiore e quello destro, possiamo osservare che il lato sinistro e quello inferiore presentano la medesima simmetria: la sottrazione sul lato sinistro è equivalente alla somma sul lato inferiore. Ragionando analogamente a quanto visto per la divisione e la moltiplicazione, possiamo quindi dire che la casella inferiore sinistra prenderà l'addendo comune (in questo caso, 1) e le altre due caselle avranno rispettivamente 5 e 7, a seconda di dove saranno 6 ed 8.

Per completezza, possiamo quindi osservare che lo schema ha due possibili soluzioni, rivelate passando il cursore del mouse sull'immagine seguente (a sinistra e a destra per risultati diversi):

There is something I learned today that, as a mathematician, I should have probably learned some time ago: the name of the function that solves the equation

$$x{e}^x=y$$

where $e$ is Napier's constant. I did know that the equation didn't have an elementary solution, but that didn't really help me solving the problem I wanted to solve, which was to find a solution to the equation:

$$x^2{e}^{kx}=c$$

for positive $k,c$ (and $x$ too, for what it's worth).

Apparently the non-elementary function we're interested in is called Lambert's $W$ or $\omega$ function, or the product logarithm. It is the (multi-valued, in fact) function such that

$$x=W\left(y\right)\iff y=x{e}^x.$$

The name product logarithm comes from the analogy with the (natural) logarithm

$$x=ln\left(y\right)\iff y=e^x$$

and the fact that there's an extra $x$ multiplying the exponential on the right hand side of the equation we want to invert (solve for $x$).

I'm not going to discuss the properties of the function (I mean, what would the Wikipedia link above be here for, otherwise), but I will show how it can be used to solve the equation we're interested in, something that is not shown on Wikipedia and actually had me thinking for a while —mostly about the fact that I was obvioulsy missing something trivial, as it often happens in mathematics.

The general idea, to use the product logarithm in solving an equation, is to bring it in the form

$$f\left(x\right)e^{f\left(x\right)}=c$$

which then leads to

$$f\left(x\right)=W\left(c\right)$$

and finally, assuming $f$ is invertible, to $x=f^{-1}\left(W\left(c\right)\right)$. Of course, how to get to the form we want is not always obvious.

Let us take for example the equation I wanted to solve:

$$x^2{e}^{kx}=c.$$

Making sure $k$ appears both as power of $e$ and outside of it is trivial: simply multiply by $k$ both sides. However, how to make sure we have the same power of $x$ muliplying the exponential and as a power is not: the most obvious ideas (divide by $x$ both sides, or multiply and divide by $x$ the power and then try to juggle things around) don't really take you anywhere.

We'd have to be able to take the square root … wait, that might actually work!1 If we take the square root on both sides, then we get two equations (with the only difference being the sign, so we'll write it as one):

$$x{e}^{\frac{k}{2}x}=\pm \sqrt{c}.$$

Now we can balance the constants:

$$\frac{k}{2}x{e}^{\frac{k}{2}x}=\pm \frac{k}{2}\sqrt{c}$$

and apply the definition of $W$ to get

$$\frac{k}{2}x=W(\pm \frac{k}{2}\sqrt{c})$$

and finally

$$x=\frac{2}{k}W(\pm \frac{k}{2}\sqrt{c}).$$

As mentioned, $W$ is a multi-valued function. However, for the specific application we derived the equation for we needed the largest positive value, meaning we need specifically the $W_0$ branch (which is the only one that gives positive value), and since $W_0$ is monotone increasing, we want the solution with the largest argument, that is, ultimately:

$$x=\frac{2}{k}{W}_0\left(\frac{k}{2}\sqrt{c}\right),$$

a surprisingly elegant formula —for which there is no built-in function in the C++ standard library.

(Surprisingly, making the latter discovery wasn't enough to reduce my enthusiasm and satisfaction in finding the answer and discovering the function, although it will be a problem I'll have to solve in the next few days —I'm not really looking forward to having to include the GSL or Boost libraries just for this.)

Nation, flags and memory card games

One of the “portable” games offered by Flying Tiger is a memory card game with national flags as a theme. The game has $68$ cards ($34$ national flags) and I like it not only because it's one of the largest memory games I've seen, if not the largest (about $50$ cards or fewer being the norm, for what I can see), but also because of its educational side-effect, as each card features not only the flag, but also (in the “native” language as well as in English) the name of the nation and the name of the capital city.

After the first play, my first consideration was that Mexico was missing from the flags/nations (why Mexico? personal reasons). The next thing I noticed was that the selection of nations is essentially centered around Europe, with only a handful of extra-European nations included. This is when I realized how small the selection is: $34$ nations is less than a fifth of the nations of the world, even if you consider the smallest possible set (the $190$ states whose sovereignity is undisputed).

So obviously, my next thought was: how large would such a memory card game be? $190$ states (at least) means $190$ pairs, or $380$ cards. The Flying Tiger cards are squares (with rounded corners) with a side length of $55$mm, and I don't think it's reasonable to go much smaller. In fact, considering the padding between cards that is needed for practical reasons when laying them down for playing, we can assume square tiles with a $6$cm side. That's $36$cm², or $0.0036$m² per tile. $380$ such tiles would cover an area of $1.368$m².

Curiously, $380$ is very close ${19.56}^2$, which means that if the $190$ pairs were laid out in a square, they would take up a square area with a side of almost exactly $117$cm, or $1.17$m. Even I would have troubles reaching the cards on the opposite side of the table. Of course, you can't actually do that, because $380$ is not a perfect square, so you cannot tile the cards on a square: you would have to either have to do a $19\times 20$ rectangle (with sides of length $1.14$m and $1.2$m respectively), or a $20\times 20$ square with an empty diagonal.

The issue of placing the memory cards in a pleasing pattern has always fascinated me. My daughter has a $48$-cards game, which I like because the card can be laid out in a $7\times 7$ square with a hole in the center. My son has a $32$-cards game that can be laid out as a $6\times 6$ square with missing corners.

In fact, the $68$-cards game that spurred these consideration is a bit annoying because $68=8\times 8+4$, but the 4 extra cards cannot be placed in a nice symmetric way with good alignment because the sides of the square are even, not odd. Possible placemets are the “wheel” pattern (extending each of the sides with one card), the “shifted” pattern (place each extra card on the middle of each side, spanning the gap between the two central cards of the side), or the “versus” pattern, good when playing 1v1 games, with two extra cards on each of two opposing sides.

Obviously, the next question is: how many nations would you have to include to be able to tile out the cards in a “good” pattern?

Perfect squares

this solution can be achieved with $20\times 20=400$ cards, or $200$ states (note that without holes or extra cards, the square must be even); problem is, Wikipedia lists $206$ states when including the ones with disputed sovereignity; we'd have to cherry-pick some, leaving out six of them;

The hole

an odd square can be made even by taking out a central hole;

a possible solution would be $19\times 19-1=360$, but this would require removing $10$ nations from the “uncontroversial” list;

the next one would be $21\times 21-1=440$, which would require $220$ states: can we find $14$ other territories to add to the $206$ states currently listed by Wikipedia?

Give or take more

good patterns can be obtained by removing the 4 corners, or by having 4 extra cards —particularly with an odd square;

$20\times 20-4=396$ would require $198$ states, which could be assembled from the $193$ UN member states, the $2$ observer states, plus more (decisions, decisions);

$21\times 21-1-4=436$ would require $218$ states: we'd only need to find $12$ more than the ones listed by Wikipedia.

$19\times 19-1+4=364$ would require $182$ states: still too little;

As it turns out, $380$ isn't even that bad: since $19\times 19-1+4\times 5=361-1+20=380$, a decent tiling can be found with a $19\times 19$ square, without the center, plus $5$ cards centered on each side.

And a long stick to pick the cards on the other side of the table.

But I want more

Revision 6.0 of the Unicode standard introduced Regional Indicator Symbols and their ligatures mapping to «emoji flag sequences». Of the $26\times 26=676$ possible combinations, only $270$ are considered valid, and if we ignore the $12$ «deprecated region sequences», this leaves us with $256+2=258$ “current” region sequences. We could use this as the basis for our memory card game!

With $258$ regions we have $258\times 2=516$ cards. What would be a good pattern? We have $516=22\times 22+32=22\times 22+4\times 8$ which actually lends itself to a decent layout: a $22\times 22$ square, plus $8$ cards centered on each side.

How large would such a memory game be? At $6$cm per tile, the main square wold be $1.32$m wide. The extra cards on each side would make it $1.44$m wide, which is actually a pretty nice number1 —if unwieldy in practice. Still, if we're basing our choice on what Unicode supports, why not build such a game around computers? You'd need lots of players to make sense of it anyway.

Something that everybody (but the staunchiest believer in a Flat Earth) can agree on is that you can see farther by climbing higher. Indeed, getting to a higher place not only helps you see beyond any obstacles that might be in your line of sight, but it actually helps you see farther along the surface of the Earth even if there are no other obstacles than Earth's own curvature: it's the reason why ships have a Crow's nest.

So the obvious question is: how much farther can you see by climbing higher? And people that follow me will surely have already caught on: yes, we're trying to solve the inverse problem to how high do you have to go. In fact, we'll recycle the figure:

Again, we assume we're dealing with a spherical Earth of known radius $r$. This time, however, we assume $h$ known (how far high we are), and we want to know $d$, the distance along the geodetic to the farthest point we can see1. Equivalently, we want to know the angle $\alpha$ subtending the geodetic, since by definition of radian its amplitude in radians is just $\frac{d}{r}$, hence $d=r\alpha$. And again, of course, we know that it will be for sure $0\le \alpha <\frac{\pi }{2}$, i.e. $2d<\pi r$.

In fact, from our study on the direct problem we know that the relationship between $h$ and $\alpha$ can be expressed as

$$h=r(\frac{1}{cos\alpha }-1)$$

which we can invert rather easily; divide by $r$:

$$\frac{h}{r}=\frac{1}{cos\alpha }-1$$

add $1$ on both sides:

$$\frac{h}{r}+1=\frac{1}{cos\alpha }$$

and take the reciprocals, swapping the two sides:

$$cos\alpha =\frac{1}{\frac{h}{r}+1}.$$

Given our range of existence for $\alpha$, we can use the inverse function of the cosine, $arccos$, to get the final formula for $\alpha$

$$\alpha =arccos\left(\frac{1}{\frac{h}{r}+1}\right)$$

and from this get

$$d=r\alpha =rarccos\left(\frac{1}{\frac{h}{r}+1}\right).$$

As a quick check, for $h=0$ we have $\alpha =arccos1=0$, while for $h$ growing to infinity we get $\alpha =arccos0=\frac{\pi }{2}$, as we would expect.

Approximation?

As with the previous problem we would like to devise a formula that can be applied easily under the assumption that the angle is small. The most obvious approach would be to use the first term(s) of the Taylor expansion of the arc cosine, as it's usually done for small-angle approximations. However, Taylor series for these functions are usually developed around 0, whereas we would like to develop them around 1, since a small angle, in our case, leads to an argument of 1 for the arc cosine.

(In fact, we can see that better if we focus on the argument to the arc cosine:

$$\frac{1}{\frac{h}{r}+1}=1-\left(\frac{h}{r}\right)+{\left(\frac{h}{r}\right)}^2-{\left(\frac{h}{r}\right)}^3+...$$

assuming $h<r$.)

From a mathematical perspective, writing a Taylor expansion of $arccos$ around 1 is not recommended, since some assumptions needed to ensure good convergence behavior for the series cannot be guaranteed (in particular, the fact that 1 is at the boundary of the domain of the arc cosine rather than inside it is a no-no).

Worse, if we opt to disrergard the warning, we find out that we can't even do what we want, since the derivative of the arc cosine is

$$-\frac{1}{\sqrt{1-x^2}}$$

which isn't even defined for $x=1$.

We could try leveraging the nice relationship between the arc cosine and the arc secant:

$$arccos\left(\frac{1}{\frac{h}{r}+1}\right)=arcsec(\frac{h}{r}+1),$$

but that barely helps us, since the arc secant's first derivative is

$$\frac{1}{x\sqrt{x^2-1}}$$

for $x>1$ so that again, for $h=0$, we would have a degenerate case.

Look ma, no inverse functions!

To work around this conundrum, let's take a step back, to:

$$cos\alpha =\frac{1}{\frac{h}{r}+1},$$

and let's use the small-angle approximation for the cosine; we get

$$1-\frac{{\alpha }^2}{2}=\frac{1}{\frac{h}{r}+1}$$

or

$$\frac{{\alpha }^2}{2}=1-\frac{1}{\frac{h}{r}+1}=\frac{\frac{h}{r}}{\frac{h}{r}+1}=\frac{h}{h+r}$$

which gives us a much more approachable

$${\alpha }^2=2\frac{h}{h+r}$$

and finally, with an ugly square root,

$$\alpha =\sqrt{2\frac{h}{h+r}}.$$

In fact, there's two horrible things in this formula: the division of a (potentially) very small number by a very large number, and a square root.

For the ratio, we can rewrite things with our friend $q=\frac{r}{h}$ under the assumption that $h\ne 0$ (sensible, since otherwise $\alpha =0$, which isn't very interesting):

$$\alpha =\sqrt{\frac{2}{1+q}}$$

with $q$ large (in fact, potentially tending to $+\infty$).

As it turns out, ignoring for a moment the $\sqrt{2}$ factor, the rest has a power series expansion, in the form of a Puiseux series that can be written in an acceptable form in terms of $p=\sqrt{\frac{1}{q}}=\sqrt{\frac{h}{r}}$:

$$\alpha =\sqrt{2}(p-\left(\frac{1}{2}\right)p^3+\left(\frac{3}{8}\right)p^5-\left(\frac{5}{16}\right)p^7+\cdots ).$$

Curiously (but unsurprisingly) the first order term is what we get if we just ignore the 1 in the non-expanded formula.

More in general, we shouldn't be surprised by the need to compute $p$ with a square root, given that in the other direction we used $s=2q^2$. But then again, if we have to compute a square root, why even bother doing it for $p$ when we can do it directly for $\alpha$?

So, shall we just stop at

$$d=r\alpha =r\sqrt{\frac{2}{1+q}}$$

or can we do something more interesting?

(Aside for local manipulations, such as:

$$d=r\sqrt{2\frac{h}{h+r}}$$

of course.)

Another rollback

To find a better formula, let's roll back to

$$1-\frac{{\alpha }^2}{2}=\frac{1}{\frac{h}{r}+1}$$

and work on the right-hand side, which we can write as ${(1+\frac{h}{r})}^{-1}$. For small $h$ (compared to $r$) this has a curiously nice expansion:

$$1-\frac{h}{r}+{\left(\frac{h}{r}\right)}^2-{\left(\frac{h}{r}\right)}^3+\cdots$$

so that our equation for $\alpha$ becomes:

$$\frac{{\alpha }^2}{2}=\frac{h}{r}-{\left(\frac{h}{r}\right)}^2+\cdots$$

and truncating:

$$\frac{{\alpha }^2}{2}=\frac{h}{r}(1-\frac{h}{r}),$$

but also

$$\frac{{\alpha }^2}{2}={\left(\frac{h}{r}\right)}^2(\frac{r}{h}-1).$$

The nice thing about these formulas is that we can rewrite the right-hand side in terms of $q$, giving us

$$\frac{{\alpha }^2}{2}=\frac{1}{q}(1-\frac{1}{q})=\frac{q-1}{q^2}$$

which comes in very handy if we don't stop at $\alpha$, but actually go and compute $d$:

$$d=r\alpha =r\frac{\sqrt{2(q-1)}}{q}=h\sqrt{2(q-1)}=h\sqrt{2\frac{r-h}{h}}$$

that is interesting since it expresses the distance in terms of “the height, multiplied by something” rather than “the radius of the planet, multiplied by something”.

In fact, in this case we can even try pulling out the 2 from under the square root:

$$d=2h\sqrt{\frac{r-h}{2h}}$$

(well, sort of; but at least it has some symmetry to it).

A different approach

Remember that we could also express $h$ as the exterior secant, that could be expressed in terms of the tangent function, giving us

$$h=rtan\left(\alpha \right)tan\left(\frac{\alpha }{2}\right).$$

Can we try inverting this instead? Let us proceed by expressing the tangent in terms of $t=tan\left(\frac{\alpha }{2}\right)$:

$$h=r\frac{2t}{1-t^2}t=r\frac{2t^2}{1-t^2}$$

and let's solve for $t$:

$$h(1-t^2)=2r{t}^2$$

$$(2r+h)t^2=h$$

$$t^2=\frac{h}{2r+h}.$$

We can go for a direct solution now, with

$$\frac{\alpha }{2}=arctan\left(\sqrt{\frac{h}{2r+h}}\right).$$

The good news is that, in contrast to the situation with the arc cosine, we would need to go now for the expansion of the arc tangent for small values of the tangent, which is just its argument, giving us the following approximation:

$$\frac{\alpha }{2}=\sqrt{\frac{h}{2r+h}},$$

or

$$\alpha =2\sqrt{\frac{h}{2r+h}},$$

If instead we wanted to use small-angle approximation for $t$, giving us $t^2=\frac{{\alpha }^2}{4}$, we'd get

$${\alpha }^2=4\frac{h}{2r+h},$$

or finally

$$\alpha =2\sqrt{\frac{h}{2r+h}}.$$

Would you look at that, it's the same formula! That's good news, like the fact that the 2 is already out of the square root (well, at least one of them!) and when we go for $d$:

$$d=2r\sqrt{\frac{h}{2r+h}}$$

we have the same nice symmetry that we had with the previous approach —but no $h$ outside of the square root.

Going crazy

As an alternative, we could leverage that fact that $0\le \alpha <\frac{\pi }{2}$, so that we are in the range where

$$tan\left(\frac{\alpha }{2}\right)=\frac{tan\alpha }{1+\sqrt{1+{tan}^2\alpha }}$$

which would give us

$$h=r\frac{{tan}^2\alpha }{1+\sqrt{1+{tan}^2\alpha }}$$

that we can manipulate to

$$1+\sqrt{1+{tan}^2\alpha }=r\frac{{tan}^2\alpha }{h}$$

$$\sqrt{1+{tan}^2\alpha }=r\frac{{tan}^2\alpha }{h}-1$$

$$1+{tan}^2\alpha ={(r\frac{{tan}^2\alpha }{h}-1)}^2$$

$$h^2+h^2{tan}^2\alpha ={(r{tan}^2\alpha -h)}^2$$

$$h^2+h^2{tan}^2\alpha =r^2{tan}^4\alpha -2hr{tan}^2\alpha +h^2$$