Ну что Вы подсказываете
О, извиняюсь.
Чувствуется, что Вам эта задача тоже интересна.
Мне интересны задачи оптимизации программ (и алгоритмов), и приложение их к аппаратуре (SSE, AVX, GPU). Не только в этой теме, а и вообще.
А задача доказательства минимальности ... Я сделал несколько подходов, для разных цепочек, для некоторых даже доказал что нет минимальных некоторых видов (потому что перебрал их все), но все они упираются в огроменное время вычислений. Почему у Hugo считается значительно быстрее я не разбирался, думаю дело в алгоритме (что по каким остаткам проверять или разлагать), а не в его реализации.
Я произвёл сплошной перебор до 250 000 000 000! (это не факториал!) и не нашёл шестёрок особого вида, а значит нет и пентадекатлона.
Кто хочет, может продолжать.
Думаю кроме Макаровой никто не захочет: хоть Вы и не озвучили затраченное время на проверку этих 25e10 чисел, но его несложно прикинуть, а все могут взять калькулятор и посчитать сколько времени понадобится для доказательства минимальности 15-ки с такой скоростью перебора, которая пока что порядка 8e34. И вероятность что 15-ка есть до 1e22 (и думаю и до 1e27) скорее всего ничтожна.
И самое главное: Вы в программе перебираете числа с шагом 640 (из миллиона чисел от 625e6 до 626e6 лишь почти 50 тысяч чисел простые) и для каждого из них запускаете медленную numdiv. Но если потребовать отсутствия в цепочке высоких степеней большого (больше тысяч) простого, то тройку можно разместить в 15-ке лишь единственным (с точностью до зеркальности) способом - квадрат должен стоять на первом (или последнем) месте и никак иначе (в середине будет конечно ещё и второй квадрат тройки). Аналогично с квадратом пятёрки, он обязан быть только на 6-м месте (с точностью до зеркальности), в итоге на первом месте получается коэффициент 45 и никак иначе (либо он же только на последнем месте). Других вариантов для 15-ки не существует, если не привлекать степени выше первой для неизвестного простого в каждой позиции. Уже это в итоге даёт увеличение шага проверки центрального числа до двух вариантов (45 слева или справа на краю) для
чисел или каждые 1440 чисел. Уже это более чем вдвое быстрее перебора лишь по центральному простому. Плюс здесь вместо медленной numdiv на первом (или последнем) месте можно использовать гораздо более быструю isprime потому что там осталось найти лишь ровно одно простое в первой степени.
Одновременно с этим автоматически оказывается что и на местах 4, 6, 10 (когда 45 слева) тоже осталось найти лишь одно простое в первой степени и проверку тоже можно сделать быстрой isprime вместо медленной numduv. Причём на этих местах коэффициенты всегда ровно 12, 50, 18 соответственно, а значит шаг проверки можно ещё увеличить чтобы числа на этих местах гарантированно делились на вот эти коэффициенты, т.е. с 2880/2 до 14400/2=7200 или в 11 раз больше шага только по центральному простому.
Дальнейший учёт вариантов размещения простых 7, 11, 13 (а они все обязаны быть в цепочке, в степени 2 или 3 или 5 и/или ещё и в первой) даёт если не ошибаюсь 806 варианта размещения всех этих простых и величину шага проверки от 7207200 до 7236072072036007200 для разных вариантов. Понимаете, уже не по 650 чисел можно проверять за раз, а по миллионам или квадриллионам. И это всё ещё будет доказательством минимальности и полным перебором.
Есть правда одна тонкость. Вовсе не обязательно проверять все эти 806 вариантов, почти во всех них присутствуют неизвестные простые в квадрате, но такие простые не могут находится совсем уж в любом месте цепочки, их вообще допустимо лишь 24 варианта и практически все они нереализуемы потому что цепочек с двумя и более квадратами почти всегда просто не существует, либо вообще в целых, либо в простых. Т.е. эти 24 варианта дают не все возможные варианты сочетаний, а максимум несколько. И эти несколько вариантов в принципе вполне можно проверить отдельно, перебрать
простых на PARI конечно нереально, но вот на нормальном языке (C/C++, асм, может ещё что-то из новых) уже не выглядит неподъёмным. Я тут недавно прикидывал, вроде бы получается за пару суток проверить отсутствие решения для каждого из 24-х вариантов с квадратами, но для этого надо писать непростую программу на асме с AVX2 (С тут не помощник, про остальные вообще молчу), да и достигнется ли такая скорость заранее непонятно, это скорость лишь самого внутреннего цикла, а что там будет снаружи и насколько оно затормозит ещё большой вопрос.
И это я ещё не касался вопроса ускорения счёта использованием внешних программ (типа моих ускорителей).
И вот по всему этому полный перебор с шагом порядка тысячи (только по центральному простому) бесполезен, потратив несколько дней на написание прог выше (тех что на PARI, не касаясь даже других) можно потом за несколько минут догнать и перегнать полный перебор только по центральному простому. Без ухудшения плотности покрытия (все исключения проще проверить отдельно), т.е. без возможных пропусков решений.
-- 12.10.2022, 22:01 --grisЧто 25e10, что триллион - это всё ни о чём. Надо то до 8e34 (если не обнаружится сильно-сильно меньшая 15-ка, что ну очень сомнительно). И везение тут не особо поможет, если 15-ки нет до 1e26, то хоть с везением, хоть без него, но её там не найти. А если случайно и наткнуться на достаточно большую (вдруг и правда повезёт и она есть где-то немногим выше 1e26), то не доказать что она минимальная.
Потому я видел энтузиазм Макаровой, но кроме улыбки он ничего более не вызывает.
Если честно, просто жалко смотреть как люди (и их компы) занимаются бесполезной работой, можно же гораздо эффективнее считать (даже без моих программ, не в них дело). Но что-то объяснять Макаровой лично у меня категорически не хватает терпения, потому пусть считает что и как хочет.
grisЕсли будет желание разобраться, то объяснить почему те же тройка и пятёрка должны быть в строго определённых местах (и потому можно перебирать с гораздо большим шагом чем 32p) несложно. Всего лишь аккуратно выписать все возможные варианты (их типа 9+9+9=27 для тройки и 15+15+15+5=50 для пятёрки) и чётко указать почему почти все они недопустимы. Несколько муторно и объёмно, но ничего сложного для понимания.