Опровергнутая гипотеза Эйлера утверждает, что для любого натурального числа n > 2 никакую n-ю степень натурального числа нельзя представить в виде суммы ( n ? 1 ) n-х степеней других натуральных чисел. (wikipedia)
Известны контрпримеры для n=4:
4224814 = 2175194 + 958004 + 4145604
206156734 = 187967604 + 153656394 + 26824404
и для n=5:
1445 = 1335 + 1105 + 845 + 275
Для n >= 6 известных контрпримеров нет.
Нашел новый контрпример для n=4:
28130014 = 27676244 + 13904004 + 6738654
Прямолинейный перебор всех возможных троек натуральных x, y, z и проверка, не является ли сумма их четвертых степеней четвертой степенью какого-то натурального числа t конечно будет слишком медленным. Нужны способы ускорить перебор вариантов.
Вспомнив малую теорему Ферма и рассмотрев сравнение
x4 + y4 + z4 = t4
по модулю 5, можно понять, что в левой части два числа кратны 5. Пусть это будут x и y. Поскольку имеет смысл искать четверки, не имеющие общего делителя, t и z должны быть не кратны 5. Перенесем z вправо:
x4 + y4 = t4 - z4
Левая часть кратна 625. Поэтому t4 ? z4 mod 625
Это позволяет сразу сократить перебор более чем в 150 раз — вместо всех значений z можно выбирать только корни 4 степени из t по модулю 625.
Можно t4 - z4 поделить на 625 и попытаться представить результат в виде суммы двух четвертых степеней.
Но прежде, чем начинать перебирать все возможные значения x/5 и y/5, надо дополнительно проверить некоторые ограничения.
Например, из теоремы о представлении натуральных чисел в виде суммы двух квадратов, если сумма двух квадратов делится на 3, то она должна делиться на 9. Но на самом деле для 4 степени есть более жесткие ограничения. Например, по модулю 16 четвертая степень нечетного числа всегда сравнима с 1. Поэтому остаток от деления на 16 для суммы двух четвертых степеней не может быть больше 2. То же самое по модулю 5. Также можно найти ограничения на возможные остатки по модулям 13 и 29.
Реализовав все эти проверки в программе, удалось найти известное решение 4224814 = 2175194 + 958004 + 4145604 за пару минут, и новое 28130014 = 27676244 + 13904004 + 6738654 за несколько часов.
Известны контрпримеры для n=4:
4224814 = 2175194 + 958004 + 4145604
206156734 = 187967604 + 153656394 + 26824404
и для n=5:
1445 = 1335 + 1105 + 845 + 275
Для n >= 6 известных контрпримеров нет.
Нашел новый контрпример для n=4:
28130014 = 27676244 + 13904004 + 6738654
Прямолинейный перебор всех возможных троек натуральных x, y, z и проверка, не является ли сумма их четвертых степеней четвертой степенью какого-то натурального числа t конечно будет слишком медленным. Нужны способы ускорить перебор вариантов.
Вспомнив малую теорему Ферма и рассмотрев сравнение
x4 + y4 + z4 = t4
по модулю 5, можно понять, что в левой части два числа кратны 5. Пусть это будут x и y. Поскольку имеет смысл искать четверки, не имеющие общего делителя, t и z должны быть не кратны 5. Перенесем z вправо:
x4 + y4 = t4 - z4
Левая часть кратна 625. Поэтому t4 ? z4 mod 625
Это позволяет сразу сократить перебор более чем в 150 раз — вместо всех значений z можно выбирать только корни 4 степени из t по модулю 625.
Можно t4 - z4 поделить на 625 и попытаться представить результат в виде суммы двух четвертых степеней.
Но прежде, чем начинать перебирать все возможные значения x/5 и y/5, надо дополнительно проверить некоторые ограничения.
Например, из теоремы о представлении натуральных чисел в виде суммы двух квадратов, если сумма двух квадратов делится на 3, то она должна делиться на 9. Но на самом деле для 4 степени есть более жесткие ограничения. Например, по модулю 16 четвертая степень нечетного числа всегда сравнима с 1. Поэтому остаток от деления на 16 для суммы двух четвертых степеней не может быть больше 2. То же самое по модулю 5. Также можно найти ограничения на возможные остатки по модулям 13 и 29.
Реализовав все эти проверки в программе, удалось найти известное решение 4224814 = 2175194 + 958004 + 4145604 за пару минут, и новое 28130014 = 27676244 + 13904004 + 6738654 за несколько часов.