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

[Dmitriy40]

По моему Вы почему-то забыли что простых в квадратах можно взять и больше чем минимально необходимо и выбирать 17шт не из наименьших доступных 17шт, а скажем из 20шт, это увеличит количество вариантов паттернов с $17!$ в $C^{17}_{20}=1140$ раз. С увеличением lcm, да. Но вполне вероятно что как минимум некоторые из таких вариантов паттернов окажутся вполне подходящими. И это простой способ нарастить количество паттернов если не хватает количества перестановок простых в квадратах. Напомню что так были найдены пентадекатлоны D(12,15) на три порядка меньшие первых трёх по оптимальным паттернам.

[EUgeneUS]

Dmitriy40
Не то чтобы совсем забыл. Но пока решил не вдаваться в такие подробности.
Там есть куча нюансов.

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

Напомню что так были найдены пентадекатлоны D(12,15) на три порядка меньшие первых трёх по оптимальным паттернам.

Для D(12,15) оптимальных паттернов было 40000 с небольшим, насколько помню, что для вероятности (по порядку величины) найти цепочку за одну проверку в $10^{16}$ крайне мало, конечно.
Потому и получили большую вероятность найти цепочки с сильно меньшими числами, которая и сработала не один раз.

[wrest]

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

По моему Вы почему-то забыли что простых в квадратах можно взять и больше чем минимально необходимо и выбирать 17шт не из наименьших доступных 17шт, а скажем из 20шт, это увеличит количество вариантов паттернов с $17!$ в $C^{17}_{20}=1140$ раз. С увеличением lcm, да. Но вполне вероятно что как минимум некоторые из таких вариантов паттернов окажутся вполне подходящими.

Тама, кстати, если пропускать необязательные простые (то есть вставить скажем 23, 29, 37 но пропустить и не вставить 31), то на не вставленные простые будет иногда что-то делиться, и тогда таблицу простых для trial division, если этот этап есть в проверках, надо дополнять этими пропущенными простыми, так?

[EUgeneUS]

wrest в сообщении #1722899 писал(а):

Тама, кстати, если пропускать необязательные простые (то есть вставить скажем 23, 29, 37 но пропустить и не вставить 31), то на не вставленные простые будет иногда что-то делиться, и тогда таблицу простых для trial division, если этот этап есть в проверках, надо дополнять этими пропущенными простыми, так?

Если речь про "исключение запрещенных остатков", то запрещенные остатки формируют используемые в паттерне простые числа.

То есть в Вашем примере,
по модулю 31 не будет запрещенных остатков, а по модулям 23, 29, 37 - будут (скорее всего, по одному запрещенному остатку на каждое простое).

[wrest]

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

Если речь про "исключение запрещенных остатков", то запрещенные остатки формируют используемые в паттерне простые числа.

Я в эту терминологию не въехал ещё. Смотрите, у нас получилась какая-то цепочка последовательных чисел путем вычисления её первого числа по формуле n=n0+k*m для какого-то k. Числа в ней n, n+1, .. , n+L-1 где L количество чисел в цепочке, гарантированно делятся на вндрённые в паттерн числа. Но ранее, когда я ускорял проверятор цепочек, мне было сказано, что ни на какие простые меньшие 59, кроме тех что в паттерне, числа в цепочке гарантированно не делятся. Типа - так сделан паттерн. Но почему так - я тогда не спрашивал, просто принял как факт. И первым этапом, факторизацию пробным делением, начинал проверку делением на 59.

[EUgeneUS]

wrest в сообщении #1722902 писал(а):

Числа в ней n, n+1, .. , n+L-1 гарантированно делятся на внедрённые в паттерн числа.

Да, это гарантирует КТО.

wrest в сообщении #1722902 писал(а):

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

lcm - это именно lcm, наименьшее общее кратное (Least Common Multiple) - для чисел, "внедренных в паттерн".
А если мы в паттерн не "внедряем" число 31, то почему решили, что какое-то число в цепочке на него не разделится?
В данном случае 31 - это обычное простое число, которое может войти множителем в какое-нибудь место с ожидаемым $pq$, например.

Или с другой стороны:
Если $m$ в формуле $n=n_0+k \cdot m$ не кратно $31$, то $n=n_0+k \cdot m$, вообще говоря, может иметь любой остаток по модулю $31$.

Но опять же, есть нюанс. Если в паттерне есть места с ожидаемым $p$. Для валидной цепочки туда 31 попасть может ровно один раз не более одного раза. А дальше, если туда попало 31, то там оказалось составное число. И это даст запрещенные остатки по модулю 31.
Но опять же, это ничем не отличается от (относительно) малых простых, которые не используются в паттерне.

[wrest]

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

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

Да, значит я всё правильно понял. Видимо, в том паттерне были вставлены все простые числа, меньшие 59.
Ща гляну в архив... Да, так и есть. Все простые до 53 включительно (про 59 я неправильно запомнил), 2 и 3 в 5 степени, остальные квадраты. Это паттерн, которым нашлась D(48,21), я на нём тренировался. НОК около 10^41

[Dmitriy40]

wrest в сообщении #1722906 писал(а):

Видимо, в том паттерне были вставлены все простые числа, меньшие 59.

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

[EUgeneUS]

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

1. Если знать до куда считать, то есть ограничивать не диапазон итераторов, а числа в цепочках, то замена в степени (например, в квадрате) необязательного простого на несколько большее простое не снижает вероятность нахождения цепочки за одну проверку. И даже немного увеличивает (очень немного - можно пренебречь).
Другое дело, что при таком расчете количество итераторов при ограниченном диапазоне чисел падает. И может
упасть так сильно, что "вылезут" накладные расходы на подготовку паттерна.

Кстати, я пробовал улучшить $D(24,19)$ таким методом на 1.5 - 2 порядка.

1. Идея была такая: если числа меньше на 2 порядка, то и вероятность больше в два раза. А количество проверок наберем за счет "размножения" паттернов путем подстановки большого количества необязательных простых в квадратах.
2. Считал по всем оптимальным для этой цепочки паттернам батчам.
3. С подстановкой в необязательных простых в квадратах до $150$, насколько помню. (Может быть до $100$)
4. Считал с помощью pcoul - у него есть нужные ключи, чтобы организовать такой расчет.

Улучшение не нашлось, видимо, количества проверок всё таки не хватило, чтобы набрать большую вероятность...

-- 22.04.2026, 07:51 --

План был такой: если бы идея сработала и цепочка нашлась бы за время заметно меньшее (например, в два раза), чем при "обычном" поиске $D(24,19)$, то поискать этим методом $D(24,20)$

[VAL]

Очередная порция приближений к неуловимой D(192,15):

15137496152559371960091618755340016507923270867803176962040
683095042757042596275431431252543958944657598252134335080440
664788393547308665977821903477870285257968799900406280194040

[Ende]

Выяснение отношений отделено по назначению, как и было обещано.

[EUgeneUS]

wrest

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

статья Ivo Düntsch and Roger B. Eggleton, Equidivisible consecutive integers, 1989.
задача ММ77

И добавлю ссылки на OEIS
A119479 - эта последовательность застопорилась надолго, если не навсегда. Уперлась в доказательство существования $D(24,31)$, что в текущем моменте нереально.
A006558 - цепочки рекордной длины (для больших цепочек - оценки). Но пока не обновлена - нет оценок для a22 и a23
A292580 - собственно последовательность упёрлась в доказательство минимальности $T(6,13)$ ($D(12,13)$), но есть файл (текущая версия) с доказанными минимальными цепочками и с оценками для $k \le 200$. Тоже не обновлен по последним достижениям. В разделе "LINKS" есть ссылки на полезные статьи, как на Ivo Düntsch and Roger B. Eggleton, так и на пару статей уважаемого VAL

-- 22.04.2026, 21:19 --

На всякий случай, обращаю внимание, что в нотации $T(\cdot, \cdot)$ на первой позиции в скобках указывается не $k$, а $k/2$, этим она отличается от нотации $D(\cdot, \cdot)$.

-- 22.04.2026, 21:41 --

VAL
Кстати, давно хотел спросить про гипотезу Эрдёша:

Цитата:

В частности, Эрдёшем еще в начале 50-х годов прошлого века высказана гипотеза (на сегодняшний день не поменявшая своего статуса), что для любого натурального $n$ найдется $k$ такое, что $d(k) \ge n$.

А это утверждение доказано в предположении о справедливости гипотезы Диксона или гипотезы Шинцеля?
Или это тривиально?

[wrest]

Продолжаю с генератором паттернов.
От D(24,6) перешёл на D(48,6)
Оказалось что оенератор не такой уж и универсальный, пришлось править.
Но вроде допилено до нормального состояния.
Дал вот эти 4 паттерна (первые два числа n0 и m, затем модули)
[1081619296944347678, 4423167467262704160, 2299, 1127, 160, 4901, 243, 8959]
[3000266040417814749, 10102296067204941600, 931, 575, 3509, 96, 5239,10693]
[15159920457771284349, 27420517896699127200, 847, 575, 4901, 96, 8959, 13357]
[437267946345566270, 451343619108439200, 2299, 3887, 32, 8381, 243, 775]
Выход годных -- 20..30 цепочек на сто тысяч. Считаю -- неплохо.
Почему-то не очень удаётся подбирать так чтобы осталось найти только pq (t_R=4), нередко проскакивает и pqr (t_R=8).

Видимо пришла пора подумать о тайне "запрещённых остатков".
Вижу что цепочки находятся в основном или для чётных или для нечётных i в $n=n0+i\cdot m$

[Dmitriy40]

wrest
Только хотел показать про остатки, но вдруг наткнулся что используемый паттерн [2299, 3887, 32, 8381, 243, 775] - некорректен! Потому что раз на месте +2 стоит 2 в степени, то на местах +0 и +4 должно стоять 2. И раз на месте +4 стоит 3 в степени, то на месте +1 должно быть 3. И раз на месте +5 стоит 5 в степени, то и на месте +0 должно быть 5. Ничего этого в паттерне не наблюдаю.
Оно бы конечно и плевать, но затрудняет анализ: например после деления 437267946345566270/2299=190199193712730 (при i=0) для места +0 получаем не p, а 2*5*p. И столь же странные частные будем получить при любом i. И для мест +1 и +4 тоже.

Зачем в паттерн попали числа 19, 23, 29, 31 все в первой степени - не вполне ясно. Если предположить чтобы все pqrs превратить в pqr, то этого не получилось, ведь там не учли 2,3,5 в первых степенях, которые pqr превращают в p или pq. В итоге вместо всех 6 мест pqr получились места p, pq, pqr, pqr, pq, pqr. Вы точно хотели этого?

Правильным будет паттерн: [22990, 11661, 32, 8381, 486, 775] - с тем же lcm(v) и n0.

Посмотрим какие числа для факторизации (и какой они имеют остаток по модулю 6) он даёт по местам для первых i=0...15:

? v1= [22990, 11661, 32, 8381, 486, 775];
? for(i=0,15, n=437267946345566270+451343619108439200*i; print(i,": ", [((n+t)/v1[t+1]) | t<-[0..5]]); )
0: [19019919371273, 37498323158011, 13664623323298946, 52173719883733, 899728284661659, 564216704962021]
1: [38652090711353, 76203718845211, 27769111420437671, 106026913906933, 1828418858958859, 1146595568327749]
2: [58284262051433, 114909114532411, 41873599517576396, 159880107930133, 2757109433256059, 1728974431693477]
3: [77916433391513, 153614510219611, 55978087614715121, 213733301953333, 3685800007553259, 2311353295059205]
4: [97548604731593, 192319905906811, 70082575711853846, 267586495976533, 4614490581850459, 2893732158424933]
5: [117180776071673, 231025301594011, 84187063808992571, 321439689999733, 5543181156147659, 3476111021790661]
6: [136812947411753, 269730697281211, 98291551906131296, 375292884022933, 6471871730444859, 4058489885156389]
7: [156445118751833, 308436092968411, 112396040003270021, 429146078046133, 7400562304742059, 4640868748522117]
8: [176077290091913, 347141488655611, 126500528100408746, 482999272069333, 8329252879039259, 5223247611887845]
9: [195709461431993, 385846884342811, 140605016197547471, 536852466092533, 9257943453336459, 5805626475253573]
10: [215341632772073, 424552280030011, 154709504294686196, 590705660115733, 10186634027633659, 6388005338619301]
11: [234973804112153, 463257675717211, 168813992391824921, 644558854138933, 11115324601930859, 6970384201985029]
12: [254605975452233, 501963071404411, 182918480488963646, 698412048162133, 12044015176228059, 7552763065350757]
13: [274238146792313, 540668467091611, 197022968586102371, 752265242185333, 12972705750525259, 8135141928716485]
14: [293870318132393, 579373862778811, 211127456683241096, 806118436208533, 13901396324822459, 8717520792082213]
15: [313502489472473, 618079258466011, 225231944780379821, 859971630231733, 14830086899119659, 9299899655447941]
? for(i=0,15, n=437267946345566270+451343619108439200*i; print(i,": ", [((n+t)/v1[t+1])%6 | t<-[0..5]]); )
0: [5, 1, 2, 1, 3, 1]
1: [5, 1, 5, 1, 1, 1]
2: [5, 1, 2, 1, 5, 1]
3: [5, 1, 5, 1, 3, 1]
4: [5, 1, 2, 1, 1, 1]
5: [5, 1, 5, 1, 5, 1]
6: [5, 1, 2, 1, 3, 1]
7: [5, 1, 5, 1, 1, 1]
8: [5, 1, 2, 1, 5, 1]
9: [5, 1, 5, 1, 3, 1]
10: [5, 1, 2, 1, 1, 1]
11: [5, 1, 5, 1, 5, 1]
12: [5, 1, 2, 1, 3, 1]
13: [5, 1, 5, 1, 1, 1]
14: [5, 1, 2, 1, 5, 1]
15: [5, 1, 5, 1, 3, 1]

Видим что каждое второе имеет остаток 2 по модулю 6 на месте +2, где стоит 2^5. Т.е. каждая вторая цепочка повышает степень с 2^5 до 2^6 и более. 2^6 нам не подходит, значит половина от половины (т.е. 1/4) цепочек (и значений i) можно выбрасывать. Вторая половина от половины повышает степень 2^5 на две и более. Половина от них (т.е. 1/8 всех i) повышает степень с 2^5 до 2^7 и в общем подходит, а вторая половина (тоже 1/8 всех i) повышает более чем до 2^7 и либо не подходит (ждать повышения до 2^11 или 2^15 или 2^23 не будем) либо придётся ещё досчитать сколько точнее i не подходит по месту +2.
Кроме того, по месту +4 видим каждую третью кратную 3 (имеет остаток 3 по модулю 6), значит имеющаяся там степень 3^5 тоже повышается. 2 раза из трёх (или 2/9 всех i) степень повышается на одну и нам не подходит, 1 раз из трёх (или 1/9) повышается на 2 (попало не 3, а 3^2=9) и более и может подойти. Подробнее можно посчитать если выше всё понятно.
wrest, досюда понятно?

[wrest]

Да блин с этим генератором.... Сплошной тришкин кафтан. Куда он, блин, двойки дел? Говорил ему - расставляй обязательные простые. Он расставлял. И потом между 50 и 60 версией забыл.

-- 23.04.2026, 00:52 --

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

Правильным будет паттерн: [22990, 11661, 32, 8381, 486, 775] - с тем же lcm(v) и n0.

Погодите, тут я как-то не понял. Если n0 и m не меняется, то получаем ровно те же цепочки.
Но только у меня для паттерна [2299, 3887, 32, 8381, 243, 775]получились
n0=1081619296944347678
m=4423167467262704160
А у вас для паттерна[22990, 11661, 32, 8381, 486, 775] получились
n0=437267946345566270
m=451343619108439200