Возвращаясь к ним-сложению: если взять d=2, то становится понятно, что это близкая история. А именно: d=2 означает, что мы последовательно (в словарном порядке) перечисляем варианты первых (n-1) букв — и пытаемся их дополнить последней буквой — наименьшей из тех, которая ещё не встречалась раньше для слов, отличающихся лишь в одной из первых (n-1) букв.

И если посмотреть — то это то же самое, как устроено перечисление проигрышных позиций при игре в ним (есть кучки камней, ход — взять любое ненулевое число камней из любой одной кучки, проигрывает тот, кто не может сделать ход, то есть перед кем взяли последний камень).

Собственно, сопоставив слову
003451
игру ним с кучками из 3, 4, 5 и 1 камня, мы увидим, что разрешённый ход это как раз уменьшение любой из координат, а условие, что ни одним разрешённым ходом нельзя попасть в слово кода (запрет на расстояние 1) как раз и значит, что из позиции нет хода в проигрышную — и потому она сама проигрышная.

А ход рассуждений с "наименьшим ещё не названным" для последнего символа соответствует доказательству теоремы Шпрага-Гранди — и принципу "наименьшего исключённого".

Да — мы тут потихоньку перешли от теории кодирования в область комбинаторной теории игр. (Где, кстати, книги Конвея "On Numbers and Games" и его же с Берлекампом и Ги "Winning Ways for your Mathematical Plays" — совершеннейшая классика.)

Ну и, наверное, до того, как переходить к этому рассказу, я показать несколько фотографий Рины Сергеевой с тех летних школ, на которых мы с Конвеем пересекались.

Вот тут — https://www.flickr.com/photos/lemezza/7958436406/in/album-72157631334930426/ — Конвей рассказывает про те самые лексикографические коды. В левой части доски как раз идёт выписывание слов, которые мы видели — а в правом верхнем углу доски можно даже разобрать "LEXICODE".

А вот тут — https://www.flickr.com/photos/lemezza/11280987216/in/album-72157638495119084/ —
Конвей в окружении участников. Собственно, это на всех школах было перманентное состояние Конвея: быть окружённым участниками, которым он что-то рассказывает, начиная с завтрака и зачастую заканчивая заполночь (и, конечно, включая завтраки, обеды и ужины!).

Вот тут — https://www.flickr.com/photos/lemezza/7902531034/in/album-72157631334930426/ — Конвей играет в футбол. Но не в обычный, а в придуманный им: см. https://en.wikipedia.org/wiki/Phutball

Гил Калаи вспоминает про эту игру (см. https://www.scottaaronson.com/blog/?p=4732#comment-1836693 ):
"<...>Conway set a special rule for me: Everytime I am convinced that I loose, we can switch sides. Needless to say that we switched sides several times; I was sure that my position is desperate beyond repair, we switched sides, and shortly afterward I was again sure that my position in the game is beyond repair.<...>"

А вот что пишет (см. https://terrytao.wordpress.com/2020/04/12/john-conway/ ) Теренс Тао:
"<...>I still remember being repeatedly obliterated in that game, which was a healthy and needed lesson in humility for me (and several of my fellow graduate students) at the time.<...>"

Ещё замечательное из той же записи Тао:
"I also recall Conway spending several weeks trying to construct a strange periscope-type device to try to help him visualize four-dimensional objects by giving his eyes vertical parallax in addition to the usual horizontal parallax, although he later told me that the only thing the device made him experience was a headache."

Вот тут — https://www.flickr.com/photos/lemezza/7924971264/in/album-72157631334930426/ — Конвей рассказывает про FRACTRAN — придуманный им "арифметический" язык программирования:
https://en.wikipedia.org/wiki/FRACTRAN .
Давайте я напишу об этом — благо, что это история короткая.

Программа на ФРАКТРАНе — это конечный упорядоченный набор дробей,
(p_1/q_1, p_2/q_2,..., p_k/q_k).
"Состояние компьютера" в каждый момент времени — это некоторое натуральное число A.

Правило перехода — на каждом такте мы идём по набору дробей слева направа, пытаясь найти такую дробь p_j/q_j, при умножении на которую состояние компьютера останется натуральным. Как только находим — объявляем это произведение
A':=A*p_j/q_j
новым состоянием компьютера.

Если ни на одну дробь из набора домножить так, чтобы остаться в натуральных числах, нельзя — программа останавливается.

Понятно, что при этом хорошо заменять числа на их разложения на простые множители — и, например, считать, что чтобы подать на вход программы пару (a,b), нужно взять начальное состояние A=2^a * 3^b, а про результат договориться, что им будет степень пятёрки после остановки.

Например, задача удвоения решается программой из одной дроби: (25/2), тогда из 2^a мы сделаем 5^{2a}.
Задача сложения — дробями (5/2,5/3): начав с
2^a * 3^b, мы получаем 5^{a+b}.

Хорошее упражнение — написать на этом языке "умножение", переводящее 2^a*3^b в 5^{ab}.
А программа, которую написал на доске Конвей, никогда не останавливалась — зато степени двойки, через которые она проходила, были в точности всеми числами вида 2^p, где p — простое.

из всех посвящений Конвею, у XKCD вышло самое поэтичное

На N+1 несколько дней назад вышел наш с Раскиным текст про Конвея —
https://nplus1.ru/material/2020/04/16/on-conway

А ещё коллеги напомнили про текст Конвея и Шипмана про разные доказательства иррациональности корня из 2 —

Вот такой есть текст Конвея и Шипмана про разные доказательства иррациональности корня из 2

И доказательства там обсуждаются действительно разные! Кроме стандартного доказательства с делимостью — вот такое доказательство с наложением квадратов:

Если квадрат со стороной p равен по площади двум квадратам со стороной q, то вот меньшая аналогичная конфигурация: два пустых квадрата со стороной (p-q) по площади равны закрытому дважды квадрату в центре со стороной q-(p-q)=(2q-p).