Гипотеза Эйлера
Back Home Up Next

Среди многочисленных гипотез, выдвинутых Л. Эйлером и, как правило, впоследствии оказавшихся верными, имеется и такое утверждение, сформулированное им в середине XVIII века:

Для любого натурального показателя k³3 и натуральных n1, n2, ..., np диофантово уравнение

                                                 (4)

не имеет решений.

Если гипотеза Эйлера справедлива, то из неё, как частный случай при p=2, следует справедливость Великой Теоремы Ферма.

Попытки доказать или опровергнуть эту гипотезу предпринимались в течение более чем 200 лет и профессионалами, и любителями математики. Однако все затраченные усилия были напрасными. И только лишь в 1967 году с помощью компьютера американскими учеными Л.Лендером и Т.Паркином гипотеза Эйлера была опровергнута [7, с.101-103; 31, с.150]. Составленная ими программа выдала следующий результат:

 275 + 845 + 1105 + 1335 = 1445.

Тем самым гипотеза Эйлера оказалась неверной и еще раз была подтверждена эффективность использования компьютера для опровержения утверждений общего характера.

адача 11. Составить программу-функцию для подбора методом возвратной рекурсии решения диофантова уравнения

,                                                            (5)

 то есть для получения одного или нескольких контрпримеров к гипотезе Эйлера.

Решение. Пусть en - натуральное число. Можно было бы подвергнуть испытанию все пятерки чисел (n0    n1    n2    n3    n4)T c ni£en (i = 0, 1, ..., 4). Но в подобном полном переборе всех вариантов необходимости нет. Во-первых, не ограничивая общности, можно считать, что n0£n1£n2£n3£n4. Во-вторых, проверки будут выполняться существенно быстрее, если не вычислять всякий раз пятые степени чисел, а выбирать их значения из заранее заготовленного массива. Создать его можно, например, так:

В-третьих, изменения следует вести только по четырем переменным. Для пятой переменной подходящее значение следует вычислять непосредственно. С учетом сказанного и использованием возвратной рекурсии для решения поставленной задачи можно предложить следующую пару функций:

                                    (6)

                                                                (7)

Рекурсия здесь организована по последовательным номерам (от нуля до трех) переменных левой части (5) по ранее рассмотренной возвратной схеме 3. Поэтому ограничимся лишь описанием фактических аргументов функции Eu(be, en, S, n, j):

be, en - соответственно нижняя и верхняя границы значений переменных ni (i = 0, 1, 2, 3);

S - переменная для формирования суммы левой части (5);

n = (n0    n1    n2    n3    n4)T - возвращаемый вектор, в котором формируются кандидаты на решение уравнения (5) и само решение, если его удается найти. Если n4 ¹ 0, то n и есть найденное решение, то есть контрпример к гипотезе Эйлера. Если n4 = 0, то в исследуемой области значений переменных контрпример построить не удалось;

j - уровень рекурсивного вызова.

Более быстро уравнение (5) решается с помощью пары функций - Eul(be, en, S, n, otv, j) и Eulmain(en). В них, как и раньше в (6)-(7), решение ищется в области 1£nj£en (j = 0, 1, 2, 3), но вычисления не прекращаются при получении первого контрпримера. Совокупность найденных решений формируется в виде столбцов матрицы ответов otv. Начальный столбец otv состоит из нулей. Остальные параметры этих функций имеют тот же самый смысл, что и соответствующие им (по именам) параметры функции Eu(). Рекурсия в Eul() организована по последовательным номерам переменных nj (j = 0, 1, 2, 3), но не от нуля до трех, а от трех до нуля.

Основная отличительная особенность рекурсивной функции Eul() от Eu() состоит в том, что в Еu() проверке на возможное решение подвергаются все четверки вида n0£n1£n2£n3 (n4 - вычисляется), а в Eul() при фиксировании nj (j = 3, 2, 1) нижняя граница для nj-1 вычисляется. Делается это исходя из следующих соображений. Пусть nj (j > 0) зафиксировано, и при этом уже подсчитана величина . Пусть, далее, при некотором натуральном k kS£S<(k+1)S, то есть Pk£S<Pk+1. Тогда для решения (n0  n1  n2  n3  n4)T уравнения (5) должно, очевидно, выполняться неравенство . Отсюда имеем: , то есть

Именно это неравенство и лежит в основе алгоритма, реализуемого функцией Eul().

Контрольные примеры:

              

Как мы видим, в области 1 £ ni £ 135 (i = 0, 1, 2, 3) программой Eulmain() обнаружен ранее указанный в [7, с.101-103] контрпример к гипотезе Эйлера. Имеет ли еще какие-либо решения уравнение (5)? Да, имеет. Например, это векторы вида m×[27   84   110   133    144]T при любом натуральном m.

Назовем решение n = (n1    n2    n3    n4     n5)T уравнения (5) примитивным, если наибольший общий делитель его компонентов равен единице. Очевидно, что найденный контрпример - примитивное решение. Есть ли еще примитивные решения в (5), неизвестно. Вычисления, проведенные по аналогам программ Eulmain() и Eul(), написанным на Object Pascal (Delphi 5), показали, что в области 1 £ ni £ 1000 (i = 0, 1, 2, 3) их нет.

Home Содержание Схемы ООД Доска объявлений Поиск