Как Гомер Симпсон почти решил уравнение Великой теоремы Ферма

Александр Клименков

кандидат технических наук, Tech Lead Bercut

Казалось бы, что может быть общего между одной из самых популярных математических теорем, Гомером Симпсоном и Дональдом Кнутом? Как и многие другие интересные идеи и задачи, их объединяет математика. Иногда даже кажется, что почти всё в этом мире сводится к математике и программированию.

Задача, о которой я хочу рассказать, совсем не сложная. Думаю, её без труда сможет решить даже начинающий программист. Но эта задача интересна и весьма необычна. Согласитесь, ведь не каждый день предоставляется возможность проверить вычисления героя культового мультсериала Гомера Симпсона?

Что это за теорема?

Большинство читателей Tproger, конечно же, неоднократно слышали о Великой теореме Ферма. О ней написано множество научных статей, она упоминается в книгах, рассказах, фильмах и мультсериалах. Не удивлюсь, если ей даже посвящена какая-нибудь басня.

Для тех, кто подзабыл, что это за теорема, приведу краткий экскурс в историю:

1. В третьем веке до нашей эры Диофант Александрийский пишет труд по арифметике, в котором предлагает читателям найти решение уравнения x2 +y2 = z2 в целых числах.
2. В 1637 году Пьер Ферма изучает книгу Диофанта Александрийского. Ферма без труда понимает, что у предложенного уравнения бесконечное количество решений и предлагает гораздо более интересную задачу: найти целочисленные решения для уравнения x3+ y3 = z3. Эта задача оказалась уже не такой простой, как предыдущая. Ферма смог найти только тривиальные решения, вроде 03 + 73 = 73. Это, конечно, математически верно, но совершенно неинтересно. В итоге Ферма решает, что для целых степеней p > 2 уравнение xp + yp = zp не имеет целочисленных решений. Это и есть та самая Великая теорема Ферма. Причём это была не просто гипотеза: Ферма удалось строго математически доказать это утверждение (не будем тут останавливаться на версии, что Ферма просто пошутил). Однако он не стал записывать доказательство, вместо этого он написал на полях книги Диофанта такую фразу: «Я нашёл этому поистине чудесное доказательство, но поля книги слишком узки для него». Кстати, вам это не напоминает некоторые технические задания: «Тут и так всё ясно — нечего и записывать»?
3. С 1637 года до нашего времени математики пытались доказать Великую теорему Ферма. Некоторым удалось найти доказательство для отдельных малых степеней (3, 5, 7 и некоторых других). Но доказать теорему полностью не удавалось никому.
4. В 1995 году математик Эндрю Уайлс из Принстонского университета наконец опубликовал полное доказательство теоремы. Текст доказательства занимает 130 страниц математических формул. Хотя теорема и доказана, многие математики сомневаются, что сам Ферма имел в виду именно такое громоздкое доказательство. Кроме того, Уайлс использовал множество современных математических методов, которые ещё не существовали во времена Ферма.

При чём здесь Гомер Симпсон?

В 1998 году на экраны вышла очередная серия десятого сезона «Симпсонов» — «Волшебник вечнозелёной аллеи». В ней Гомер Симпсон соревнуется в изобретательском таланте с самим Томасом Эдисоном. Как и у каждого заправского изобретателя у Гомера есть грифельная доска, на которой он пишет разные формулы и рисует чертежи будущих изобретений. В течение нескольких секунд мы видим в кадре эту доску, на которой написано равенство: 378712 + 436512 = 447212. Там есть другие надписи и рисунки, но нас сейчас интересует именно эта запись. Выглядит так, будто Гомер написал решение уравнения Великой теоремы Ферма. Но к этому мы ещё вернёмся.

Доска изобретателя Гомера — это одна из многочисленных математических шуток в «Симпсонах». В сериале они появляются постоянно: в виде особенных чисел, формул, чертежей, фраз героев, кодов и шифров. Некоторые из них видны в кадре всего на мгновение, но внимательные зрители их находят и стараются разгадать.

В таком обилии математических отсылок и аллюзий в сериале нет ничего удивительного: многие сценаристы «Симпсонов» имеют математическое образование. Например, один из сценаристов серии «Волшебник вечнозелёной аллеи» Дэвид Коэн — это математик и программист, который в какой-то момент увлёкся написанием весёлых историй для популярного сериала. Интересно, что в школе Дэвид был типичным «гиком», организатором группы программистов Glitchmaster («Мастера глюков»), которая занималась программированием. Например, они разработали собственный язык программирования FLEET для разработки ускоренной графики на компьютере Apple II Plus. Затем он одновременно закончил Гарвард (получив степень бакалавра по физике) и Беркли (получив степень магистра по компьютерным наукам).

Нет ничего удивительного, что в сериале, написанном программистами, физиками и математиками, периодически появляются математические шутки и загадки. Этой теме посвящена очень интересная книга «Симпсоны и их математические секреты», написанная Саймоном Сингхом в 2016 году. Там среди прочего описана и шутка про Великую теорему Ферма.

Кстати, похожее равенство появлялось в сериале и раньше — в серии, посвящённой Хэллоуину в 1995 году. Там есть эпизод, в котором Гомер из своего привычного плоского мира попадает в трёхмерное пространство. В странном мире трёхмерных моделей вокруг Гомера летает множество неких загадочных научных объектов и формул. Одна из них выглядит так: 178212 + 184112 = 192212. Кстати, автор этого эпизода — уже знакомый нам Дэвид Коэн.

Чем особенны именно эти цифры?

Давайте разберёмся, чем же так примечательны эти равенства. Напомню, что интересующие нас серии «Симпсонов» вышли в 1995 и 1998 годах — время начала расцвета «Симпсонов». В эти же годы появились одноимённые Windows 95 и 98, но до появления первой версии Android оставалось ещё 10 лет. Да и сама компания Google была основана только осенью 1998 года. В то время у инженеров, учёных и математиков ещё были в ходу инженерные (или научные) калькуляторы, на которых можно было делать довольно сложные вычисления. Поэтому зрители проверяли равенство, написанное Гомером, скорее всего, с помощью такого калькулятора.

Я решил повторить этот эксперимент и отыскал свой старый добрый CASIO FX-911W, который верой и правдой служил мне на бесконечных лабораторных работах по физике и электротехнике, а потом и в аспирантуре. Как ни удивительно, спустя 20 лет калькулятор всё ещё прекрасно функционирует. Проверить уравнение несложно. Набираем:

(3987 [xy] 12 + 4365 [xy] 12) [xy] (1÷12) =

Получаем ответ: 4472.

Что примечательно, ответ целый, дробная часть полностью отсутствует. Всё выглядит так, как будто Гомер Симпсон успешно нашёл решение уравнения Великой теоремы Ферма в целых числах.

Аналогично можно проверить и второе равенство:

(1782 [xy] 12 + 1841 [xy] 12) [xy] (1÷12) =

Ответ: 1922.

Если у вас тоже есть инженерный калькулятор, вы можете разыграть своих друзей, интересующихся математикой. Секрет заключается в том, что числа 4472 и 1922 настолько близки к решению, что десяти разрядов калькулятора уже недостаточно, чтобы показать первый отличный от нуля разряд дробной части.

Современные компьютерные программы-калькуляторы уже считают гораздо точнее, с ними такой фокус не пройдёт. Например, калькулятор Google для первого выражения выдаст ответ 4472,00000001. Так что чуда не произошло — в математике «почти» не считается. Но на инженерном калькуляторе действительно выглядит эффектно.

Постановка задачи

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

Написать такую программу — задача совсем не сложная. Её решение доступно любому начинающему программисту. Нам потребуется просто перебрать значения из определённого диапазона и найти наилучшее решение.

Сформулирую задачу. Нужно найти решение Великой теоремы Ферма в целых числах (шутка!). На самом деле нужно найти целые числа a и b и целую степень p, которые дают наиболее близкое к целому число c в выражении: ap + bp = cp.

У задачи есть важное ограничение, о котором нужно не забыть. Программа не должна выдавать тривиальные решения. Например, решение 100050 + 50050 = 100050 не подходит. Понятно, что второе слагаемое настолько меньше первого, что им вообще можно пренебречь.

Кстати, в сети пишут, что Дональд Кнут в первом издании своего «Искусства программирования» (1968 год) предложил читателям написать программу, которая доказывала бы Великую теорему Ферма. Он оценил решение этой задачи по максимуму: в 50 баллов. Также пишут, что в разделе ответов он указал, что один из читателей «нашёл потрясающее доказательство, но места для него недостаточно». Дональд Кнут тоже не прочь был пошутить.

Самый простой вариант решения

Приведу здесь самый простой вариант решения. Поскольку в «Симпсонах» в обоих равенствах используются четырёхзначные числа, попробуем решить задачу именно для них. При этом будем проверять степени от 3 до 20. Чтобы избежать тривиальных решений, ограничим значение b. Пусть оно будет отличаться от a не больше, чем на 500. Отдельно найдём решение для чисел, которые чуть больше и чуть меньше требуемого целого. Выведем на экран не только варианты решения с минимальной и максимальной дробной частью, но и те, у которых дробная часть меньше 0,0000001 или больше 0,9999999.

Вот как выглядит мой вариант программы на Delphi:

			program ferma;
{$APPTYPE CONSOLE}
uses
  SysUtils, Classes, Math;
  
var
   p, a, b: integer;
   best_p_min: integer = 1;
   best_p_max: integer = 1;
   best_a_min: integer = 1;
   best_a_max: integer = 1;
   best_b_min: integer = 1;
   best_b_max: integer = 1;
   best_c_min: integer = 1;
   best_c_max: integer = 1;
   min: extended = 1;
   max: extended = 0;
   c, k, u: extended;

function print_result (a_res, b_res, c_res, p_res: integer; h_res: extended): string;
// Формирование строки с результатами
begin
result:=inttostr(a_res)+'^'+inttostr(p_res)+'+'+inttostr(b_res)+'^'+inttostr(p_res)+'='+inttostr(c_res)+'^'+inttostr(p_res)+' '+floattostrf(h_res,ffFixed,18,18);
end;
begin
   for p:= 3 to 20 do
   // Перебираем степень от 3 до 20
   begin
      for a:= 1000 to 9500 do
      // Первое слагаемое - перебираем четырёхзначные числа
      begin
         for b:= a to a+500 do
         // Второе слагаемое - перебираем следующие 500 чисел после первого слагаемого
         begin
            k:=intpower(a,p)+intpower(b,p); // Сумма a^p + b^p
            c:=power(k,(1/p)); // Корень степени p из полученной суммы
            u:=frac(c); // Дробная часть числа c
            if (u<min) then
            // Числа, которые чуть больше требуемого целого
            begin
               min:=u;
               best_p_min:=p;
               best_a_min:=a;
               best_b_min:=b;
               best_c_min:=trunc(c); // Целая часть числа c
            end;
            if (u<0.0000001) then writeln(print_result(a, b, trunc(c), p, u));
            if (u>max) then
            // Числа, которые чуть меньше требуемого целого
            begin
               max:=u;
               best_p_max:=p;
               best_a_max:=a;
               best_b_max:=b;
               best_c_max:=trunc(c)+1; // Целая часть числа c, увеличенная на 1
            end;
            if (u>0.9999999) then writeln(print_result(a, b, trunc(c)+1, p, u));
         end;
      end;
   end;

   // Выводим лучшие результаты
   writeln('Best min result: '+print_result(best_a_min, best_b_min, best_c_min, best_p_min, min));
   writeln('Best max result: '+print_result(best_a_max, best_b_max, best_c_max, best_p_max, max));
   
end.
		

Даже такой простейший вариант программы выдаст нам много чего интересного. Итак, для начала посмотрим на варианты решения с минимальной дробной частью. Решения расположены в порядке уменьшения дробной части. В таблице выделена строка с решением Гомера Симпсона.

Похоже, в этом случае Гомер Симпсон нашёл самый подходящий ответ для четырёхзначных чисел.

Теперь посмотрим на аналогичную таблицу, содержащую варианты решения с максимальной дробной частью. Решения расположены в порядке возрастания дробной части.

Здесь решение Гомера Симпсона только на втором месте. Похоже, Дэвид Коэн в своей программе не дошёл до степени 20. Это уже интересный результат.

Если в нашей программе увеличить максимальную степень до 30, то лучший результат в первой таблице останется неизменным, а во второй таблице появится новый максимум: 672724 + 698424 = 708424. Остаток — 0,999999982255980857. А вот увеличение максимальной степени до 50 этот результат уже не поменяет.

Для трёхзначных чисел и степеней от 3 до 20 лучшие решения будут такими:

Только вот на калькуляторе они уже выглядят не так феерично: отображается дробная часть. Так что выбор четырёхзначных чисел был вполне оправдан.

В итоге нам удалось не только повторить решение Гомера Симпсона, но и найти несколько других подходящих вариантов. И один вариант оказался даже лучше, чем у Гомера!

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