![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
Короче
Многие слова, многие печали. Одной из самых коротких научных статей считается математическое опровержение гипотезы Эйлера.
Сегодня любой пятиклассник слышал про Великую теорему Ферма, сформулированную в 1637 году Пьером Ферма в виде:
a1n + a2n = bn
Если число степени n = 2, мы получаем обычную теорему Пифагора, когда квадрат гипотенузы равен сумме квадратов катетов, ее простейшим решением является выражение:
32 + 42 = 52
известное еще очень древним египтянам сильно до рождества Христова.
Ферма предположил, что при n > 2 задача не имеет решений в целых числах. Историки считают, что Ферма обманул читателей и на самом деле не знал полного решения собственной теоремы. По крайней мере, он нашел и привел только самое простое частное доказательство для n = 4.
Через 133 года Леонард Эйлер доказал теорему для n = 3, а еще через 55 лет Дирихле решил ее (в смысле математически доказал, что решения нет) для n = 5. Дальше пошло-поехало, подоспели доказательства для иных частных случаев, где n=7 и так далее. Полное решение Великой теоремы Ферма было найдено лишь в 1994 году английским математиком Эндрю Уайлсом, причем оказалось настолько заумным, что другие математики в течение семи(!) лет пытались прочитать формулы и понять в чем суть, и нет ли в доказательстве ошибок, окончательно подтвердив, что решение верное только к 2001 году.
Великая теорема Ферма уже 22 года как доказана, %username%!
А в 1770 году Эйлер, окрыленный успехами в частичном доказательстве теоремы Ферма, задумал ее расширить и усугубить. Он сформулировал так называемую "гипотезу Эйлера", которая похожа на теорему Ферма, но имеет более общий вид:
a1n + a2n + ... + akn = bn
Эйлер заявил, что данная формула не имеет целочисленных решений при k < n, то есть, если количество слагаемых слева меньше степени уравнения, то решений нет, например:
a14 + a24 + a34 = b4
или
a15 + a25 + a35 + a45 = b5
и так далее нерешаемо, а теорема Ферма - лишь частный и упрощенный случай.
В 1966 году математики Ландер, Паркин и Селфридж опубликовали научную работу на полстранички, она выглядела так:
и содержала найденное ими опровержение гипотезы Эйлера.
no subject
no subject
Результат получен за 50 секунд.
Процессор Haswell, ОС Linux Ubuntu, JDK8
Теперь можно улучшать результат - алгоритм поумнее, параллельные вычисления и т.д. Но лениво.
PS: Одновременно с расчётом на компе крутились - сервер БД MySQL, медиасервер Plex, с которого смотрелся фильм в HD, работало IDE Eclipse Neon плюс качались торренты.
no subject
no subject
no subject
no subject
C++, четыре вложенных цикла + поиск в хеш–таблице
Intel(R) Core(TM) i7 CPU Q 720 @ 1.60GHz
Если ограничить цикл числом 150, то отрабатывает за 0.3 секунды
Если ограничить цикл числом 256, то отрабатывает за 1.5 секунды
no subject
no subject
Однако авторы пишут о "smallest instance". В общем, интересно, а какое следующее решение? Есть ли оно?
no subject
no subject
Тоже в лоб перебором с поиском по хешу.
no subject
no subject
https://gist.github.com/speshuric/e9edae0f0cdf324311466e84a94ea865
(код понятен даже если не знать kotlin)
1. Я сразу искал y>x1>=x2>=x3>=x4, причем цикл по y от 0 вверх, а по остальным от предыдущего вниз.
2. И снизу ограничил: x1^4>=y^4/4, x2^4>=(y^4-x1^4)/3, x3^4>=(y^4-x1^4-x2^4)/2 - оно как бы следует из предыдущего.