Блог проекта iLWN

Дневник  •  Список статей
30 апреля 2022
Что сейчас происходит на проекте iLWN

Сегодня я хочу рассказать о том, что сейчас происходит на проекте iLWN. После переезда на другой хостинг, пропала старая главная страница раздела MDPN с интересной информацией. Я восстановлю её позже, потому что считаю, что сейчас важнее закончить другие уже начатые задачи.

В таск-листе проекта сейчас более 130 задач, многие из них планировалось завершить ещё несколько месяцев назад. И количество этих задач пока только растёт. Я просто не успеваю делать всё то, что мне хотелось бы сделать.

И если говорить о приоритетах, то на первом месте — обеспечение возможности непрерывных вычислений, на втором — работа с блогом проекта. И только затем исходный код в публичном репозитории и публикация информации на веб-сайте (и в том числе перевод). Из-за нехватки времени, сейчас я публикую только самые важные результаты.

Вычисления на проекте MDPN не прерываются, и в данный момент по прежнему последовательно проверяются числа 23-значного диапазона и уже пройдена отметка в 6.1%. Отдельно на GPU GeForce GTX 1060 (да, это CUDA!) проверяется начало диапазонов 26- и 27-значных чисел в поисках новых результирующих палиндромов (проверено 53.4% и 7.8% соответственно).

Последние две недели я, в основном, занимаюсь (и продолжу в ближайшие дни) восстановлением блога, возникшим при возвращении к старому формату. И поэтому я продолжу добавление записей «задним числом». Да, это неудобно, но считаю, что так будет лучше.

Также я занимаюсь алгоритмами для уравнений степеней 3, 4, 5 и 7 (проект ESLP), реализацией критически важных функций программы и накоплением результатов вычислений для диофантовых уравнений указанных степеней, чтобы позже выложить всё на странице проекта.

• • •
28 апреля 2022 · ESLP
Пропущенные оптимизации для уравнения 4.1.4 и новый алгоритм для 4.1.5

Сегодня был полностью переработан специализированный алгоритм для уравнения 4.1.5. Изменён подход к организации внешнего цикла (по аналогии с 4.1.4) и добавлены все возможные математические оптимизации, основанные на сравнимости чисел в четвёртой степени и их сумм.

Как результат, алгоритм стал работать быстрее примерно в 1.6 раза. Да, эффект совсем незначительный по сравнению с эффектом для 4.1.4. Всё из-за того, что подавляющая часть времени вычислений приходится на проверку случаев, когда старший коэффициент уравнения кратен 5. В этих случаях все пять коэффициентов правой части уравнения всегда должны быть некратны 5. Эти приводит к очень большому количеству итераций, так как из каждых 5 кандидатов мы можем пропустить только один.

Также для алгоритма 4.1.4 были добавлены пропущенные оптимизации в цикле перебора значений второго коэффициента (сравнимость по модулю 5 и 16). По непонятной причине эти оптимизации применялись к перебору только старшего коэффициента правой части. Тогда как в случае 4.1.4 они работают и для второго коэффициента. Также была добавлена проверка на сравнимость суммы двух последних коэффициентов по модулю 17. Эта проверка не имеет эффекта для 4.1.3, но хорошо работает для 4.1.4 и 4.1.5. Как итог, скорость работы выросла ещё примерно в 2.4 раза!

• • •
27 апреля 2022 · ESLP
Новый алгоритм для уравнения вида 4.1.4

Несколько дней назад я рассказывал о том, что улучшил алгоритм для диофантова уравнения вида 4.1.4. Тогда я просто добавил несколько проверок внутри циклов (сравнимость по модулю 13 и 29, а также кратность 625), что привело к росту производительности примерно в три раза.

Сегодня я решил немного поэкспериментировать. Действуя методом проб и ошибок, я обнаружил, что используемый алгоритм крайне неэффективен! Оказалось, что если во внешнем цикле перебирать не нечётные значения коэффициента, а некратные 5, то это будет значительно быстрее. Код нового алгоритма стал даже проще, чем раньше, хоть при этом и длиннее (284 строки против 180)!

Так, для того чтобы достичь значения старшего коэффициента 85,233, старому алгоритму понадобилось 12 часов и 32 минуты. А новый алгоритм достиг коэффициента 85,277 всего за 25 минут (а точнее за 1502 секунды работы)! Таким образом, скорость поиска для данного уравнения выросла в 30 раз! Честно сказать, я и сам удивлён.

В ближайшие дни я постараюсь выложить новую версию (это будет версия 0.34) программы ESLP, в которую войдут обновлённые алгоритмы для уравнений 4.1.3, 4.1.4 и 4.1.5. Но сначала проверю, можно ли применить аналогичные изменения к алгоритмам для 4.1.3 и 4.1.5. Было бы очень здорово, если их также удалось бы улучшить!

Update Позже, занимаясь анализом алгоритма для уравнения 4.1.5 (да, оказалось, что его также можно улучшить), я понял, что упустил ещё несколько значимых моментов в алгоритме для уравнения 4.1.4. Несколько небольших изменений повысили скорость его работы ещё примерно в 2.4 раза! Доработанный алгоритм справился с указанным выше диапазоном за 10 минут и 19 секунд!

• • •
25 апреля 2022 · ESLP
Поиск решений диофантова уравнения вида 4.1.3

После улучшения алгоритма для уравнения 4.1.3, которое привело к более чем трёхкратному увеличению скорости его работы, я решил потратить некоторое время на поиск решений этого диофантова уравнения.

Дело в том, что для меня ситуация с ним не совсем ясна. С одной стороны, это одно из наиболее хорошо исследованных уравнений. А с другой стороны, мне не удалось найти достоверных сведений о том, какие диапазоны значений старшего коэффициента были проверены.

На сегодняшний день известно о 23 решениях этого уравнения. И за прошедшие 2 дня моей программой были подтверждены первые 7 из них. Я убедился, что кроме этих решений в диапазоне значений старшего коэффициента до 21 миллиона других примитивных решений нет. Однако старший коэффициент следующего известного решения превышает 44 миллиона! То есть оно находится необычно далеко от всех предыдущих решений.

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

Проанализировав плотность решений для уравнений 2.1.2, 2.1.3, 3.1.3, 3.1.4, 4.1.4 и 4.1.5, я обнаружил, что для всех из них плотность решений растёт по мере увеличения значения старшего коэффициента. Причём, чем больше слагаемых в правой части, тем быстрее рост. Для уравнений 2.1.2 и 4.1.4 этот рост выражен очень слабо. И поэтому далее я предположил, что для уравнения 4.1.3 плотность решений может, наоборот, снижаться. Но если для первых 7 его решений плотность равна 0.34-0.37 решений на миллион значений, то для 8-го решения она резко уменьшается до 0.18! Что не совсем обычно.

Предположительно, для 8-го решения значение старшего коэффициента должно быть от 23.5 до 26.5 миллиона. Сейчас скорость проверки составляет примерно 160 тысяч в час. Поэтому на поиск всех решений до верхней границы указанного диапазона понадобится ещё около 2 дней вычислений.

• • •
24 апреля 2022 · ESLP
Обновлён алгоритм для уравнения вида 4.1.3

Из всех алгоритмов для диофантовых уравнений четвёртой степени, больше всего меня озадачивает уравнение 4.1.3. Дело в том, что именно это уравнение самое сложное для поиска решений. И я уже несколько раз пытался улучшать этот алгоритм. Сегодня я предпринял очередную попытку, которая оказалась весьма удачной!

С самого начала (с вводной статьи) во всех алгоритмах для поиска 2 младших коэффициентов использовался цикл (перебор предпоследнего коэффициента) + проверка хеша (последний коэффициент) + бинарный поиск в массиве степеней.

Это очень эффективный метод: с помощью проверки хеша мы быстро выясняем, существует ли такое число, степень которого нам известна, и при положительном ответе довольно быстро (за log(N) итераций) находим искомое число в отсортированном массиве (или убеждаемся в его отсутствии в случае коллизии хеша).

Однако у этого способа есть недостаток, наиболее сильно проявляющийся именно при поиске решений уравнения 4.1.3. Коэффициенты этого уравнения очень большие с самого начала поиска и поэтому хеш быстро становится малоэффективным, а бинарный поиск требует большого количества итераций.

Сегодня мне удалось увеличить скорость работы алгоритма примерно в 3.7 раза. Для этого пришлось полностью отказаться от проверки хеша и бинарного поиска, заменив их одним простым циклом, в котором перебираются сразу оба последних коэффициента.

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

Несмотря на свою простоту, этот способ оказался значительно эффективнее. И в отличие от бинарного поиска, он гораздо дружелюбнее к контроллеру памяти: чтение данных из массива степеней стало последовательным (против случайного чтения у бинарного поиска).

• • •
21 апреля 2022 · ESLP
Немного оптимизаций из алгоритма для уравнения 4.1.3 для уравнений 4.1.4 и 4.1.5

Вчера, в очередной раз пробегая взглядом по алгоритмам поиска решений диофантовых уравнений вида 4.1.n, я заметил, что по какой-то причине не использую в специализированных алгоритмах для 4.1.4 и 4.1.5 некоторые оптимизации, применяемые для 4.1.3. Степень уравнений одна и та же, а значит эти оптимизации должны работать во всех алгоритмах!

Дело в том, что у чисел, возведённых в четвёртую степень, есть интересная особенность. Так, значение любого натурального числа в четвёртой степени будет сравнимо с 0, 1, 3 или 9 по модулю 13. А если два таких числа в четвёртой степени сложить, то их сумма будет сравнима с 0, 1, 2, 3, 4, 5, 6, 9, 10 или 12. Другими словами, сумма никогда не будет сравнима с 7, 8 и 11 по модулю 13! И вот это уже важно.

Этот факт можно использовать для оптимизации перебора 2 последних коэффициентов. Когда нам уже известна их предполагаемая сумма, мы можем быстро проверить, сравнима ли она с 7, 8 или 11 по модулю 13. И если да, то искать сами коэффициенты нет смысла, так как очевидно, что не существует двух таких натуральных чисел, сумма четвёртых степеней которых была бы равна заданной.

Аналогичным образом для четвёртой степени работает сравнимость по модулю 29. Я думаю, что эта тема заслуживает более детального изучения. Поэтому я планирую позже собрать все сведения об этом классе оптимизаций в отдельной статье блога.

Несравнимость по модулю 13 и 29 вместе с проверкой на кратность 625 разности левой части уравнения и значений степеней коэффициентов правой части привели к трёхкратному росту скорости поиска решений уравнения 4.1.4! Алгоритм для уравнения 4.1.5, добавленный в программу два дня назад, также значительно ускорился.

• • •
19 апреля 2022 · ESLP
Специализированный алгоритм для уравнения 4.1.5

Среди всех диофантовых уравнений вида 4.1.n для уравнений 4.1.3 и 4.1.4 уже написаны специализированные (быстрые) алгоритмы поиска решений. Для уравнения 4.1.6 и выше универсальный алгоритм работает достаточно быстро для того, чтобы найти первые 100 тысяч примитивных решений (на это ему требуется около 1 минуты).

А вот для уравнения 4.1.5 универсальный алгоритм оказался недостаточно быстр: за один час работы программа нашла около 63 тысяч первых решений для этого уравнения. Поэтому я решил, что для него также стоит добавить реализацию, аналогичную 4.1.4, тем более что это совсем не сложно.

Update Около 103 тысяч первых решений были найдены новой версией программы всего за 34 минуты. На мой взгляд, это достаточно быстро! Коэффициент в левой части (самый старший коэффициент уравнения), на котором закончились вычисления, равен 7,367. Позднее поиск будет продолжен до значения коэффициента 10,000 или немного больше.

Update После завершённой 28 апреля доработки алгоритмов для уравнений 4.1.4 и 4.1.5 новая версия программы выполнила поиск первых 63 тысяч примитивных решений ровно за 4 минуты, а первых 103 тысяч решений — всего за 13 минут и 42 секунды. На поиск всех 272,252 примитивных решений до значения старшего коэффициента 12,000 потребовалось 2 часа и 47 минут.

• • •
13 апреля 2022
Появилась возможность поддержать проект на Boosty.to!

Сегодня я зарегистрировался на платформе boosty.to и настроил страницу проекта iLWN. Для тех, кто не знает, Boosty — это сервис, аналогичный Patreon, который позволяет оформить ежемесячную подписку и таким образом финансово поддерживать авторов и их проекты.

Сейчас доступны только 2 варианта подписки (30 и 100 рублей в месяц), а также настроена цель — набрать 25 подписчиков. По мере увеличения количества подписчиков, я добавлю и другие уровни.

Если Вам интересен проект, Вы следите за его жизнью и хотели бы ему помочь — выберите подходящий для Вас уровень, оформив подписку. Сейчас минимальная сумма — всего 30 рублей. Независимо от выбранного уровня, Ваша подписка будет означать, что проект iLWN интересен не только мне одному! И для меня это очень важно!

Если подписка по какой-то причине Вам не подходит, то Вы также можете разово пожертвовать проекту любую комфортную сумму! Чтобы это сделать, нужно перейти на страницу проекта и в левой колонке «Цели» нажать кнопку «Поддержать».

Ну а если Вы пока не решили, оформлять подписку или нет (от неё, кстати, можно отписаться в любой момент), не проходите мимо, нажмите на кнопку «Отслеживать», чтобы получать уведомления о появлении новых постов в блоге проекта iLWN на Boosty!

Хотел бы отметить, что на платформе Boosty при оформлении подписки можно указать сумму, большую рекомендованной, и это, на мой взгляд, очень здорово! Регистрация в сервисе реализована очень удобно, не требует никаких данных о пользователе и занимает совсем немного времени. Интерфейс прост, интуитивно понятен и не содержит ничего лишнего!

• • •
7 апреля 2022
О текущем состоянии проекта

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

Из значимых событий хочу рассказать, что сайт переехал с Amazon AWS в Яндекс облако. В целом полёт нормальный, но пришлось немного повозиться. Да, конкретно для этого проекта выходит немного дороже, но что делать, времена сейчас такие. Уверен, что этот переезд весьма позитивен для проекта. И немного позже я поделюсь своими планами.

Касательно вычислений на проектах MDPN и P196 — мы уже вплотную приблизились к отметке в 6.0% от всех чисел 23-значного диапазона и 600 миллионам итераций для числа 196 соответственно.

• • •
9 февраля 2022 · ESLP
Эксперимент «Equal Sums of Like Powers» (завершение)

Эксперимент закончен! Сегодня ночью в 2:48 универсальная программа наконец-то нашла минимальное решение для диофантова уравнения 4.1.3! Поиск занял 204 часа и 48 минут! Все выводы по эксперименту я добавил к статье «Равные суммы одинаковых степеней». Желаю приятного чтения!

Есть кое-что ещё, что я хотел бы здесь добавить. В рамках этого эксперимента было найдено некоторое количество минимальных примитивных решений для многих диофантовых уравнений вида p.1.n, где степень уравнения p варьировалась от 2 до 11, а количество коэффициентов правой части — от 2-8 до 35.

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

Также я выполнил небольшое исследование вопроса. И насколько мне удалось выяснить, все проекты, которые занимались распределёнными вычислениями с целью поиска решений диофантовых уравнений, в настоящее время прекратили (закончили) вычисления. Я уверен, что кто-то (отдельные исследователи) ещё продолжает поиск. Но учитывая текущую сложность, им будет очень тяжело добиться результатов в одиночку.

К чему я веду? Помните, как в самой первой записи этой серии я сказал о «безумном» плане? Так вот. Полагаю, что было бы замечательно продолжить поиск решений. И я не исключаю, что это можно было бы сделать на базе проекта iLWN. Тем более, что работа в направлении распределённых вычислений для MDPN уже начата.

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

• • •
7 февраля 2022 · MDPN
Проверены 5.0% всех 23-значных чисел

На 361-й день с начала поиска среди 23-значных чисел проект преодолел отметку в 5.0% от всех кандидатов, которые необходимо проверить в этом диапазоне! Над его проверкой сейчас трудятся 12 ядер двух процессоров Intel Core i5-10400. Эффективность отсева чисел Лишрел понемногу растёт и поэтому скорость поиска постепенно увеличивается.

Суммарное процессорное время, затраченное на проверку 5.010% диапазона, составило 380,736,757 секунд (105,760 часов или 4,406.7 дня). Проверено 55,288,404,752,640 чисел, из которых 52,992,885,039,828 (~95.85%) оказались числами Лишрел. Сохранено в базе данных 19,254,087,329 отложенных палиндромов (шаги от 50 до 289). Размер БД (отдельно для 23-значных чисел) достиг 54.8 GiB.

Среди 23-значных чисел на данный момент найдено 13 наименьших отложенных палиндромов: 9 из них пока считаются кандидатами (шаги 237, 241, 242, 243, 245, 248, 262, 288 и 289), а 4 являются достоверно наименьшими (шаги 246, 247, 286 и 287). Наиболее длинный известный результирующий палиндром в этом диапазоне содержит 142 знака, вот его первые 20 цифр: 66343434455441881783.

Таким образом, проверка 23-значного диапазона длится уже почти целый год (до полного года не хватает всего четырёх дней)! За каждый прошедший день было проверено в среднем примерно по 153.15 миллиарда кандидатов (или 0.01388% от всех кандидатов в диапазоне). Средняя суммарная скорость проверки чисел составила 1.77 миллиона кандидатов в секунду.

• • •
3 февраля 2022 · ESLP
Эксперимент «Equal Sums of Like Powers» (продолжение)

Эксперимент длится уже более 3 суток, универсальная программа преодолела значение 320K для старшего коэффициента уравнения 4.1.3. За это время я дописал специализированный алгоритм для этого вида уравнения и почти закончил работу над обновлённой статьёй (осталось лишь добавить итоговые результаты).

Мне очень хочется прервать эксперимент, так как скорость значительно упала и упадёт ещё сильнее. И прочитав следующий абзац, Вам станет понятно моё желание. Сейчас программа проверяет примерно 34 тысячи старших коэффициентов в сутки. Но всё же я не буду прерывать её работу и дождусь завершения вычислений.

Сегодня я запустил на втором ПК (с точно таким же ЦПУ) версию программы со специализированным для уравнения 4.1.3 алгоритмом. И был слегка шокирован результатом. Минимальное решение для уравнения 4.1.3 было найдено ей всего за 2 минуты и 28 секунд! Похоже, что разница в скорости с универсальной программой составит тысячи раз!

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

• • •
3 февраля 2022
Самые первые буквы!

Всем привет! Ура, это наконец-то свершилось! Это самая первая запись дневника, переведённая на английский язык! И пока все остальные (старые) записи всё ещё не переведены, начиная с этого момента, я буду обновлять как английскую, так и русскую страницы каждый раз при добавлении нового поста. Так что, по крайней мере, эти непереведённые записи перестанут накапливаться. И время от времени я буду переводить старые посты.

Так что, ещё раз привет и добро пожаловать в блог!

• • •
31 января 2022 · ESLP
Эксперимент «Equal Sums of Like Powers» (продолжение)

Итак, программа доработана, код проверен. Всё готово к началу эксперимента. В нём будут участвовать две версии программы: универсальная, отличающаяся от выложенной в загрузках только поддержкой 128-битной арифметики, многопоточностью и простой оптимизацией набора значений для старшего коэффициента, исключающей для уравнений вида 4.1.3 и 4.1.4 из перебора все чётные и кратные пяти значения. Также будет вторая версия, в которой я реализовал все известные мне математические способы сокращения проверяемых вариантов.

Едва начавшись, поиск решения уравнения 5.1.4 сразу завершился! Первое минимальное решение было найдено универсальной программой через 0.1 секунды. Однако в течение следующих двух часов работы, второе решение так и не было найдено.

Поэтому ровно в 14:00 по местному времени программа начала поиск решения для уравнения 4.1.3. Через 1 минуту старший коэффициент достиг значения 18,889, через две минуты – 23,917, через 5 – 32,183, а через 15 минут – 46,293. Ещё через 3 минуты и 40 секунд программа преодолела 64-битный барьер.

К концу первого часа работы программа достигла значения 73,327, а через два часа – 92,193. Пока трудно сказать, сколько времени займут вычисления до нахождения первого минимального решения (422,481), но скорость очень быстро снижается.

Программа выполняется в 12 потоков на ПК с 6-ядерным процессором Intel Core i5-10400, работающим на частоте 4.0 GHz. Здесь лежит журнал работы (текстовый файл, 508 байт) универсальной программы со всеми временными точками.

• • •
29 января 2022 · ESLP
Эксперимент «Equal Sums of Like Powers» (продолжение)

Наигравшись с получившейся программой, мне удалось найти много разных решений для уравнений вида 2.1.2+, 3.1.3+, 4.1.5+, 5.1.6+, 6.1.9+ и некоторых других. Я решил начать работу над той самой статьёй, в которой хотел рассказать о том, как была шаг за шагом написана моя программа.

Но в ходе работы над материалом мне не давала покоя мысль о ненайденных решениях для уравнения 6.1.6, 6.1.5, а также идея возможного опровержения новой гипотезы Ландера — Паркина — Селфриджа. Пожалуй, это прозвучит безумно, но что, если эта гипотеза тоже неверна? И, например, существует решение для уравнения 5.1.3 или 6.1.4, её опровергающее?

Да, это было бы потрясающе! Но, полагаю, что сделать это весьма и весьма непросто. Поэтому я подумал, что неплохо было бы для начала повторить поиск решения уравнений 5.1.4 и 4.1.3 на современном оборудовании. Ведь любопытно же, как много времени это займёт сейчас, в 2022 году? Думаю, Вы уже догадались, что произошло дальше...

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

А для эксперимента мне потребуется существенно доработать программу: нужна 128-битная арифметика, а также многопоточность. Плюс ещё есть ряд математических «оптимизаций» — они, как и оптимизации программные, уменьшают количество проверяемых вариантов решений, но с помощью чисто математических методов.

• • •
28 января 2022 · ESLP
Эксперимент «Equal Sums of Like Powers»

Сегодня я хочу рассказать об идее, возникшей у меня около недели назад. Эта запись дневника будет состоять из 3 отдельных частей, написанных в течение нескольких дней. Пожалуй, именно эта идея стала последней каплей, побудившей меня изменить (вернуть) формат блога. И я решил не постить каждую запись задним числом, а просто объединить их. Итак, поехали!

Запись №1. Слышали ли Вы когда-нибудь о диофантовых уравнениях? Уверен на 100%, что да! Возможно, этот термин Вам не знаком, но сами уравнения Вы встречали в жизни много раз! Наверное, самый простой пример — это Пифагоровы тройки (ссылка на страницу в Википедии):

z2 = x2 + y2

Есть и более сложные уравнения, с бо́льшим количеством слагаемых, иногда с обеих сторон, с разными значениями степеней. Но главная их особенность в том, что решение, то есть числа, удовлетворяющие равенству, обязательно должны быть целыми! И оказывается, что искать такие наборы чисел одновременно сложно и интересно!

Несмотря на то, что в моём списке задач просто океан дел, я не смог удержаться от того, чтобы не попробовать что-нибудь найти!!! Меня так захватила эта мысль, что у меня даже появился слегка безумный план... Но давайте обо всём по порядку.

Запись №2. Я взял и написал очень простую программу, перебирающую все варианты чисел для уравнения вида 2.1.2 (которое указано выше; цифры здесь обозначают степень, количество слагаемых слева и справа). Буквально в течение пары секунд программа выдала несколько сотен первых решений. Но, внимательно их изучив, я понял, что решений слишком много.

Оказывается, что решения бывают примитивные, то есть такие, которые не могут быть получены из других решений каким-либо способом (например, умножением всех коэффициентов на одно и то же число), и не примитивные, в которых числа не являются взаимно простыми (то есть такими, которые нельзя все одновременно поделить на какое-либо число большее 1).

Программа была немного доработана и теперь решений стало в разы меньше. За несколько минут работы программа смогла найти около 50 минимальных примитивных решений для 2.1.2. Я решил попробовать другие виды. Уравнения 3-й степени дались тяжелее, но по несколько первых решений мне найти удалось. А вот уравнения 4-й и 5-й степени оказались программе не по силам.

Невелика беда, подумал я. И потратил ещё часа 3 на оптимизацию перебора... Теперь уравнения 2-й и 3-й степени совсем перестали быть сложными (программа смогла выдать тысячи примитивных решений за несколько секунд), уравнения 4.1.5 и 5.1.6 были сложноватыми, 4.1.4 и 5.1.5 довольно сложными, а вот 4.1.3, так же, как и 5.1.4 оказались слишком сложны. Точнее для 5.1.4 первое решение найти удалось, но второе никак не находилось.

Где-то в процессе оптимизации я подумал, что процесс, когда я шаг за шагом делал программу быстрее, сам по себе интересен. И у меня родилась идея: написать об этом небольшую статью (к этому я ещё вернусь). Но самое интересное выяснилось при попытке найти решения для диофантовых уравнений шестой степени.

Запись №3. Пытаясь найти решения для уравнения 6.1.7, я понял, что это сложно. А для уравнений 6.1.6 и 6.1.5 вообще нет известных решений! Понимаете? То есть никто до сих пор не смог их найти! Ну ничего себе, подумал я. Вот, оказывается, насколько это непросто!

А дальше я узнал, что в 1769 году Леонард Эйлер выдвинул гипотезу, обобщающую Великую теорему Ферма (я не буду тут подробно рассказывать о них, Вы можете пройти по ссылкам и прочитать сами, если Вам интересно).

Так вот. Эта гипотеза утверждает, что для любого натурального числа n > 2 никакую n-ю степень натурального числа нельзя представить в виде суммы (n – 1) n-х степеней других натуральных чисел. Это значит, что, согласно гипотезе, для уравнений 4.1.3, 5.1.4, 6.1.5, 7.1.6 и других не существует решений в натуральных числах! Вот это поворот!

И знаете что? Это неправда! Ну то есть, гипотеза оказалась неверна. В 1966 году трое американских учёных, используя суперкомпьютер, с помощью перебора смогли найти решение уравнения 5.1.4, которое и опровергло гипотезу Эйлера! А в 1988 году было найдено решение для уравнения вида 4.1.3!

Внимательный читатель, наверное, уже задаётся вопросом: а что с другими степенями? А ничего! Для 6-й степени и степеней выше до сих пор не найден ни один пример, который бы опровергал эту гипотезу! Кстати говоря, те трое учёных взамен опровергнутой выдвинули свою гипотезу, которая так и называется: гипотеза Ландера — Паркина — Селфриджа.

• • •
28 января 2022
Блог, дневник проекта и статьи

Я долгое время ничего не писал (не считая нескольких записей, перенесённых в блог со страницы событий). И как мне кажется причина этого в том, что формат нового блога, который, как я думал, будет лучше, оказался для меня совсем неудобен. И поэтому я решил вернуть всё, как было раньше.

Блог снова будет Дневником проекта, где я буду периодически публиковать короткие посты обо всём, то есть о чём угодно. А статьи будут находится на отдельной странице (ссылка на неё расположена наверху, сразу под заголовком). Раздел «Интересные факты» будет полностью упразднён, вся интересная информация теперь будет на домашних страницах соответствующих проектов, а более объёмные тексты — среди прочих статей.

• • •
14 декабря 2021 · MDPN
Новый мировой рекорд среди наиболее отложенных палиндромов: 293 итерации!

Сегодня очень необычный и очень знаменательный день! 2 года, 6 месяцев и 12 дней (всего 926 дней) назад стартовал проект MDPN. В течение этого времени программа проверяла число за числом в поисках новых отложенных палиндромов. Иногда это был один компьютер, временами — несколько. Были в работе и перерывы длиной в несколько месяцев.

И вот, наконец, спустя два с половиной года вычислений, мной установлен новый мировой рекорд среди наиболее отложенных палиндромов! Найденному сегодня числу 1,000,206,827,388,999,999,095,750, состоящему из 25 знаков, потребовалось 293 итерации, чтобы стать 132-значным палиндромом 88022661552988847333 (указаны первые 20 цифр).

Начиная этот проект, я полагал, что найти новый рекорд будет легче, особенно с учётом того, насколько продвинулась вычислительная техника с 2010 года, когда был установлен предшествующий рекорд (261 итерация). Но оказалось, что с ростом длины числа поиск не только становится медленнее, но и плотность самих отложенных палиндромов стремительно снижается!

Это был долгий, но это очень интересный путь. Чтобы найти этот рекорд понадобилось прибегнуть к некоторым хитростям, таким как обратный вывод. Я обязательно подробно опишу этот метод позднее в отдельной статье. А сейчас лишь коротко опишу события, предшествующие обнаружению рекорда.

Вечером, проверяя числа в начале 25-значного диапазона, программа обнаружила отложенный палиндром 1,000,000,000,005,083,294,994,790, которому потребовалось 292 операции RAA, чтобы стать палиндромом. И само по себе это число уже было рекордом!

Однако важнее было то, что результирующий 132-значный палиндром встретился впервые. А это значит, что его было необходимо подвергнуть анализу с помощью метода обратного вывода, чтобы обнаружить родственные отложенные палиндромы, которые, возможно, разрешались бы за большее число итераций.

Это число было найдено в 21:36 по местному времени и было сразу мной замечено, так как в этот момент я находился за рабочим компьютером. Я немедленно запустил процесс анализа, который через 1 час и 15 минут углубился в дерево вывода на 16 шагов, чего было вполне достаточно, чтобы утверждать, что с высокой вероятностью были выведены все наиболее отложенные палиндромы соответствующего потока. И в 22:51 я сделал запись в журнале об обнаружении нового отложенного палиндрома, которому требуется 293 итерации.

В процессе обратного вывода также были обнаружены родственные отложенные палиндромы для шагов 290 и 291, неизвестные ранее. Сейчас все 4 числа являются кандидатами, так как перед ними имеется большое количество непроверенных чисел в диапазонах 23- 24- и 25-значных чисел.

Должен отметить, что в 2019 году, на момент начала проекта MDPN, мне было известно лишь о 19-значном рекорде, требующем 261 шаг. Однако Rob van Nobelen установил новый мировой рекорд ещё 26 апреля того же года, найдя отложенный палиндром, которому требуется 288 шагов. Я узнал об этом лишь в конце августа, спустя почти три месяца после начала проекта.

Узнав об этом, надо признаться, я расстроился. И не только потому, что новый рекорд уже был найден. А потому, что по моим расчётам, учитывая ту скорость, с которой я тогда двигался, и то, как далеко я был на тот момент от этого рекорда, мне требовалось 7 лет для того, чтобы добраться до той же точки, где уже находился Rob van Nobelen.

Тем не менее, я не остановился. И стал думать о том, как мне ускориться. И как теперь видно, у меня это получилось. За 2 с половиной года мне удалось не только «догнать», но и преодолеть отметку в 4.0% проверенных кандидатов в диапазоне 23-значных чисел, а также полностью проверить все числа во всех предшествующих диапазонах!

И теперь мне интересно, где расположено то число, которое станет следующим мировым рекордом среди наиболее отложенных палиндромов? И поэтому поиск продолжается! А его экспоненциально растущая сложность заставляет искать более эффективные методы и пути улучшения алгоритмов!

• • •
18 октября 2021 · H/W
Апгрейд: самый слабый компьютер проекта получил новый процессор и не только!

Как Вы, быть может, уже знаете, я принимаю пожертвования в помощь проекту iLWN. И за прошедший год собралась небольшая сумма. И так как проект остро нуждается в вычислительных мощностях, особенно в связи со стартом нового проекта P196, я решил потратить эти деньги на апгрейд самого слабого компьютера, который используется исключительно под задачи проекта.

Увы, сумма собранных средств не такая большая, чтобы на неё можно было купить мощный компьютер. Однако, добавив к ней ещё почти столько же, этих денег хватило на новую бюджетную материнскую плату на базе чипсета Intel H510, 6-ядерный процессор Intel Core i5-10400 и недорогую, но качественную систему охлаждения для него. 16 гигабайт оперативной памяти DDR4 остались от апгрейда основного ПК, а корпус, блок питания и SSD остались старыми.

Как и ранее, на проекте 3 компьютера трудятся в режиме 24/7, и ещё один участвует в вычислениях по несколько часов в рабочие дни. Но теперь они в сумме располагают 19 полноценными ядрами CPU, способными выполнять в общей сложности 35 потоков одновременно, и 80 гигабайтами оперативной памяти!

Это определённо хорошая новость! Благодаря апгрейду поиск отложенных палиндромов в проекте MDPN станет быстрее. В рамках проекта P196 можно будет параллельно проверять больше чисел (помимо первых трёх базовых чисел Лишрел)!

• • •
6 октября 2021 · H/W
Объём оперативной памяти на моём основном ПК увеличен c 24 до 40 Гб!

В конце 2020 года я делал апгрейд своего основного компьютера: старенький 4-ядерный Intel Core i7-2600K с 16 Гб DDR3 я обновил до 6-ядерного Intel Core i5-10400F с 24 Гб DDR4. Но этого объёма памяти было недостаточно для одновременной комфортной работы (мои задачи компиляции в Visual Studio требуют иногда более 10 Гб оперативной памяти) и эффективной работы программы проекта MDPN в фоновом режиме. Остановка и перезапуск программы — это было не слишком удобно.

И вот, наконец, я увеличил объём оперативной памяти до 40 Гб! Теперь программа использует набор отсева размером 26.3 GiB (ранее 12.5 GiB), что сделает поиск более быстрым и эффективным (особенно во второй половине диапазона 23-значных чисел). И при этом у меня ещё остаётся более 10 Гб свободной памяти для других нужд.

• • •
29 сентября 2021 · MDPN
Преодолён очередной рубеж: проверены 2.0% всех 23-значных чисел

230 дней прошло с начала поиска отложенных палиндромов в диапазоне 23-значных чисел. И вот, наконец, мы добрались до отметки в 2.0% от всех чисел, которые необходимо проверить в этом диапазоне. К моему сожалению, над его проверкой работают значительно меньшие мощности, чем на диапазонах 21- и 22-значных чисел, так как часть имеющихся в распоряжении вычислительных ядер была отдана другим проектам, а ещё часть оборудования более мне недоступна.

Вот немного статистики. Суммарное процессорное время, затраченное на проверку 2.001% диапазона, составило 198,954,235 секунд (55,265 часов или 2,302.7 дня). Проверено 22,085,469,658,880 чисел, из которых 20,922,749,693,781 (~94.74%) оказалось числом Лишрел. Сохранено в базе данных 7,917,196,749 отложенных палиндромов (шаги от 50 до 289), общий размер БД (отдельно для 23-значных чисел) достиг 22.0 GiB.

Среди наиболее отложенных палиндромов (шаги 286, 287, 288 и 289) мной найдено 9 канонических чисел: 5 для шага 286, 2 для шага 287 и ещё 2 для шага 289. Среди последних двух чисел (текущий мировой рекорд), число 10,037,000,102,799,917,799,950 было найдено 20 сентября 2021 года моей программой, и является на сегодняшний день наименьшим известным отложенным палиндромом для шага 289 (второе число — 10,037,000,230,509,917,799,950). Все 9 отложенных палиндромов дают в результате один и тот же палиндром длиной 142 знака. Вот первые 20 цифр этого палиндрома: 66343434455441881783.

Мне также известно о существовании ещё двух наиболее отложенных палиндромов: числа 12,000,700,000,025,339,936,491, найденного Rob van Nobelen 26 апреля 2019 года (даёт палиндром за 288 шагов). А также числа 10,809,000,707,896,963,790,960, найденного Антоном Стефановым 11 января 2021 года (даёт палиндром за 289 шагов).

Update Указанное выше 23-значное число оказалось не наименьшим отложенным палиндромом, разрешающимся за 289 шагов. Новый (наименьший) кандидат для этого шага был обнаружен 14 октября.

• • •
20 сентября 2021 · MDPN
Установлен новый локальный рекорд: 289 шагов!

Сегодня проектом MDPN был установлен новый локальный рекорд: 289 шагов! Я решил написать об этом не только в новостях проекта, но и в блоге потому, что найденное сегодня 23-значное число 10,037,000,102,799,917,799,950, хоть и считается пока кандидатом, является наименьшим известным на сегодняшний день числом и новым мировым рекордом среди наиболее отложенных палиндромов.

Ранее в этом году, а именно 4 января, Антон Стефанов сообщил о том, что нашёл число, разрешающееся за 289 шагов: 13,968,441,660,506,503,386,020, которое стало новым мировым рекордом среди наиболее отложенных палиндромов. Однако, из собственных соображений (сам автор называет такую запись «возвратной формой»), он не привёл число к каноническому виду (т. е. наименьшему числу, которое может быть получено путём изменения пар цифр при условии неизменности их сумм). В каноническом же виде этот отложенный палиндром будет записан как 10,037,000,230,509,917,799,950. И это число больше найденного мной сегодня.

Позднее, 11 января, Антон сообщил о нахождении им второго числа, дающего палиндром за 289 шагов: 16,909,736,969,870,700,090,800. И снова вид числа оказался не каноническим (в этот раз, видимо, автор указал наибольшее известное ему число, дающее палиндром за 289 шагов). Его каноническая форма будет такой: 10,809,000,707,896,963,790,960. Таким образом, данное число является третьим известным на сегодняшний день каноническим отложенным палиндромом в диапазоне 23-значных чисел для шага 289.

• • •
19 сентября 2021 · P196
Старт проекта P196 («196 Palindrome Quest»)

С началом осени у меня появилось больше свободного времени, которое я могу уделять проекту. И в конце августа я уже начал улучшение веб-сайта. А теперь пришло время и для нового проекта.

Основным объектом исследования в проекте MDPN являются отложенные палиндромы, а числа Лишрел остаются без должного внимания. Поэтому сегодня я официально объявляю о старте проекта с кодовым названием P196, которое расшифровывается как «196 Palindrome Quest».

Наиболее подходящим переводом названия проекта на русский будет «Поиск палиндрома 196». Главная его цель состоит в том, чтобы проверить, сможет ли десятичное число 196, а также другие базовые числа Лишрел когда-либо стать палиндромами в результате многократного выполнения над ним операции Перевернуть-И-Сложить. Подробнее о целях и том, почему я решил начать этот проект, я попытался рассказать в этой статье.

Здесь лишь добавлю, что в рамках нового проекта все числа до 12-значных включительно были предварительно проверены с глубиной 23,000 итерации. В результате чего был получен список из 786,640 первых базовых чисел Лишрел. И для первых 173 из них было дополнительно выполнено по одному миллиону итераций. Текстовый файл со списком чисел можно скачать здесь (.zip архив, 1.86 Мб).

• • •
13 июня 2021 · MDPN
Проверены 1.0% всех 23-значных чисел

Почти ровно 4 месяца назад (а если точнее, то 122 дня) был начат поиск отложенных палиндромов среди 23-значных чисел. И вот сегодня программа преодолела первый значимый рубеж: 1.0% от всех чисел диапазона, которые необходимо проверить. В самом начале диапазона скорость всегда самая низкая, поэтому первые проценты даются тяжелее всего.

Тем не менее, за эти месяцы было проверено 11,048,371,399,680 кандидатов. 10,249,606,869,196 (92.77%) из них оказались числами Лишрел и лишь 798,764,530,484 (7.23%) — отложенными палиндромами. Всего на проверку 1.001% чисел диапазона затрачено 99,227,460 секунд процессорного времени (27,563 часа или 1,148.5 дня). В базе данных сохранён 3,894,297,231 отложенный палиндром (шаги от 50 до 258), а размер БД достиг 10.8 GiB.

Средняя суммарная скорость проверки чисел составила 1.05 миллиона кандидатов в секунду, а среднее количество задействованных потоков процессора 9.4 (с учётом непродолжительных перерывов в работе). Весь этот объём вычислений был совершён практически одним компьютером — моим основным рабочим ПК на базе 6-ядерного процессора Intel Core i5-10400F.

Среди проверенных чисел были найдены достоверно наименьшие отложенные палиндромы, разрешающиеся за 246 и 247 итераций.

• • •
2 июня 2021 · MDPN
Проект MDPN празднует годовщину! Сегодня ему исполнилось ровно 2 года!

Сегодня исполняется ровно 2 года со дня старта проекта MDPN! За эти два года было проверено очень много чисел: более 175 триллионов кандидатов в отложенные палиндромы и числа Лишрел из всех диапазонов, начиная от единицы и до первых 23-значных чисел. Все найденные за это время числа сохранены в базу данных, размер которой на сегодня уже превысил 242 GiB.

Наиболее отложенный палиндром, найденный моей программой, — это число 1,186,060,307,891,929,990, которое превращается в палиндром за 261 шаг (впервые было обнаружено ещё в 2005 году). Текущий мировой рекорд среди отложенных палиндромов: 289 шагов (его обнаружил Антон Стефанов 4 января 2021 года). Другими словами, за 2 года поисков мне пока не удалось установить новый мировой рекорд.

Тем не менее за это время я смог найти достоверно наименьшие числа для шагов 238, 239, 240, 246, 247, 249 и 250. Отложенные палиндромы для этих шагов впервые были обнаружены другими исследователями, однако найденные ими числа не являлись наименьшими возможными. Также я стал первым, кто подсчитал точное полное количество чисел Лишрел в каждом диапазоне до 22-значных чисел включительно.

Впереди ещё очень много работы. И речь не только об объёме вычислений. Я планирую обновить и расширить этот веб-сайт, добавить на его страницы (по крайней мере для проекта MDPN) всю ту информацию, что накопилась, но по разным причинам ещё не опубликована. В планах начать ещё несколько проектов, связанных с палиндромами и числами Лишрел. А также перевести, наконец, сайт на английский язык! Всё это потребует значительных усилий и времени. Поэтому я буду крайне признателен за любую помощь, оказанную проекту!

• • •
30 марта 2021 · MDPN
Текущий статус поиска отложенных палиндромов

До окончания проверки диапазона 22-значных чисел остаётся менее 2 дней (проверено уже 98.833% всех чисел). А в диапазоне 23-значных чисел пока проверено лишь 0.469% чисел, но среди них уже найдены 2 новых отложенных палиндрома! Точнее, пока это ещё кандидаты, но с учётом того, что перед ними остаётся слегка больше 1% непроверенных 22-значных чисел, вероятность, что эти 23-значные числа являются наименьшими отложенными палиндромами, очень высока. Суммарный размер базы данных уже достиг 236.8 GiB!

• • •
28 декабря 2020 · H/W
Полный апгрейд основного компьютера

Приближается Новый год, мой самый любимый праздник в году. И в связи с возросшими потребностями проекта я, наконец-то, решил сделать полный апгрейд своего основного ПК, заменив мой старенький Intel Core i7-2600K на более современный, мощный и прохладный Intel Core i5-10400F, одновременно увеличив объём оперативной памяти с 16 Гб DDR3 до 24 Гб DDR4. Теперь вместо 4 ядер у него будет 6, более быстрых и мощных!

Итого, теперь в парке проекта трудится 5 машин, обладающих в сумме 22 процессорными ядрами и 88 Гб оперативной памяти:

С наступающим Новым 2021 годом!!!

• • •

Это место — не самое начало блога. И есть ещё много других записей! Но я перенесу их сюда немного позже. Вот здесь находится старый дневник проекта MDPN, который ранее использовался одновременно и в качестве новостной ленты, и в качестве блога.