Пентадекатлон мечты

[Dmitriy40]

Именно такой метод привёл к нахождению пентадекатлона в 827 раз меньше первого найденного.
Вот кто помнит во сколько раз больше паттернов было для этого проверено? Больше или меньше 827 раз?
И кстати как это количество паттернов считать, ведь там был и поиск с одним (и двумя и более) пустыми местами, на которые квадраты небольших простых не размещались, т.е. под один проверяемый паттерн подпадали десятки и сотни (а может и тысячи, не помню) полных паттернов ...

[Yadryara]

Вроде бы в каждом комплекте было по 46080 паттернов. И проверили весьма немало этих комплектов. Компиляция одного комплекта с Асма занимала немало времени — часы.

[EUgeneUS]

Yadryara в сообщении #1704080 писал(а):

Вроде бы в каждом комплекте было по 46080 паттернов.

А $46080$ - количество шаблонов с минимально возможными простыми в квадрате, с учетом перестановок квадратов простых и "правых"-"левых" шаблонов.

Yadryara в сообщении #1704080 писал(а):

И проверили весьма немало этих комплектов.

Насколько помню, минимальный известный пентадекатлон содержит простое в квадрате из начала второй сотни (то ли 101, то ли 103).

-- 01.10.2025, 18:44 --

VAL

Плохо знаю PARI\GP, поэтому прошу разъяснить на примере программы из этого поста:

1. Шаблон, который используется в этой программе, сколько содержит простых в квадрате? (на скольких местах размещаются простые в квадрате, не считая обязательных?)
2. Пусть на $n$ местах. Тогда вариантов шаблона будет $n!$ - просто за счёт перестановок простых в квадрате.. Сколько из этих вариантов использует эта программа?

А то у меня может быть завышенные ожидания....

[Dmitriy40]

101:

? x=80215613469168729088982885848674841; for(i=0,14, print("+",i,":",numdiv(x+i)," ",factor(x+i)))
+0:12   [23, 2; 9649, 1; 15715236849165389302315212121, 1]
+1:12   [2, 1; 101, 2; 3931752449228934863688995483221, 1]
+2:12   [3, 1; 29, 2; 31793742952504450689252035611841, 1]
+3:12   [2, 2; 200396929, 1; 100070911602104352967633159, 1]
+4:12   [5, 1; 19, 2; 44440783085412038276444812104529, 1]
+5:12   [2, 1; 3, 2; 4456422970509373838276826991593047, 1]
+6:12   [7, 1; 31, 2; 11924425965388543048756189363561, 1]
+7:12   [2, 5; 2506737920911522784030715182771089, 1]
+8:12   [3, 1; 11, 2; 220979651430216884542652578095523, 1]
+9:12   [2, 1; 5, 2; 1604312269383374581779657716973497, 1]
+10:12  [13, 2; 224814373570921, 1; 2111291163772264499, 1]
+11:12  [2, 2; 3, 1; 6684634455764060757415240487389571, 1]
+12:12  [17, 2; 10073981, 1; 27552431989290592962811817, 1]
+13:12  [2, 1; 7, 2; 818526668052742133561049855598723, 1]
+14:12  [3, 2; 5, 1; 1782569188203749535310730796637219, 1]

[EUgeneUS]

Dmitriy40
Ага.
При этом, из необязательных простых используются:
$17^2, 19^2, 29^2, 31^2, 101^2$.
Необязательные простые начинаются с $17$.

То есть уже довольно много вариантов перебрали, пока добрались.

[Dmitriy40]

EUgeneUS
$23^2$ на +0 пропустили.

-- 01.10.2025, 18:59 --

EUgeneUS в сообщении #1704086 писал(а):

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

На всех 21-м, их можно увидеть в массиве
M = [3698, 3971, 12, 49, 50, 5043, 362024, 529, 18, 4805, 28, 4107, 242, 841, 480, 289, 4418, 63, 4, 845, 320226]
В нём 21 число и все содержат квадрат простого.

EUgeneUS в сообщении #1704086 писал(а):

Сколько из этих вариантов использует эта программа?

Один конкретный. Указанный выше в M[].
На каждый вариант размещения нужна своя программа. Поменяется не только массив М[], но и часть других, T[] точно, u[] и nu[] не уверен, но ещё и константы в длинном if.

[Yadryara]

Кстати, слово "шаблон" мне гораздо меньше нравится сразу по нескольким причинам. Например, на шоблу смахивает.

Паттерн — нравится, но только конечно с ударением на первый слог.

EUgeneUS в сообщении #1704086 писал(а):

А $46080$ - количество шаблонов с минимально возможными простыми в квадрате,

Нет, это стандартное количество паттернов далеко не только для минимальной расстановки КМК37-11.

EUgeneUS в сообщении #1704086 писал(а):

Насколько помню, минимальный известный пентадекатлон содержит простое в квадрате из начала второй сотни (то ли 101, то ли 103).

101. Мы почему-то не догадались что надо всего лишь заменить 37 на 101

[EUgeneUS]

Dmitriy40 в сообщении #1704088 писал(а):

В нём 21 число и все содержат квадрат простого.

Все не интересуют, интересуют только "необязательные".
Для цепочки длиной $21$ - обязательные до $21$, то есть до $19$ включительно. А необязательные, соответственно, больше $21$, то есть с $23$ и выше.
Из Вашего сообщения я понял, как это можно получить. Спасибо!

-- 01.10.2025, 19:04 --

Yadryara в сообщении #1704098 писал(а):

Мы почему-то не догадались что надо всего лишь заменить 37 на 101

Поди, догадайся
Перебирали с нарастанием LCM.

[VAL]

EUgeneUS в сообщении #1704086 писал(а):

Плохо знаю PARI\GP, поэтому прошу разъяснить на примере программы из этого поста
:
1. Шаблон, который используется в этой программе, сколько содержит простых в квадрате? (на скольких местах размещаются простые в квадрате, не считая обязательных?)
2. Пусть на $n$ местах. Тогда вариантов шаблона будет $n!$ - просто за счёт перестановок простых в квадрате.. Сколько из этих вариантов использует эта программа?

Как уже отметил Дмитрий, каждый элемент шаблона делится на квадрат простого.
9 из них больше 19 и их можно произвольно менять местами.
Данная программа использует 1 указанный вариант. Но я одновременно запускал более полусотни аналогичных программ на 4-х компах.

-- 01 окт 2025, 19:09 --

Dmitriy40 в сообщении #1704097 писал(а):

На каждый вариант размещения нужна своя программа. Поменяется не только массив М[], но и часть других, T[] точно, u[] и nu[] не уверен, но ещё и константы в длинном if.

Константы в длинном if меняются, u[] и n[u] - нет. И конечно же поменяется p1.

-- 01 окт 2025, 19:14 --

Поколдовал над таблицей для 19-ки по 24 делителя для ускорителей. Удалось впихнуть 9 позиций, где оставшийся множитель обязан быть простым, и всего 3 позиции, где нужно $pq$.
Во избежание недоразумений, большие квадраты расставлять не стал, только клеточки покрасил в квадратный цвет.

[Dmitriy40]

EUgeneUS в сообщении #1704099 писал(а):

Перебирали с нарастанием LCM.

Не только: можно просто не указывать $37^2$, LCM стал бы меньше, шаг перебора меньше, работа дольше, зато нашлись бы любые простые в квадрате. Когда-нибудь.
И кстати по моему этот пентадекатлон был найден именно такой проверкой, не с подставленными $101^2$, а вообще без квадрата на этом месте. Потому что название паттерна этого пентадекатлона S9-45-304251 и ноль в номере позиции указывает насколько помню именно на пустую позицию, без размещённого квадрата. Это так называемая "проверка по строкам", проверяются сразу любые квадраты простых, без их расстановки.
Я проверял и все другие варианты, в том числе с меньшим количеством расставленных простых (вплоть до нулевого), но ничего интересного найти не успел.

[EUgeneUS]

Dmitriy40 в сообщении #1704097 писал(а):

Один конкретный. Указанный выше в M[].

Итого, шаблон содержит $9$ необязательных простых (от $23$ до $59$), прибитых на конкретные места.

Это даёт $9! = 362880$ шаблонов с такого же качества и с таким же LCM. Более трети миллиона.
Далее, скорее всего это не единственная расстановка обязательных простых, которая даёт такой же набор неизвестных $p, pq, pqr, ....$
Это ещё умножает $362880$ на количество таких вариантов.
Далее - набор необязательных простых в квадрате можно увеличить, скажем до $73$ включительно, это несколько ухудшит LCM, но даст ещё кучу "хороших" шаблонов.

Итого: лучше искать по этим миллионам шаблонов по низам, чем улетать в заоблачные дали на одном шаблоне.

Цитата:

Ах, не солгали предчувствия мне,
Да, мне глаза не солгали.
Лебедем белым скользя по волне,
Плавно на встречу идет пароход.

-- 01.10.2025, 19:22 --

VAL в сообщении #1704100 писал(а):

Данная программа использует 1 указанный вариант. Но я одновременно запускал более полусотни аналогичных программ на 4-х компах.

полусотня VS треть миллиона (и только на перестановках минимальных необязательных простых).

[VAL]

EUgeneUS в сообщении #1704102 писал(а):

полусотня VS треть миллиона (и только на перестановках минимальных необязательных простых)

Ну извините, миллиона логических ядер на моих 4-х компах не нашлось

[Yadryara]

Dmitriy40 в сообщении #1704101 писал(а):

Потому что название паттерна этого пентадекатлона S9-45-304251 и ноль в номере позиции указывает насколько помню именно на пустую позицию, без размещённого квадрата.

Конечно. И комплекты называли по номеру выброшенного подквадратного простого из минимального набора: 17-1, 19-2, ..., 37-6. Шестёрка заменена нулём — он нашёлся в 37-м комплекте.

[EUgeneUS]

VAL в сообщении #1704105 писал(а):

миллиона логических ядер на моих 4-х компах не нашлось

ИМХО, нужен не миллион ядер. А следующее:
1. "Хорошие" шаблоны, пока без ориентации на ускорители Дмитрия. То есть минимизируем количество $p$, потом $pq$ и т.д. Все варианты (с точностью до перестановок необязательных простых в квадрате) с одинаково "хорошим" набором $p, pq, pqr ...$

2. Программа на PARI/GP:
на вход подаётся:
а) набор "хороших шаблонов" из пункта 1.
б) набор небольших простых, которые она будет использовать в квадратах необязательных простых.

обработка: перед тем как, повышать градус размерность $N$ - она должна проверять все варианты шаблонов.

и нужно логирование с возможностью перезапуска с прерванного места по данным логов.

Тогда есть (почти) уверенность, что имеющимися мощностями можно будет улучшить цепочки с $k=24n$ на 1-2 (кроме $k=72$, там с ускорителями Дмитрия искалось, и нужно отдельно разбираться, какие шансы будут на увеличение количества шаблонов).

-- 01.10.2025, 20:04 --

EUgeneUS в сообщении #1704109 писал(а):

пока без ориентации на ускорители Дмитрия.

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

И чем больше шаблонов, с уже расставленными необязательными простыми в квадратах, тем с этим больше проблем.
На десятки тысяч - компилируется часы. А на единицы миллионов сколько будет?

Если мы улучшаем известную цепочку, то стратегия понятна:
1. Скомпилировали пачку из десятков тысяч.
2. Считаем до известной цепочки.
3. Если не нашли (или хотим ещё улучшить) - компилируем ещё пачку из десятков тысяч.

А если известной цепочки нет, то как будет оптимально?

[Dmitriy40]

EUgeneUS в сообщении #1704102 писал(а):

Далее - набор необязательных простых в квадрате можно увеличить, скажем до $73$ включительно, это несколько ухудшит LCM, но даст ещё кучу "хороших" шаблонов.

Включение одного дополнительного простого увеличивает количество паттернов в 10 раз (1 старый набор простых плюс 9 наборов с заменой одного из 9-ти простых на новое). Добавление второго нового простого увеличивает количество ещё в 9 раз (предыдущее новое простое на это не меняем). Третье ещё в 8 раз. Четвёртое (73) ещё в 7 раз. Итого 9!*10*9*8*7=1828915200 штук. Почти 2млрд.
Даже если проверка по каждому будет занимать 10 секунд, (а меньше нет смысла - больше потратится на вычисление служебных массивов по паттерну, не отказываться же от скорости перебора), это порядка 2млн простых можно перебрать, то это 18.3млрд секунд или 580 лет в одном потоке. Ну пусть даже в 5 раз меньше, сотня лет в одном потоке. Всего лишь на один круг проверки всех паттернов ...
Пусть даже мы найдём пару сотен потоков, но одним кругом ведь дело не завершится, надо хотя бы сотни кругов, а может и миллионы ...
Так что эта идея увеличения количества паттернов хорошая, но стоит вовремя остановиться.

Если отказаться от пары методов ускорения проверки и не вычислять служебные массивы (T[] и условия в if), то такую программу (на PARI) сварганить несложно. Тогда можно уменьшить количество перебираемых простых в круге (до тысяч, меньше снова нет смысла, вычисление расстановки станет дольше её проверки) и сократить время на круг до дней-недель.

А теперь вопрос: а сколько кругов надо сделать чтобы найти решение? Про М48n21 не знаю, а вот для M12n15 прикинуть можно:
первый поиск проверил не менее 66387422053662391209161093722597723545 / 440538835723387181869888800 = 1.5е11 кандидатов для каждого из 46080 паттерна;
второй (или какой он там был по счёту) поиск проверил 80215613469168729088982885848674841 / 321796081609486619335200 = 2.45e11 кандидатов для каждого из 46080 паттерна;
итого было проверено не менее 46080*(1.5e11+2.45e11)=1.8e16 кандидатов (на самом деле в несколько раз больше, были и другие поиски).
В соседней теме обсуждается ускорение этой (и аналогичной M48n20) программы на PARI, лучшая скорость 0.3млн кандидатов в секунду, без методов ускорения будет максимум 0.1млн/с. Перебрать 1e16 кандидатов со скоростью 1e5/c надо 1e11с или 3000 лет в один поток.
Да, скорее всего первое решение встретится значительно раньше конца всего перебора, но вопрос насколько раньше.

-- 01.10.2025, 20:53 --

EUgeneUS
Поясню почему невыгодно перебирать по одному кандидату в каждом паттерне: чтобы получить проверяемое число надо выбрать расстановку простых в квадрате, это цикл forperm, потом для выбранной расстановки вычислить КТО для минимум 10 аргументов (1 посчитанный ранее для всех остальных мест кроме этих 9-ти) и только потом можно выбирать следующее простое и проверять не даёт ли оно решение. ispseudoprime для составных чисел вроде бы быстрее chinese (КТО) и уж точно даже частичная проверка по небольшим модулям (что простые не попадают на занятые места) во много раз быстрее chinese. Потому выгоднее медленно вычислить КТО, а потом быстро линейно (kan=base+i*m) пройтись по сотням-тысячам чисел проверяя каждое из них.

Если хотите, могу сделать такую программу, на базе хоть 3-х, хоть 9-ти (ожидаю что он будет выгоднее) цифирного паттерна M48n21, но только одного, не десятков тысяч штук конечно, т.е. основные простые перераставлять не будет, только дополнительные. Даже самому интересно какова будет её скорость, насколько меньше той что без перебора простых в квадратах ...