John H. Conway & Richard K. Guy, ... - 2020

A poche settimane di distanza, se ne sono purtroppo andati i co-autori del Book of Numbers, John Horton Conway e Richard Kenneth Guy.

John Conway (1937-2020) è stato senz'altro uno dei matematici più geniali ed ecclettici della sua generazione. L'ho più volte menzionato in questo blog, vista la sua visione della matematica, tra il giocoso e il rigoroso, l'ultima volta proprio nel post precedente (mentre lo scrivevo, ero ignaro della sua recente scomparsa). Fra le sue innumerevoli invenzioni, oltre al libro scritto con Guy, potrei menzionare il Monstrous Moonshine, il Teorema Cosmologico, i Numeri Surreali e, naturalmente, l'algoritmo Doomsday e il Game of Life.

La carriera di Richard Guy (1916-2020) spazia su quasi otto decenni; decisivo fu il suo incontro con Paul Erdös, con cui condivise quattro pubblicazioni. Esperto scacchista e editor di riviste sugli scacchi, ebbe un'importante influenza nel campo della matematica ricreativa (oltre che in svariati ambiti della matematica discreta).

Ad accumunare i due matematici, oltre al Libro di numeri, c'è il già menzionato Gioco della vita, l'ipnotico automa cellulare ideato da Conway e studiato da Guy (che, fra le altre cose, descrisse per primo il glider). Le regole sono abbastanza semplici:

Proviamo a giocarci un po' (l'ho rubato qui).

Doomsday+2

È del 2011 un'ulteriore "semplificazione" della formula $$y=\left(x+\left\lfloor\frac{x}{4}\right\rfloor\right)\bmod7$$ ad opera di Chamberlain Fong e Michael K. Walters (vedi qui e, soprattutto, qui). Si tratta di $$y=-\left(\frac{x+11\cdot (x\,{\rm mod}\,2)}{2}+11\cdot\left(\frac{x+11\cdot(x\,{\rm mod}\,2)}{2}{\rm mod}\,2\right)\right){\rm mod}\,7\;.$$

Cos'è 'sta roba? Vi chiederete.

Beh, a dispetto della sua apparente imperscrutabilità, questa versione offre alcuni vantaggi: essa permette di calcolare il valore dello spostamento $y$ con una semplice sequenza di passi che richiedono operazioni aritmetiche molto semplici. Vediamone una parafrasi dettagliata:

• se $x$ è pari, dividi per due; se è dispari, aggiungi 11 e dividi per due;
• se il risultato ottenuto è pari lascialo invariato, se è dispari aggiungi 11;
• calcola il resto della divisione per 7;
• sottrai da 7 quanto ottenuto.

Ad esempio (cfr. con i precedenti post), con $x=71$ iniziamo aggiungendo 11 e dividendo per 2, ottenendo 41, dispari. Aggiungiamo nuovamente 11, ottenendo 52; il resto di 52:7 è 3; sottraiamo 3 da 7, ottenendo 4. Analogamente, da $x=7$ otteniamo 18, dividiamo per 2 ottenendo 9, aggiungiamo 11, il resto di 20:7 è 6, che sottratto da 7 dà 1. Facile, no?

Doomsday+1

Apparentemente, dividere per quattro o per sette un numero di taglia moderata non è un'operazione del tutto agevole. Per questo motivo, nel 1973 Conway propose di rimpiazzare la formula$$ y=\left( x + \left\lfloor \frac{x}{4} \right\rfloor \right) \bmod 7 $$ con l'equivalente$$ y=\left( \left\lfloor \frac{x}{12} \right\rfloor + x \bmod 12 + \left\lfloor \frac{x \bmod 12}{4} \right\rfloor \right) \bmod 7 \quad,$$ che richiede la manipolazione di numeri più piccoli. In effetti, i primi due termini della somma sono quoziente e resto della divisione euclidea $x:12$, e il terzo si ricava facilmente dal secondo. Ad esempio (cfr. con il post di ieri), per $x=71=5\cdot12+11$ occorre calcolare $$ \left(5+11+\left\lfloor\frac{11}{4}\right\rfloor\right) \bmod 7 = \underbrace{\left(5+11+2\right) \bmod 7}_{18\,{\rm mod}\,7} =4 $$ e per $x=7=0\cdot12+7$ $$\left(0+7+\left\lfloor\frac{7}{4}\right\rfloor\right) \bmod 7 = \underbrace{(0+7+1)\bmod 7 }_{8\,{\rm mod}\,7}= 1 \;. $$ 

Oggi è doomsday

(essenzialmente, un altro post ispirato dal geniale John Conway).

L'altra sera, commentando le performances di un astro nascente del mentalismo (nonché mio ex-allievo), il discorso è caduto sulla sua capacità di azzeccare quasi istantaneamente il giorno della settimana relativo ad una qualsiasi data. In effetti, la facoltà potrebbe sembrare quasi paranormale (e magari un po' lo è, vista la sua velocità nell'eseguire i calcoli, anche se forse il suo metodo si basa su una serie di date memorizzate in precenza), ma in realtà l'esercizio è alla portata di chiunque abbia un minimo di scioltezza nel calcolo mentale.

Il procedimento descritto da Conway negli anni '70 (ma ispirato da altri autori, ad esempio Lewis Carroll) si basa sull'osservazione che alcune date facili da memorizzare (l'ultimo giorno di febbraio, la sequenza 4.4/6.6/8.8/10.10/12.12, le coppie 5.9/9.5 e 7.11/11.7, il 3 gennaio negli anni comuni e il 4 gennaio nei bisestili) cadono sempre nello stesso giorno della settimana. Identificato tale giorno, che Conway battezza con il pittoresco nome di doomsday, non è quindi difficile situare nella settimana una data qualsiasi. Ad esempio, dal momento che il doomsday per l'anno 1971 cade di domenica (vedremo poi perché), procedendo a ritroso dall'8 agosto è facile affermare che il sottoscritto nacque di lunedì (2 agosto).

Il problema si riduce quindi alla determinazione del doomsday per un dato anno; osservando che le date corrispondenti avanzano di un giorno all'interno della settimana ogni anno comune (perché $365=52 \cdot 7+1$) e di due giorni ogni anno bisestile (perché $366=52 \cdot 7+2$) non è difficile convincersi del fatto che la formula
$$ y=\left( x + \left\lfloor \frac{x}{4} \right\rfloor \right) \bmod 7 $$ (dove $\lfloor n \rfloor$ è la parte intera di $n$, cioè la sua approssimazione per difetto, e $n \bmod 7$ è il resto della divisione $n:7$) rappresenta lo spostamento dei doomsdays all'interno della settimana dopo che sono trascorsi $x$ anni. Aggiungendo tale spostamento al doomsday del primo anno del secolo (che Conway chiama anchor day), con $x$ pari al numero di anni trascorsi all'interno del secolo è poi facile ricavare il doomsday per l'anno $x$. Ad esempio, per l'anno 1971 poniamo $x=71$ e calcoliamo $$ \left( 71 + \left\lfloor \frac{71}{4} \right\rfloor \right) \bmod 7 = \left( 71 + 17 \right) \bmod 7 = 88 \bmod 7 = 4 \;. $$ Per il XX secolo (1900-1999) l'anchor day è mercoledì; pertanto il doomsday 1971 cade di "mercoledì più quattro", cioè di domenica. Gli anchor days sono facilmente memorizzabili, ripetendosi ogni quattro secoli (dal momento che il calendario gregoriano ha un ciclo di 400 anni): partendo dal 1900, sono mercoledì-martedì-domenica-venerdì (in breve MeMaDoVe).

Calcoliamo, a mo' di esempio conclusivo, il giorno di nascita di un certo Leonhard Euler (15 aprile 1707): la parte intera di 7:4 è 1, aggiungendolo a 7 otteniamo 8, che diviso per 7 dà resto 1; l'anchor day per il '700 è domenica (MeMaDoVe partendo dal '500), quindi il doomsday 1707 cade di lunedì; il 4 aprile (4.4) è un doomsday, aggiungendo 11=7+4 giorni possiamo quindi affermare che Eulero nacque di venerdì.

1, 11, 21,1211,111221,...

... cioè: "uno", "una volta uno", "due volte uno", "una volta due una volta uno"e così via. Probabilmente un po' tutti noi insegnanti di matematica ci siamo visti sottoporre questa bizzarra sequenza di numeri (nota come look-and-say,  numero A005150 dell'OEIS) da qualche intraprendente alunno e probabilmente un po' tutti, dopo aver capito il meccanismo che la genera, l'abbiamo archiviata come una mera curiosità poco matematica. Ma non (come ho appreso leggendo The Irrationals) quel mattacchione di John Horton Conway, che nel saggio The Weird and Wonderful Chemistry of Audioactive Decay prende tale successione terribilmente sul serio, associandole addirittura un enunciato che battezza con il nome altisonante di Teorema Cosmologico. Si tratta in effetti di un risultato piuttosto imprevedibile, che solo una mente non convenzionale come quella del grande matematico inglese avrebbe potuto partorire: essenzialmente, qualunque sia la scelta iniziale delle cifra (non soltanto "1", quindi, ma anche ad esempio "123", che si trasforma in "111213", "31121113" ecc.), a un certo punto (dopo meno di 30 passaggi) il procedimento "look-and-say" (che Conway chiama decadimento audioattivo) finisce per produrre immancabilmente ed esclusivamente allineamenti di sequenze "atomiche" che non interagiscono più con le sequenze vicine, classificate in 92 "elementi comuni" e due "transuranici".

Ma c'è di più: Conway si occupa anche del tasso di crescita delle sue successioni, mostrando che il limite $$ \lim_{n\to\infty}\frac{L_{n+1}}{L_n} $$ del rapporto tra la lunghezza di due termini consecutivi è pari ad una costante algebrica $\lambda \cong 1.303577269$ di grado 71, di cui è in grado di fornire esplicitamente il polinomio minimo:

Weird, nevvero?

L'articolo originale di Conway, piuttosto stringato, fu pubblicato inizialmente su Eureka, magazine dell'Università di Cambridge, e non è di facile reperibilità in rete (anche se da qualche parte lo si trova...). Pare che la dimostrazione originale del Teorema Cosmologico sia andata persa, ma ne esistono di più recenti, ad esempio quella annunciata qui sull'ArXiv. A questo indirizzo è inoltre visionabile una lezione sul decadimento audioattivo.
Il decadimento audioattivo non è l'unica stramberia architettata da quel geniaccio di Conway. A lui si devono anche, in ordine sparso, il gioco della vita, l'algoritmo Doomsday, il FRACTRAN e i numeri surreali. E vale certamente la pena di dare un'occhiata al Book of Numbers, da lui scritto a quattro mani con un altro celebre matematico, Richard K. Guy.