Математики доказали «превосходство» числа 73 над остальными числами

В 73-й серии сериала «Теория большого взрыва» Шелдон Купер заметил, что число 73 обладает тремя нетривиальными свойствами, которые делают его «самым замечательным числом». На тот момент это утверждение было голословным, поскольку математики не знали, является ли 73 единственным числом с перечисленными свойствами. Теперь же «превосходство» числа 73 доказали строго.

Переформулируем заявление Шелдона на математическом языке. Обозначим n-ое простое число как p(n). Определим «зеркальное» число m(x), которое получается перестановкой цифр числа x в десятичной записи. Например, m(922) = 229, m(6) = 6, m(1200) = 21. Тогда первое свойство запишется как m(p(n)) = p(m(n)). Теперь введем функцию П(x), которая возвращает произведение цифр числа x в десятичном представлении. Например, П(647) = 168, П(81) = 8, П(1024) = 0. В этих обозначениях второе свойство выглядит как П(p(n)) = n. Наконец, назовем число, которое обладает свойствами «зеркальности» и «произведения», числом Шелдона. Тогда «превосходство» числа 73 над всеми остальными числами означает, что 73 является единственным числом Шелдона.

Ищем контрпримеры к гипотезе Шелдона

К сожалению, на момент формулировки это утверждение было голословным: никто — кроме, возможно, самого Шелдона — не проверял, что других чисел с перечисленными свойствами не существует. Тем не менее, с помощью довольно простого анализа можно убедиться, что свойства зеркальности и произведения являются чрезвычайно ограничительными. Следовательно, если контрпримеры к гипотезе Шелдона и существуют, то они лежат далеко за пределами обозримого множества простых чисел, то есть искать их простым перебором будет сложно.

Сначала рассмотрим свойство «зеркальности», которое на самом деле разбивается на два утверждения. Во-первых, это свойство означает, что число m(p(n)) является простым. В принципе, чисел, которые удовлетворяют этому свойству, довольно много: среди первых десяти миллиардов простых чисел почти 15 процентов имеют «зеркального» собрата. В частности, в первом десятке таких чисел семь: это 2, 3, 5, 7, 11, 13, 17. Во-вторых, число m(p(n)) со свойством «зеркальности» также должно быть m(n)-ым по счету простым. Это ограничение гораздо жестче. Очевидно, ему удовлетворяют однозначные простые числа (2, 3, 5, 7), а также пара 37 и 73. Однако помимо этих тривиальных примеров среди первых десяти миллиардов простых чисел встречается только одно число со свойством «зеркальности» — это p(8114118) = 143787341. Интересно, что в этом случае и n, и p(n) являются палиндромами.

Свойство «произведения» ограничивает множество кандидатов на число Шелдона гораздо сильнее, чем свойство «зеркальности». Прежде всего, из него следует, что десятичная запись числа p(n) не содержит нуля. Если считать, что все десять цифр в записи числа встречаются с одинаковой вероятностью, то это ограничение оставит из простых чисел длиной n порядка 0,9ⁿ чисел. Чем больше n, тем меньше вероятность встретить число со свойством «произведения». Например, для n = 512 эта вероятность не превышает 4,6×10⁻²⁴. Впрочем, гипотеза о равномерном распределении цифр в записи простых чисел не доказана (и, вероятно, даже не верна), поэтому это соображение носит скорее качественный характер.

Тем не менее, с помощью свойства «произведения» все равно можно надежно исключить большое множество простых чисел. Заметим, что все простые делители числа П(x) ограничиваются множеством {2,3,5,7}, поскольку П(x) получается умножением десятичных цифр. Математики называют такое число 7-гладким. Следовательно, из анализа можно выбросить все простые числа, номер которых делится на простое число больше семи. Это заметно снижает множество возможных кандидатов на число Шелдона.

Это множество можно сузить еще сильнее, если воспользоваться ограничениями на функцию p(n). Из известной теоремы о распределении простых чисел, доказанной в 1896 году Жаком Адамаром, следует, что при больших n функция p(n) ≈ n•ln(n). Например, миллионное простое число примерно равно p(1000000) ≈ 1000000•ln(1000000) ≈ 13815510 (в действительности p(1000000) = 15485863). Более того, около двадцати лет назад были доказаны более строгие соотношения, которые не просто говорят об асимптотическом поведении p(n), но и строго ее ограничивают: n•ln(n) + n•ln(ln(n)) − n < p(n) < n•ln(n) + n•ln(ln(n)) для всех n ≥ 6. С помощью этого ограничения можно показать, что номер числа Шелдона не делится на сто: если это не так, то после зеркального отражения длина номера уменьшится на два (например, m(13700) = 731), а потому отвечающее ему простое число будет слишком коротким, чтобы длины чисел p(n) и p(m(n)) совпали (очевидно, простое число не может заканчиваться на ноль).

Таким образом, номер простого числа-кандидата на число Шелдона должен быть 7-гладким числом, которое не делится на сто. Оказывается, что это условие чрезвычайно ограничительно. Среди первого миллиарда простых чисел только 3039 чисел удовлетворяют обоим свойствам. Более того, после полноценной проверки свойства «произведения» из этих кандидатов остается только три числа: 17, 73 и 2475989 (7-ое, 21-ое и 181440-ое простое число соответственно). Очевидно, свойство «зеркальности» оставляет из них только 73.

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

Насколько нам известно, впервые гипотеза Шелдона привлекла внимание математического сообщества в 2015 году, когда математики Джесси Бирнс (Jessie Byrnes), Крис Спайсер (Chris Spicer) и Алисса Тёрнквист (Alyssa Turnquist) строго ее переформулировали и провели предварительный качественный анализ. Свою заметку ученые опубликовали в журнале Math Horizons, который предназначен для «студентов, заинтересованных математикой». Собственно, на момент написания заметки два ее соавтора (Бирнс и Тёрнквист) сами были студентами.

Доказываем гипотезу

В феврале этого года гипотеза Шелдона, наконец, была строго доказана: математики Крис Спайсер и Карл Померанс (Carl Pomerance) показали, что не существует чисел, которые одновременно обладают свойствами «зеркальности» и «произведения», кроме 73. Это доказательство полагается на следующие три утверждения.

Во-первых, математики показали, что простое число Шелдона не может превосходить 10⁴⁵. Для этого ученые воспользовались соотношением, доказанным в 1962 году Баркли Россером (Barkley Rosser) и Лоуэлом Шёнфельдом (Lowell Schoenfeld): функция π(x), подсчитывающая число простых чисел на отрезке [2; x], строго больше x/ln(x) для всех x ≥ 17. Предположим, что в десятичной записи n-ого простого числа p(n) содержится k цифр, причем первая цифра в точности равна a. Тогда из свойства «произведения» следует, что число n не может быть больше, чем a × 9^k − 1. В то же время, само число p(n) ≥ a × 10^k − 1. Следовательно, из теоремы Россера и Шёнфельда следует следующее соотношение:

a × 9^{k − 1} > a × 10^{k − 1}/ln(a × 10^{k − 1}) ⇒ ln(a) + (k − 1) ln(10) > (10/9)^{k − 1}.

Левая сторона этого неравенства растет по k линейно, а правая — экспоненциально. Следовательно, рано или поздно неравенство нарушится. Кроме того, если это неравенство нарушается для a = 9, то для других цифр оно также выполняться не будет. Путем несложного вычисления можно найти, что для всех k ≥ 46 оно не выполняется. Следовательно, простое число Шелдона не превосходит 10⁴⁵.

Во-вторых, немного усложнив анализ 2015 года, который мы уже упомянули в этом блоге, Спайсер и Померанс установили, что простое число Шелдона обладает следующими свойствами:

1. Его номер n является 7-гладким числом;
2. Первая цифра числа p(n) принимает значения из множества {1,3,7,9};
3. Число цифр числа с «зеркальным» номером p(m(n)) совпадает с числом цифр p(n);
4. n не делится на 625;
5. Если p(n) > 10¹⁹, то n не делится на 125;
6. n не делится на 100;
7. Десятичная запись числа p(n) не содержит нуля, а единица может стоять только в самом его начале;
8. Первая цифра p(m(n)) принимает значения из множества {3,7,9}.

Наконец, исследователи вывели ограничение на функцию p(n), которое позволяло быстро оценить первые несколько цифр кандидата на число Шелдона. Для этого ученые приблизили функцию π(x) обратным интегральным логарифмом li⁻¹(x) (интегральный логарифм исследователи определили как li(x) ≡ ∫₂^xdt/ln(t), а li⁻¹(li(x)) ≡ x). Если точнее, с помощью нескольких промежуточных лемм Спайсер и Померанс вывели следующее соотношение, которое выполняется для всех p(n) > 10¹⁹:

где функция E(x) = (5,5 × 10⁹ + 2,3 × 10⁻⁸li(x) + 10⁻¹¹x)∙ln(x).

Используя это соотношение, ученые проверили свойства числа Шелдона p(n) для всех возможных кандидатов в диапазоне 10¹⁹ < p(n) < 10⁴⁵. Среди этих простых чисел 1865251 имело 7-гладкий номер. После исключения номеров, которые делятся на 100 или 125, множество сузилось до 213449 кандидатов. Из них всего 112344 начинались на 1, 3, 7 или 9.

Затем исследователи использовали выведенное ограничение на функцию p(n) и нашли первые пять цифр числа p(n). Перемножая эти числа и умножая их на нужную степень девяти, ученые получили ограничение сверху на произведение П(n) и отбросили всех кандидатов, для которых этот ограничение не дотягивало до n. Подобный отбор пережило 991 число, тогда как для 168 чисел однозначно восстановить первые пять цифр вообще не удалось. После этого ученые повторили подобный анализ, оценивая первые шесть чисел числа. В результате среди всех кандидатов осталось всего 141 число, которое прошло обе проверки, 168 чисел, которые не удалось исключить на первом этапе, и 29 чисел, которые не удалось исключить на втором этапе.

Для оставшихся 338 кандидатов ученые нашли p(m(n)) и проверили, что число его цифр совпадает с p(n), а первая цифра принадлежит множеству {3,7,9}. Это сузило область поисков до 45 кандидатов. Все они были достаточно малы, чтобы можно было однозначно восстановить первые пять цифр числа p(m(n)). Придерживаясь той же стратегии, что и для чисел p(n), ученые показали, что произведение П(m(n)) не дотягивает до n (очевидно, П(m(n)) = П(n)).

В диапазоне p(n) < 10¹⁹ исследователи придерживались той же стратегии. Впрочем, из-за недостаточной жесткости ограничений на разницу p(n) и li⁻¹(n) в этом диапазоне пять простых чисел пережило все проверки. Это числа 97496326163, 97841660857, 99024780191, 316109730941 и 785009387557. Впрочем, десятичная запись четырех последних чисел содержит ноль, а первого — единицу на нелидирующей позиции, поэтому эти числа не обладают необходимыми свойствами. Следовательно, число 73 действительно является единственным числом Шелдона.

Более подробное доказательство гипотезы Шелдона можно найти в препринте, подготовленном Спайсером и Померансом.

***

Внимательный читатель мог заметить, что Шелдон упоминал о еще одном свойстве числа 73: двоичная запись этого числа является палиндромом. Теперь очевидно, что это замечание служило скорее «вишенкой на торте», то есть не было необходимым для доказательства «превосходства» 73 над остальными числами. Тем не менее, оно также указывает на возможные обобщения гипотезы Шелдона на другие системы записи чисел. Если бы человечество пользовалось другой системой, сколько бы в ней существовало чисел Шелдона? И существовали бы вообще? Пока что математики не пытались ответить на этот вопрос.