Тяжело искать ответы в бесконечном пространстве. Математика уровня старших классов может помочь вам сузить область поисков.
![](https://habrastorage.org/getpro/habr/post_images/938/2c1/49a/9382c149a1c6f3c643d419ef0f9eb94a.jpg)
Учитывая, что люди изучают свойства чисел тысячи лет, можно было бы решить, что нам известно всё о числе 3. Однако недавно математики обнаружили нечто новое касательно числа 3: третий способ выразить это число в виде суммы трёх кубов. Задача записи числа через сумму трёх кубов целых чисел оказывается неожиданно интересной. Легко показать, что большую часть чисел нельзя записать в виде одного куба или суммы из двух кубов, но существует гипотеза, что большую часть чисел можно записать в виде суммы из трёх кубов. Однако найти эти кубы оказывается иногда чрезвычайно сложно.
К примеру, нам было известно, что число 3 можно записать в виде 13 + 13 + 13, а также в виде 43 + 43 + (-5)3, однако более 60 лет математиков интересовал вопрос, нет ли ещё одного способа сделать это. И в этом сентябре Эндрю Букер и Эндрю Сазерленд, наконец, нашли и третий способ:
3 = 569 936 821 221 962 380 7203 + (−569 936 821 113 563 493 509)3 + (−472 715 493 453 327 032)3
Если вам захочется проверить этот результат, не пытайтесь использовать калькулятор. Большинство из них не справится с таким количеством цифр. Но с этим справится WolframAlpha.
В поисках новых вариантов решений для числа 3, математики используют техники, придуманные в этом году Буккером, первым нашедшим сумму трёх кубов для числа 33. Но почему на подобные прорывы требуется столько времени? В поисках правильных кубов приходится покрывать очень большую территорию, а нужное направление нам может указать лишь небольшое число подсказок. Поэтому фокус состоит в том, чтобы найти более хитрые методы поиска. Чтобы представить себе саму задачу и её решение, начнём с более простого вопроса: как мы можем записать 33 в виде суммы трёх целых чисел?
Мы можем записать 33 = 19 + 6 + 8, или 33 = 11 + 11 + 11, или 33 = 31 + 1 + 1. Мы можем использовать и отрицательные числа: 33 = 35 + (−1) + (−1). Существует бесконечное множество способов сделать это, поскольку всегда можно увеличить одно или два числа и уменьшить третье для компенсации этого – например, 33 = 36 + (−1) + (−2), 33 = 100 + 41 + (−108), и так далее.
Что насчёт записи 33 в виде суммы трёх квадратов? Нам нужно будет найти числа, являющиеся квадратами целых чисел, типа 1 = 12, 9 = 32, и 64 = 82 — их сумма даёт 33. Немного поигравшись, можно обнаружить, что 33 = 42 + 42 + 12 и 33 = 52 + 22 + 22. Есть ли ещё варианты? В принципе, нет. Можно заменить 4 на -4, и получить 33 = (-4)2 + 42 + 12, что даст нам ещё несколько способов записи наши решений, но как их ни считай, найдётся не очень много способов записать 33 в виде суммы трёх квадратов.
При суммировании квадратов у нас нет той же гибкости, что при суммировании любых целых чисел. У нас меньше выбор, и, что ещё важнее, сложение лишь увеличивает нашу сумму. Ведь квадраты целых чисел не бывают отрицательными – возведение в квадрат и положительного и отрицательного числа всегда даёт положительное.
У квадратов больше ограничений, но это даёт нам и нечто полезное: наше пространство поисков «ограничено». Пытаясь найти три квадрата, дающих в сумме 33, мы не можем использовать числа, чьи квадраты больше, чем 33, поскольку как только наша сумма выйдет за пределы 33, уменьшить её уже не получится. А это значит, нам нужно рассмотреть лишь комбинации из 02, 12, 22, 32, 42 и 52 (их отрицательные двойники ничего нового нам не дают, и мы их проигнорируем).
Имея шесть вариантов для каждого их трёх квадратов, мы получаем не более 6 × 6 × 6 = 216 способов записать 33 как их сумму. Достаточно небольшой список для того, чтобы проверить все возможности и убедиться, что мы ничего не пропустили.
Теперь вернёмся к задаче о сумме трёх кубов. Несложно видеть, что она комбинирует ограниченный выбор из задачи о сумме квадратов с бесконечным пространством поиска из задачи о сумме целых чисел. Как и с квадратами, не любое целое число является кубом другого числа. Мы можем использовать числа типа 1 = 13, 8=23, 125=53, но не можем использовать 2, 3, 4, 10, 108, и большую часть остальных чисел. Но, в отличие от квадратов, кубы бывают отрицательными – к примеру, (-2)3 = -8, (-4)3 = -64 – а значит, мы можем по необходимости и уменьшать нашу сумму. Доступ к отрицательным числам даёт нам неограниченное количество вариантов, то есть, наше пространство поиска, как и в случае с суммой целых чисел, неограниченно.
Неограниченность пространства поиска означает, что мы можем искать ответы очень долго. И люди искали их десятилетиями. Понадобился суперкомпьютер и хитрая математика, чтобы найти, наконец, правильную комбинацию кубов. Давайте посмотрим, как это удалось сделать.
Допустим, вам нужно найти решение уравнения:
33 = x3 + y3 + z3
Простой подход – разметить некий регион чисел и подставлять каждый из них, пока что-нибудь не подойдёт. Если вы ничего не найдёте, можно определить новое пространство поиска и начать сначала. Это похоже на поиск новых планет при помощи методичного изучения неба в телескоп.
Представьте, что ваше начальное пространство поиска ограничивает все x, y и z рамками от -100 до 100. Сначала вы пробуете:
(−100)3 + (−100)3 + (−100)3
Не вышло. Тогда вы пробуете:
(−99)3 + (−100)3 + (−100)3
Тоже не работает. Вы продолжаете, пока не дойдёте до (100, −100, −100), потом переключаетесь на (−100, −99, −100), и вновь продолжаете свою охоту. В итоге вы проверите порядка 200 × 200 × 200 = 8 000 000 вариантов, не найдя ничего подходящего. Придётся обозначить новое пространство поиска и начать заново.
Более интересный подход – переписать уравнение в следующем виде:
33 – (x3 + y3) = z3
Теперь, вместо того, чтобы перебирать все тройки (x, y, z), мы будем перебирать двойки (x, y). Для каждой пары мы будем вычислять результат, а потом проверять список кубов, смотря, нет ли там нашего результата z3. Если он есть, решение найдено. Если нет, мы продолжим искать. Это значительно уменьшает пространство поиска. Вместо 8 000 000 троек мы теперь ищем среди 200 × 200 = 40 000 пар. Серьёзная экономия, однако всё равно недостаточно для того, чтобы сделать задачу вычислительно доступной.
Ещё более удобный подход — переписать уравнение в следующем виде:
33 – z3 = x3 + y3
Теперь мы перебираем z, а для каждого вычисленного z мы используем хитрый фокус из курса математики. Выражение x3 + y3 всегда можно разложить так:
x3 + y3 = (x + y)(x2 – xy + y2)
Это формула для суммы кубов. Чтобы проверить её, просто перемножим правую часть, пользуясь правилом дистрибутивности:
(x + y)(x2 – xy + y2) = x3 – x2y + xy2 + yx2 – xy2 + y3 = x3 + y3
Как это помогает нам в поисках? Подсчитав 33 – z3, мы раскладываем её на произведение простых чисел, с чем хорошо справляются компьютеры, по крайней мере, в интересующем нас числовом диапазоне. Разложив 33 – z3 на множители, мы проверяем, можно ли составить эти множители в виде (x + y)(x2 – xy + y2). Если да, мы нашли решение.
Допустим, к примеру, что мы пытаемся записать 34 как сумму трёх кубов, и наши поиски привели нас к z = -6. Мы подсчитываем 34 – z3 = 34 – (-6)3 = 34 – (-216) = 34 + 216 = 250, и теперь разложим 250.
Изучив вопрос, мы понимаем, что можем записать 250 = 10 × 25 = (5+5)(52 – 5 × 5 + 5²). А это именно (x + y)(x2 – xy + y2) для x = 5 и y = 5, так что тройка (x, y, z) = (5, 5, -6) должна сработать для 34. И, конечно же, 34 = 53 + 53 + (-6) 3, и мы успешно обнаружили три куба, сумма которых даёт 34.
Такой метод позволяет вместо 2003 = 8 000 000 троек или даже 2002 = 40 000 пар исследовать 200 возможных вариантов z. Дополнительную работу составляют разложение на множители и проверка, но в целом поисковая эффективность серьёзно растёт. И всё равно пространство поисков, изученное в поисках суммы кубов, дающих такое число, как 33, настолько огромно, что даже такие улучшения не могут помочь суперкомпьютерам близко подступиться к этой задаче.
Тут на сцену и вышел Эндрю Букер. Он разработал некоторые дополнительные техники, используя алгебру и теорию чисел, для ещё более сильного улучшения поисковой эффективности. Напустив суперкомпьютер своего университета на эту задачу, через три недели он получил впервые найденное представление числа 33 как суммы трёх кубов:
33 = 8 866 128 975 287 5283 + (−8 778 405 442 862 239)3 + (−2 736 111 468 807 040)3
Решив эту задачу, перед тем, как перейти к числу 3, Букер и Сазерленд решили такую же задачу для числа 42:
42 = (−80 538 738 812 075 974)3 + 80 435 758 145 817 5153 + 12 602 123 297 335 6313
Вас может удивить, что спустя тысячи лет, мы ещё можем узнать что-то новое о таких числах, как 3, 33 и 42. Возможно ещё более удивительным будет то, что этому могут помочь такие абстрактные вещи из школьной математики, как формула для суммы кубов. Однако так работает математика, и поэтому мы продолжаем наши изыскания. Так что следите за числом 114 – самым маленьким из чисел на сегодня, для которого пока ещё не найдена сумма из трёх кубов. У меня есть ощущение, что для Эндрю Букера и других математиков поиск уже начался.