Автостопом к ответу жизни, Вселенной и всего такого

10 октября 2020 года исполнилось 10 лет с первого «Дня 42», потому что 101010₂ = 42. Сегодня делимся переводом поста об этом удивительном числе. Автор — профессор компьютерных наук Лилльского университета управления Жан Поль Делахайе, также написавший книгу «Formal methods in artificial intelligence», которая вышла еще в 1987 году. Он рассказывает о некоторых аллюзиях на 42, об этом числе в математических последовательностях и, конечно, о 42 в контексте задачи о сумме трех кубов. Подробности под катом.

---

Все любят неразгаданные тайны. Примером может быть исчезновение Амелии Эрхарт над Тихим океаном в 1937 году и дерзкий побег заключенных Фрэнка Морриса, Джона и Кларенса Энглинов с острова Алькатрас в Калифорнии в 1962 году. Более того, наш интерес сохраняется, даже когда тайна основана на шутке. Возьмем популярный научно-фантастический роман Дугласа Адамса 1979 года «Автостопом по галактике» — первый из пяти в серии. В конце книги суперкомпьютер «Deep Though» отвечает на вопрос «Жизни, Вселенной и всего такого» просто: 42.

«Deep Though» нужно было 7,5 миллионов лет для вычисления ответа на вопрос. Герои, которым было поручено получить ответ, разочарованы. Ответ не очень полезен. Но, как указывает компьютер, вопрос сформулирован расплывчато. Чтобы найти правильную формулировку вопроса, ответом на который будет 42, компьютер должен построить новую версию самого себя. Это тоже займет время. Новая версия компьютера — Земля. Чтобы узнать, что будет дальше, придется прочитать книги Адамса.

Выбор автором числа 42 закрепился в культуре гиков. 42 стоит у истоков множества шуток и подмигиваний, которыми обмениваются посвященные. Если, например, вы введете в поисковой системе вариации вопроса «What is the answer to everything?», то, скорее всего, ответом будет 42. Попробуйте на французском или немецком языке. Вы часто будете получать один и тот же ответ, используете ли вы Google, Qwant, Wolfram Alpha (который специализируется на расчетах математических задач) или чат-бот веб-приложения Cleverbot.

С момента создания первой школы «Сети 42» во Франции в 2013 году увеличилось количество частных учреждений, обучающих работе с компьютером. Название — четкая аллюзия на романы Адамса. Сегодня компания-основатель насчитывает более 15 кампусов в своей глобальной сети. Число 42 появляется в фильме «Человек-паук: через Вселенные». Многие другие ссылки и аллюзии на 42 можно найти, например, в статье Википедии. Число 42 также появляется в целой цепочке любопытных совпадений, значение которых, вероятно, не стоит пытаться выяснить. Например:

• В древнеегипетской мифологии во время суда над душами умершие должны были объявить перед 42 судьями, что они не совершили ни одного из 42 грехов.
• Марафонская дистанция в 42,195 километра связана с легендой о том, как далеко древнегреческий воин Фидиппид пробежал между Марафоном и Афинами, чтобы объявить победу над персами в 490 году до нашей эры. Понятия километра в то время еще не было, что делает это совпадение еще более поразительным.
• В Древнем Тибете правили 42 правителя. Царствовавшая около 127 года до нашей эры Ньятри Ценпо была первой. Лангдарма, который правил с 836 по 842 год, то есть 42-й год девятого века, был последним.
• Библия Гутенберга, первая книга, напечатанная в Европе, состоит из 42 строк текста на колонку и также называется «сорокадвухстрочная Библия».

Согласно сообщению блога Economist от 6 марта, посвященному 42 годовщине предшествующей роману радиопередачи Автостопом по Галактике, "редко отмечается 42 годовщина чего-либо".

Совершенно произвольный выбор

Очевидный (и безусловно заданный) вопрос в том, имело ли использование 42 в книгах Адамса какое-то особое значение для автора. Его ответ, выложенный в дискуссионной группе alt.fan.douglas-adams, был кратким:

Это была шутка. Это должно было быть число, обычное, небольшое число, и я выбрал его. Двоичные представления, основание тринадцать, тибетские монахи — все это полная ерунда. Я сидел за своим столом, смотрел в сад и думал: «42 подойдет». И написал его. Конец истории.

В двоичной системе 42 записывается как 101010. Это довольно просто и, кстати, это побудило нескольких фанатов провести вечеринки 10 октября 2010 года (10/10/10). Ссылка на основание 13 в ответе Адамса требует более подробного объяснения. Однажды в серии книг делается предположение, что 42 — это ответ на вопрос «Что вы получите, умножив шесть на девять?». Идея кажется абсурдной, потому что 6 x 9 = 54. Но при основании 13 число, выраженное как «42», равно (4 x 13) + 2 = 54.

Помимо намеков на 42, намеренно привнесенных специалистами компьютерных наук для развлечения, а также кроме неизбежных встреч с числом, когда вы немного покопаетесь в истории и в мире, можно задаться вопросом, есть ли что-то особенное в этом числе со строго математической точки зрения.

42 математически уникально?

Число 42 обладает рядом интересных математических свойств. Вот некоторые из них:

Это число — сумма первых трех нечетных степеней двойки, то есть 2¹ + 2³ + 2⁵ = 42. Это элемент в последовательности a_n сумм n нечетных степеней 2 для n > 0. Последовательность соответствует записи A020988 в онлайн-энциклопедии целочисленных последовательностей (OEIS), созданной математиком Нилом Слоуном. В двоичной системе элемент n может быть задан путем повторения 10 n раз (1010… 10). Формула для этой последовательности: a_n = (2/3)(4ⁿ – 1). При увеличении числа n плотность чисел стремится к нулю. Это означает, что числа, входящие в этот список, включая 42, исключительно редки.

Число 42 — это сумма первых двух ненулевых целых степеней шести, то есть 6¹ + 6² = 42. Последовательность b_n, представляющая собой сумму степеней шести, соответствует записи A105281 в OEIS. Она определяется формулами b₀ = 0, b_n = 6b_{n — 1} + 6. Плотность этих чисел также стремится к нулю.

Сорок два — каталонское число. Эти числа также чрезвычайно редки. Гораздо более редки, чем простые числа: только 14 из них меньше одного миллиона. Каталонские числа были впервые упомянуты под другим названием швейцарским математиком Леонардом Эйлером. Эйлер хотел знать, сколькими различными способами можно разрезать на треугольники N-сторонний выпуклый многоугольник, соединяя вершины с отрезками линий. Начало последовательности (A000108 в OEIS) 1, 1, 2, 5, 14, 42, 132… Элемент n определяется по формуле c(n) = (2n)! / (n!(n + 1)!). И, как и в случае с двумя предыдущими последовательностями, плотность таких чисел стремиться к нулю.

Каталонские числа названы в честь франко-бельгийского математика Эжена Шарля Каталана (1814-1894), который обнаружил, что c_n — это число способов расположить n пар скобок в соответствии с обычными правилами их написания. Скобка никогда не закрывается до того, как она была открыта. Скобку можно закрыть только тогда, когда все скобки, которые были открыты после нее, сами закрыты. Например, c₃ = 5, поскольку возможные расположения трех пар скобок таковы:

( ( ( ) ) )
( ) ( ) ( )
( ( ) ) ( )
( ( ) ( ) )
( ) ( ( ) )

Сорок два — «практичное» число. Это означает, что любое целое число между 1 и 42 можно представить как сумму его различных делителей. Первые практические числа таковы: 1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, 56, 60, 64, 66, 72. (последовательность A005153 в OEIS). Ни одна простая известная формула не дает элемент N этой последовательности.

Все это забавно, но было бы неправильно сказать, что 42 — это действительно нечто особенное математически. Числа 41 и 43, например, также являются элементами многих последовательностей. Вы можете исследовать свойства различных чисел в Википедии.

Что делает число особенно интересным или неинтересным, это вопрос, который мы с математиком и психологом Николасом Гавритом, вычислительным естествоиспытателем Гектором Зенилом изучили, начав с анализа последовательностей в OEIS. Помимо теоретической связи со сложностью Колмогорова (определяющей сложность числа по длине его минимального описания), мы показали, что числа, содержащиеся в энциклопедии Слоуна, указывают на общую математическую культуру и, следовательно, что OEIS основана не только на человеческих предпочтениях, но и на чистой математической объективности.

Задача о сумме трех кубов

Ученые области компьютерных наук и математики признают привлекательность числа 42. Но всегда думали, что это игра, в которую можно играть так же хорошо с другим числом. Тем не менее, недавняя новость привлекла их внимание. Представить 42 в виде суммы трех кубов было сложнее, чем все остальные числа меньше 100.

Задача формулируется так: какие целые числа n можно записать как сумму трех кубов целых чисел n = a³ + b³ + c³? И для таких целых чисел, как найти a, b, c? на практике трудность вычисления в том, что для данного n пространство рассматриваемых триплетов включает отрицательные целые числа. Таким образом, это триплетное пространство имеет неограниченное число вариантов, в отличие от суммы квадратов. Для этой конкретной задачи любое решение имеет абсолютное значение, меньшее, чем квадратный корень из заданного n. Более того, для суммы квадратов мы прекрасно знаем, что возможно, а что невозможно.

Для суммы кубов некоторые решения могут быть удивительно большими, например, решение для 156, открытое в 2007 году:

156 = 26,577,110,807,569³ + (−18,161,093,358,005)³ + (−23,381,515,025,762)³

Заметим, что для некоторых целых значений n уравнение n = a³ + b³ + c³ не имеет решения. Так обстоит дело со всеми целыми числами n, которые выражаются как 9m + 4 или 9m + 5 для любого целого числа m (например, 4, 5, 13, 14, 22, 23). Демонстрация этого утверждения проста: мы используем вычисление «по модулю 9» (mod 9), которое эквивалентно предположению, что 9 = 0, а затем манипулируем только числами между 0 и 8 или между -4 и 4. Когда мы делаем это, то видим, что:

0³ = 0 (mod 9)
1³ = 1 (mod 9)
2³ = 8 = –1 (mod 9)
3³ = 27 = 0 (mod 9)
4³ = 64 = 1 (mod 9)
5³ = (–4)³ = –64 = –1 (mod 9)
6³ = (–3)³ = 0 (mod 9)
7³ = (–2)³ = 1 (mod 9)
8³ = (–1)³ = –1 (mod 9)

Другими словами, куб целого числа по модулю 9 равен -1 (= 8), 0 или 1. Сложение любых трех чисел между этими числами дает:

0 = 0 + 0 + 0 = 0 + 1 + (–1)
1 = 1 + 0 + 0 = 1 + 1 + (–1)
2 = 1 + 1 + 0
3 = 1 + 1 + 1
6 = –3 = (–1) + (–1) + (–1)
7 = –2 = (–1) + (–1) + 0
8 = –1 = (–1) + 0 + 0 = 1 + (–1) + (–1)

Вы не можете получить сумму 4 или 5 (= -4). Это ограничение означает, что суммы трех кубов никогда не являются числами вида 9m + 4 или 9m + 5. Таким образом, мы говорим, что n = 9m + 4 и n = 9m + 5 — это запрещенные значения.

Поиск решений

Чтобы проиллюстрировать, насколько трудно найти решение уравнения n = a3 + b3 + c3, давайте посмотрим, что происходит при n = 1 и n = 2. Для n = 1 решение очевидно: 1³ + 1³ + (–1)³ = 1. Есть ли другие? Да, есть: 9³ + (–6)³ + (–8)³ = 1. Этот расчет — не единственное другое решение. В 1936 году немецкий математик Курт Малер предложил бесконечное их число. Для любого целого p:

(9p⁴)³ + (3p – 9p⁴)³ + (1 – 9p³)³ = 1

Это может быть доказано с помощью тождества куба суммы. Бесконечное множество решений также известно для n = 2. Оно открыто в 1908 году математиком А. С. Веребрусовым. Для любого целого p:

(6p³ + 1)³ + (1 – 6p³)³ + (–6p²)³ = 2

Умножив каждый член этих уравнений на куб целого числа r³, мы приходим к выводу, что существует также бесконечно много решений как для куба, так и для двойного куба любого целого числа. Рассмотрим пример 16, то есть (2³)*2. При p = 1 получаем: 143 + (–10)³ + (–12)³ = 16. Обратите внимание, что для n = 3 по состоянию на август 2019 года было известно только два решения: 1³ + 1³ + 1³ = 3; 4³ + 4³ + (–5)³ = 3. Естественно, возникает вопрос: существует ли хотя бы одно решение для каждого незапрещенного значения?

Компьютеры в решении задачи

Чтобы ответить на этот вопрос, математики начали с того, что взяли незапрещенные значения 1, 2, 3, 6, 7, 8, 9, 10, 11, 12, 15, 16… (A060464 в OEIS) и рассматривая их один за другим. Если решения могут быть найдены для всех рассмотренных значений, то будет разумно предположить, что для любого целого числа n, которое не имеет вида n = 9m + 4 или n = 9m + 5, существуют решения уравнения n = a3 + b3 + c3.

Проведенные до сих пор исследования, которые зависят от мощности используемых компьютеров или компьютерных сетей, дают все более широкие результаты. Эта работа возвращает нас к знаменитому и интригующему числу 42.

В 2009 году, используя метод, предложенный Ноамом Элкисом из Гарвардского университета (или американским математиком Ноамом Элкисом в 2000 году), немецкие математики Андреас-Стефан Эльзенханс и Йорг Янель исследовали все триплеты a, b, c целых чисел с абсолютным значением меньше 1014, чтобы найти решения для n между 1 и 1000. В документе делается вывод о том, что вопрос о существовании решения для чисел меньше 1000 открыт только для 33, 42, 74, 114, 165, 390, 579, 627, 633, 732, 795, 906, 921 и 975. Для целых чисел меньше 100 оставалось только три загадки: 33, 42 и 74.

В препринте 2016 года Сандер Хюисман, ныне работающий в Университете Твенте в Нидерландах, нашел решение для 74:

(–284,650,292,555,885)³ + (66,229,832,190,556)³ + (283,450,105,697,727)³

В 2019 году Эндрю Букер из Бристольского университета в Англии решил проблему с 33:

8,866,128,975,287,528)³ + (–8,778,405,442,862,239)³ + (–2,736,111,468,807,040)³

С этого момента число Дугласа Адамса было последним положительным целым числом меньше 100, представление которого в виде суммы трех целых кубов было неизвестно. Если бы решения не было, то этот вывод дал бы действительно убедительное обоснование математической значимости 42. Это было бы первое число, для которого решение казалось возможным, но не было найдено.

Ответ пришел в препринте 2020 года. Это результат огромных вычислительных усилий, координируемых Букером и Эндрю Сазерлендом из Массачусетского технологического института. Компьютеры, участвующие в благотворительной сети персональных компьютеров, работали более одного миллиона часов и вычислили, что:

42 = (–80,538,738,812,075,974)³ + 80,435,758,145,817,515³ + 12,602,123,297,335,631³

Недавно были также раскрыты дела 165, 795 и 906. Задачу для чисел меньше 1000 — 114, 390, 579, 627, 633, 732, 921 и 975 еще предстоит решить.

Гипотеза о том, что решения существуют для всех целых чисел n, кроме чисел вида 9m + 4 или 9m + 5, по-видимому, подтверждается. В 1992 году Роджер хит-Браун из Оксфордского университета выдвинул предположение, что существует бесконечно много способов выразить все возможные N в виде суммы трех кубов. Работа еще далека от завершения.

Эта трудность кажется настолько пугающей, что вопрос «является ли N суммой трех кубов?» может оказаться неразрешимым. Другими словами, ни один алгоритм, каким бы умным он ни был, не сможет обработать все возможные случаи. Например, в 1936 году Алан Тьюринг показал, что ни один алгоритм не решит проблему остановки для каждой возможной компьютерной программы. Но здесь мы находимся в чисто математической области, которую легко описать. Если бы мы могли доказать такую неразрешимость, это было бы чем-то новым. Число 42 было сложным, но это не последний шаг!

Уважаемые читатели, искренне надеемся, вам понравился наш выбор материала. А на наших курсах, можно научиться правильно формировать запросы и работать с ИИ так, чтобы на выдачу решения не требовалось 7 миллионов лет.

• Обучение профессии Data Science с нуля
• Онлайн-буткемп по Data Science
• Обучение профессии Data Analyst с нуля
• Онлайн-буткемп по Data Analytics

Читать еще

• Данные внутри нас: Чем занимаются биоинформатики?
• Machine Learning и Computer Vision в добывающей промышленности

Автор: Skillfactory School

Источник