Примерно полвека назад аспирант-математик Нил Слоун, изучая поведение нейросетей, натолкнулся на незнакомую последовательность чисел и решил выяснить, что о ней писали другие математики. Нигде больше эта последовательность ему не встретилась, зато попутно он нашел много других интересных последовательностей и превратился в страстного коллекционера и создателя путеводителя по миру последовательностей целых чисел. Рассказываем об обитателях этого мира и историях, с ними связанных. Да, и не включайте музыку сразу на полную громкость при других людях — не все оценят красоту звучания чистой математики.
Нейросети, перфокарты, кубометры писем
Молодой математик и инженер Нил Джеймс Александр Слоун начал работу над диссертацией по модной, относительно новой тематике — нейронным сетям. На дворе были не 2010-е, как можно было бы подумать, а 1964 год.
Впереди еще десятки лет развития теории построения искусственных нейросетей и необходимого для их нынешнего расцвета развития компьютерной техники, пока же в этой области есть только самые базовые идеи о моделирование нейронов и их соединений, а работа Слоуна имеет еще более абстрактную направленность: моделью нейросети в ней выступает граф-дерево с выделенной «корневой» вершиной: вершины представляют нейроны, которые передают сигнал в корневой нейрон.
Помимо прочего, Слоун вычислил среднее количество шагов, которое должен пройти сигнал в сети, просуммированное по всем возможным формам сети из 1, 2, 3... нейронов. Получились несколько начальных членов некоей последовательности чисел: (0, 1, 8, 78, 944, 13800, 237432, ...). Слоун захотел узнать, какие сведения о свойствах этой последовательности есть в научной литературе, и стал штудировать научные журналы и книги, заодно выписывая и другие последовательности целых чисел, попадавшиеся ему. Так он нашел главное дело своей жизни.
Уже через год-два слух о парне, который коллекционирует последовательности, разошелся по сообществу математиков, и Слоун стал получать письма с новыми экземплярами для своей коллекции. Эти письма потом были отсканированы и опубликованы.
Он так и не встретил тогда ту последовательность, с которой все началось, но в 1967 году успешно защитил диссертацию и вскоре поступил на работу в Лаборатории Белла, став успешным исследователем в области теории кодирования (он сотрудничал и дружил, например, с Джоном Конвеем).
Коллекция перекочевала из блокнотов на перфокарты, затем на магнитную пленку и в конечном итоге превратилась в 200-страничный «Справочник целочисленных последовательностей», вышедший в 1973 году. Книга, в которой было 2372 последовательности, стала очень популярна, а ее автора завалили корреспонденцией: в кабинете Слоуна до сих пор упираются в потолок папки с присланными в те годы статьями и письмами.
В 1995 году коллекция превратилась в «Энциклопедию целочисленных последовательностей», в которой было уже почти пять с половиной тысяч экземпляров, причем это были уже не только «обычные» бесконечные последовательности, но и конечные, а также и бесконечные прямоугольные и треугольные таблицы чисел, такие как треугольник Паскаля.
На следующий год Слоун открыл сайт — Онлайн-энциклопедию целочисленных последовательностей, OEIS. А в 2009 году он занялся превращением OEIS из своего личного проекта в технически и юридически самостоятельную сущность: для управления Онлайн-энциклопедией был создан фонд, а сам сайт превратили в краудсорсинговый проект, подобный Википедии. Слоун занимал пост президента фонда до конца июня 2021 года, когда его сменил Расс Кокс, программист из компании Google, который в 2007 году написал для OEIS поисковую систему — как по членам последовательностей, так и по тексту записей, — а в 2010-м и весь софт, необходимый для ее работы.
Сегодня Онлайн-энциклопедия редактируется пользователями без обязательного непосредственного участия Слоуна (но с премодерацией выбранными Слоуном редакторами-волонтерами) и доступна по адресу oeis.org. В ней уже больше трети миллиона записей. Но что скрывается в этом гигантском скопище чисел, что там могут найти математики (и обычные люди)?
Соединить концы с концами
Ничего особо необычного в увлечении Слоуна не было. Некоторые коллекционируют крышки от пивных бутылок (и находят единомышленников), а вот он — собирает числа. Азарт коллекционера наверняка играет немаловажную роль и для Слоуна, и для многих из тех, кто присылал и присылает ему новые последовательности. Всегда приятно пополнить коллекцию таким изящным экземпляром, как, например, последовательность Морса—Туэ, в которой «прячется» фрактал.
Но в ней можно найти слова и явления из обычной, нематематической реальности. Так, по запросу «bamboo» — «бамбук» — вы найдете последовательность чисел, в разложении которых на простые множители встречаются только 2, 3 и 5, потому что именно таковы циклы цветения разных видов бамбука (самый длинный из известных составляет ровно 120 лет), и этому, как ни удивительно, есть эволюционное объяснение.
Пушечные ядра обычно складывают пирамидкой, и по запросу «pyramid» Энциклопедия находит несколько последовательностей, например, чтобы сложить пирамиду с квадратным основанием высотой 1, 2, 3, 4... слоя, ядер нужно 1, 5, 14, 30, 55... В Энциклопедии есть даже шведская застольная песня, которая полностью состоит из чисел.
Но, конечно, гораздо чаще в энциклопедии ищут не слова, а числа. Каждая последовательность, которая есть в ней, может быть представителем той или иной задачи — к примеру, задача о расстановке n ферзей на доске n × n может быть представлена последовательностью, содержащей количество решений задачи для разных n.
Скажем, математик работает над задачей, в которой какая-то последовательность возникает естественным путем (как число решений в задаче о расстановке ферзей). И в этом случае запись о ней в картотеке становится «точкой входа» в корпус литературы, посвященной не только и не столько самой последовательности, сколько задачам, связанным с ней.
Поэтому если в математической статье рассматривается, к примеру, подсчет танграмов и других полиформ из квадратов и треугольников, то непременно даются ссылки на соответствующие записи из OEIS.
«Справочник» Слоуна заслужил популярность благодаря своей организации: в нем было настолько удобно найти последовательность по нескольким первым членам, насколько это вообще возможно в бумажной книге, задолго до эпохи онлайн-поисковиков, после чего можно было проследовать по ссылке на источник и отыскать таким образом информацию о своей задаче.
Особенно полезным бывает такой поиск, когда последовательность связана с на первый взгляд разными, не связанными между собой задачами из разных областей математики (или хотя бы из разных углов комбинаторики и теории чисел — областей, которые чаще всего имеют дело с целочисленными последовательностями). Ведь самые интересные и амбициозные проекты в современной математике (такие как программа Ленглендса) связаны именно с выявлением неожиданных, неочевидных связей.
Последовательности действительно помогают в этом: если вы обратили внимание на то, что в двух упомянутых нами в самом начале этой статьи последовательностях есть два очень близких числа — 196883 и 196884, — то вы вслед за британским математиком Джоном Маккеем сделали первый шаг к комплексу фактов и гипотез под названием monstrous moonshine, иногда называемому по-русски в популярных источниках «гипотезой чудовищного вздора».
Пояснить ее суть мы можем лишь в общих чертах: это связь между объектами, о которых до Маккея никто не мог подумать, что они связаны: монстром — крупнейшей из спорадических простых групп (о них мы немного рассказывали в тексте о Джоне Конвее) — и j-инвариантом — функцией, которую можно охарактеризовать как простейшую из подчиняющихся уравнению j(τ) = j(τ+1) = j(−1/τ) для всех τ. Идеи из monstrous moonshine потом оказались полезны в теоретической физике при обсуждении квантовой гравитации (мы описывали эту кухню в материале про сложный мем).
В том числе поэтому охват энциклопедии последовательностей, собранной Слоуном, весьма широк: четко очертив тип содержания — последовательности целых чисел и только они, — он собирает последовательности и из чистой математики, и из других наук, и из загадок. Иногда говорят, что подойдет любая последовательность, которая заинтересует кого-то, кроме ее автора. Поэтому безоговорочно принимаются последовательности, опубликованные в научной литературе, но не допускаются последовательности с надуманными, неестественными определениями.
Музыка чисел
Числовые последовательности можно превращать в музыку. Для этого каждому целому числу сопоставляют ноты с шагом в один полутон. В интересных последовательностях часто встречаются регулярные структуры, которые и звучат тоже любопытно. Вот несколько примеров.
- n-й член последовательности, названной «Парафраза Кимберлинга» (Кларк Кимберлинг — профессор Университета Эвансвилла), получается из числа n делением его пополам до тех пор, пока оно делится нацело, и после этого еще раз с округлением вверх (иначе бы получилась последовательность сплошь из нечетных чисел). Послушайте, что получается.
- Последовательность Рекамана (как и выше, это редкий случай, когда последовательность названа в честь автора: Бернардо Рекаман — колумбийский педагог-математик) строится так: начиная с числа 0, делаем шаг длиной 1, затем 2, затем 3… по числовой прямой — влево, если это возможно без попадания в отрицательное числа или в уже встречавшееся число, иначе вправо. Это красиво выглядит и красиво звучит.
- «Закрученная нумерация» натуральных чисел придумана известным ученым и любителем математических загадок Дональдом Кнутом. Она основана на системе счисления с основанием 5: у двух соседних чисел в этой последовательности любая пара пятеричных цифр должна либо совпадать, либо немного отличаться по строго определенным правилам. Звучит это так.
Непрошеные подсказки
В реальной научной работе в области комбинаторики и теории чисел OEIS обычно помогает установить связь с существующими работами и иногда предположить явную формулу для той или иной последовательности, возникшей в работе.
Иногда целое математическое исследование возникает благодаря энциклопедии. Так, запрос в OEIS послужил отправной точкой для работы о связи песчаных куч и замощений доминошками.
Специалист по комбинаторике Сергей Китаев с коллегами обнаружил связь между интервальными порядками и определенными перестановками именно благодаря OEIS, что тоже выросло в научную статью и затем в целую небольшую область в комбинаторике интервальных порядков. Интервальный порядок — способ взаимного расположения интервалов (отрезков) на прямой, которые могут обозначать, к примеру, временны́е рамки нескольких длящихся событий: к примеру, два события могут пересекаться по времени, и тогда невозможно успеть посетить сразу оба, а могут следовать одно за другим (возможно, с перерывом) — значит, для 2 интервалов существует два возможных интервальных порядка, так что 2-й член соответствующей последовательности равен двум.
Бывает и так, что сама идея математической работы рождается благодаря коллекции последовательностей. Филипп Дюшон (Philippe Duchon) и Ромарик Дювиньо (Romaric Duvignau) из лаборатории компьютерных исследований в Бордо работали над алгоритмом — сейчас они сами не помнят, в чем именно была точная задача этого алгоритма, но для его работы ученым потребовался набор чисел — вероятностей с определенными свойствами. Они вывели формулы, дававшие нужные числа, но не смогли с ходу доказать, что числа всегда будут получаться неотрицательными, как полагается значениям вероятности. Эти числа составляли не последовательность, а треугольную таблицу, и были не целыми, а рациональными.
Но Дюшон был знаком с Энциклопедией целочисленных последовательностей еще с тех пор, когда она представляла собой бумажную книгу, и знал, как искать в ней рациональные числа, то есть дроби с целым числителем и знаменателем: можно, в частности, привести дроби в каждом ряду треугольной таблицы к общему знаменателю, после чего поискать в OEIS последовательность числителей.
Сделав это в надежде узнать что-то полезное для своей задачи, Дюшон и Дювиньо неожиданно обнаружили, что их числа совпадают с так называемыми числами встреч: число встреч dnk — это количество способов переставить n предметов, оставив на месте ровно k из них, к примеру, d3^1 = 3, потому что если ровно один из трех предметов остается на месте (его мы можем выбрать тремя способами), то два других уже обязательно нужно поменять местами.
В результате разрабатываемый Дюшоном и Дювиньо алгоритм получил новую интерпретацию, и его удалось применить для эффективной генерации случайных перестановок — задачи, которую решает ваш плеер всякий раз, как вы нажимаете кнопку «перемешать».
Наконец, Онлайн-энциклопедия нередко пригождается любителям математических загадок. Так что если вам предложат продолжить последовательность (1, 3, 6, 10, 15, 21, 28, ...) — вы знаете, где искать подсказку.
Андрей Заболотский