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

[Yadryara]

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

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

Я надеюсь, вы не предлагаете мне погрузиться в пучину 300 страниц этой темы?

Предлагаю. Причём на полном серьёзе. Я неоднократно перечитывал некоторые места.

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

Ну вот и давайте посмотрим буквально первые 6 страниц. Пока в контексте последнего разговора.

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

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

Но работа ведется в основном с 35-40 значными числами.

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

По одному числу в каждом наборе кратно 49, 121, 169, 289, 361, 529, 841, 961, 1369. При этом в наборах нет третьего числа, кратного 7, и вторых чисел, кратных 11 и 13 (последние теоретически могли бы присутствовать, но их допущение резко снижает эмпирическую вероятность успеха, поскольку в интересующем нас диапазоне произведения двух простых встречаются гораздо чаще, чем простые).

Таким образом, в проверяемых наборах заведомо не будет чисел, делящихся на квадраты простых чисел, больших 37. Разумеется, в интересующих нас цепочках таковые могут встречаться. Но в целях ускорения поиска выгоднее искать цепочки без них.

Подчёркивание моё.

То бишь первое свободное простое — 41. А диапазон 1e35 — 1e40. Окей, подставил в программу эти числа:

10^       1e6         2       4       8      16      4/2

  35   148726        83     252     312     217      3.0
  36   148719        81     246     313     219      3.0
  37   148732        79     242     311     224      3.1
  38   148722        77     238     308     224      3.1
  39   148708        76     234     306     226      3.1
  40   148726        74     231     304     228      3.1

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

Поэтому достаточно, чтобы частное было произведением двух простых. Эмпирическая вероятность этого события (для 40-значных чисел) примерно 0.24.

Да, примерно так и есть. В 4-м столбце частотности 0.231 — 0.252.

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

вероятность, что число из интересующего нас диапазона окажется произведением двух простых в 4 с лишним раза выше.

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

Так что, как обычно, без обид — на слово не верим.

[wrest]

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

Более шедевральный паттерн, дающий почти втрое больше цепочек на 1e5 итерациях - [50,363,4,169,18,245]:

Продолжаю тут с генератором. Вот выдался такой паттерн, для D(24,6): [833, 338, 75, 32, 2299, 18]
Он даёт 79 попаданий на первых 10^5 цепочках. Рекорд, однако.
Но если с двойным шагом, то попаданий 125 (на 10^5 удвоенных шагах).
С двойным шагом получается так:

СИСТЕМА #1 | n0=2014230969373 | m=4660507051200 | log10m=12.67
tau_R = [4, 4, 4, 4, 4, 4]
Проверено: 100001 | Полных: 125 | Плотность: 1.250 e-3
Распределение τ(n+i) по позициям:
  pos 0 (τ_R=4): =  31.6% | >  50.6% | <  17.8%
  pos 1 (τ_R=4): =  35.6% | >  47.1% | <  17.3%
  pos 2 (τ_R=4): =  30.5% | >  53.0% | <  16.5%
  pos 3 (τ_R=4): =  37.1% | >  46.7% | <  16.1%
  pos 4 (τ_R=4): =  34.2% | >  47.5% | <  18.2%
  pos 5 (τ_R=4): =  25.0% | >  59.4% | <  15.6%
Расчёт ожидаемой вероятности полной цепочки:
  Ожидаемая (prod pos): 1.0884 e-3
  Эмпирическая (full/trials): 1.2500 e-3

Так вот, повторю вопрос про "запрещённые остатки". Как мне по сгенерированному паттерну понять, что надо скорректировать n0 и m?
То есть, если по паттерну сразу видно, что надо ходить только по чётным i в n=n0+i*m, то надо сделать m=2*m, а если по нечётным, то сделать n0=n0+m;m=2*m Так же, да?
Я это делаю с расчётом на то, что в функцию проверки цепочек буду передавать только n0;m и паттерн.
Я думал, что можно и паттерн не передавать, достаточно n0 для его вычисления, но вроде недостаточно, могут быть какие-то пограничные случаи. А функция проверки должна быть универсальная.
А, и ещё вопрос: а как тут в этом паттерне повысить вероятность последней позиции с 25% до 35%? Это можно?

[Yadryara]

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

tau_R = [4, 4, 4, 4, 4, 4]

Ну вот видите, какая скукота. Потому что числа n маленькие и обгон ещё не состоялся: вы обычно берёте koli не больше 1e5, так что n всегда меньше 1е18, а частные ещё меньше.

Ну а если взять i больше 1e20, то все частные, видимо перевалят за 1e30, обгон состоится и тогда снова будет скукота, ибо по вашему критерию будет: tau_R = [8, 8, 8, 8, 8, 8].

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

А, и ещё вопрос: а как тут в этом паттерне повысить вероятность последней позиции с 25% до 35%? Это можно?

Это надо смотреть, но тут обычно по Ломоносову — вероятность для другого места упадёт.

[wrest]

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

Ну вот видите, какая скукота. Потому что числа n маленькие и обгон ещё не состоялся: вы обычно берёте koli не больше 1e5, так что n всегда меньше 1е18, а частные ещё меньше.

Генератор частично учитывает, а потом будет учитывать более точно вероятности двух/трёх/четырёх простых в зависимости от бюджета (десятичных разрядов) на НОК. Для D(6,48) бюджет побольше, там больше попадаются в паттерне t_R=8

-- 26.04.2026, 21:53 --

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

Это надо смотреть, но тут обычно по Ломоносову — вероятность для другого места упадёт.

Вот одинарный шаг:

========================================
СИСТЕМА #1 | n0=2014230969373 | m=2330253525600 | log10M=12.37
tau_R = [4, 4, 4, 4, 4, 4]
Проверено: 100001 | Полных: 79 | Плотность: 7.900 e-4
Распределение τ(n+i) по позициям:
  pos 0 (τ_R=4): =  32.1% | >  49.8% | <  18.0%
  pos 1 (τ_R=4): =  35.9% | >  46.5% | <  17.6%
  pos 2 (τ_R=4): =  30.5% | >  52.6% | <  16.9%
  pos 3 (τ_R=4): =  18.8% | >  64.7% | <  16.5%
  pos 4 (τ_R=4): =  34.7% | >  46.7% | <  18.7%
  pos 5 (τ_R=4): =  25.2% | >  59.0% | <  15.8%
Расчёт ожидаемой вероятности полной цепочки:
  Ожидаемая (prod pos): 5.7765 e-4
  Эмпирическая (full/trials): 7.8999 e-4

а вот двойной:

СИСТЕМА #1 | n0=2014230969373 | m=4660507051200 | log10M=12.67
tau_R = [4, 4, 4, 4, 4, 4]
Проверено: 100001 | Полных: 125 | Плотность: 1.250 e-3
Распределение τ(n+i) по позициям:
  pos 0 (τ_R=4): =  31.6% | >  50.6% | <  17.8%
  pos 1 (τ_R=4): =  35.6% | >  47.1% | <  17.3%
  pos 2 (τ_R=4): =  30.5% | >  53.0% | <  16.5%
  pos 3 (τ_R=4): =  37.1% | >  46.7% | <  16.1%
  pos 4 (τ_R=4): =  34.2% | >  47.5% | <  18.2%
  pos 5 (τ_R=4): =  25.0% | >  59.4% | <  15.6%
Расчёт ожидаемой вероятности полной цепочки:
  Ожидаемая (prod pos): 1.0884 e-3
  Эмпирическая (full/trials): 1.2500 e-3

Изменилась (заметно) только вероятность (частота) pos 3

Собсно что мы тут видим. Увеличение НОК-а на 0,3 десятичных порядка увеличило вероятность/плотность полных цепочек вдвое.

[Dmitriy40]

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

То есть, если по паттерну сразу видно, что надо ходить только по чётным i в n=n0+i*m, то надо сделать m=2*m, а если по нечётным, то сделать n0=n0+m;m=2*m Так же, да?

Да, можно и так.
Или в самом деле "ходить только по (не)чётным i", forstep никто не отменил.

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

Я это делаю с расчётом на то, что в функцию проверки цепочек буду передавать только n0;m и паттерн.
Я думал, что можно и паттерн не передавать, достаточно n0 для его вычисления, но вроде недостаточно, могут быть какие-то пограничные случаи. А функция проверки должна быть универсальная.

А зачем n0,m вместе с паттерном если они по нему и рассчитываются? Одного паттерна достаточно.

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

А, и ещё вопрос: а как тут в этом паттерне повысить вероятность последней позиции с 25% до 35%? Это можно?

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

? v=[833, 338, 75, 32, 2299, 18]; pp=chinese(vector(6,i,Mod(-i+1,v[i])))
%1 = Mod(2014230969373, 2330253525600)
? st=0*10^5; len=1e5; q=vector(6); s=vector(7); for(k=st,st+len-1, n=lift(pp)+pp.mod*(6*k+0); q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++); print(q); print(s); print(vecprod(q)/len^5*1.)
[31138, 34643, 29997, 36388, 33648, 1226]
[13234, 32818, 32699, 16653, 4117, 477, 2]
4.8572666180851084603575552000000000000
? st=0*10^5; len=1e5; q=vector(6); s=vector(7); for(k=st,st+len-1, n=lift(pp)+pp.mod*(6*k+2); q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++); print(q); print(s); print(vecprod(q)/len^5*1.)
[31163, 35137, 29767, 36697, 33495, 36163]
[8261, 25915, 33170, 22438, 8377, 1689, 150]
144.88185611127481608415402650000000000
? st=0*10^5; len=1e5; q=vector(6); s=vector(7); for(k=st,st+len-1, n=lift(pp)+pp.mod*(6*k+4); q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++); print(q); print(s); print(vecprod(q)/len^5*1.)
[31135, 34728, 29613, 36636, 33680, 36244]
[8352, 25831, 33313, 22442, 8217, 1685, 160]
143.19481886217504263674368000000000000

[wrest]

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

Да, можно и так.
Или в самом деле "ходить только по (не)чётным i", forstep никто не отменил.

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

-- 26.04.2026, 23:23 --

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

А зачем n0,m вместе с паттерном если они по нему и рассчитываются? Одного паттерна достаточно.

Ну так вот недостаточно же? Раз надо НОК посчитать а потом на два умножить. А если ходить надо по нечётным то ещё прибавить n0+m
Ну и из n0 тоже непонятно что за числа брались по местам. Туда же ещё случайные залетают.
Поэтому оказывается что паттерн (в смысле набора параметров для поиска цепочки) определяется как миниму n0,m ну и собсно рабором модулей. Плюс ещё желаем кол чеством делителей, но это и так ясно что надо передавать в функцию поиска.

[Dmitriy40]

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

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

Ну и разделите, в чём проблема. По каким i ходить - это фактически вопрос фильтрации, можно же и остальные простые учесть и получить огромный список допустимых остатков i по большому модулю (произведения учитываемых простых). И шаг перебора нужен только функции поиска цепочек, всем остальным удобнее работать с "натуральными" n0 и m, т.е. получаемыми прямо из паттерна (через chinese).

Кроме того, компьютеру всё равно, а человеку удобнее ограничивать перебор по круглым цифрам, хоть праймориалов, хоть степеней 10 (что конечно удобнее). И сколько именно i (которые реально будут проверяться кучей этапов) попадёт в интервал перебора - вообще говоря внутреннее дело функции поиска цепочек, снаружи с ней можно общаться на языке n0 и m (или прайморилов или даже степеней 10). А она уже пусть перебирает как может быстрее, хоть с шагом 2, хоть с шагом 6, хоть с шагом 19652 (ну если сможет конечно). Не фиксированное количество уже предварительно пофильтрованных i, а вообще без привязки к i, просто например от 33e45 до 39e45 - а сколько там будет i и с каким шагом - да плевать, функция сама выберет.

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

Ну так вот недостаточно же? Раз надо НОК посчитать а потом на два умножить. А если ходить надо по нечётным то ещё прибавить n0+m

Достаточно: и эта вся информация есть в паттерне. Мы же сами её оттуда вытаскиваем, просто усложнённо, но именно из паттерна, не откуда-то ещё.
И менять n0 и m не обязательно! Можно менять i. А i вообще могут присутствовать только внутри функции поиска цепочек, а снаружи с ней общаться на языке "перебери от 123e43 до 321e43" - и пусть сама морочится про i и шаг. Это же универсальнее модификаций n0 и m и указаний про i. Ведь мы же можем и не знать с каким шагом функция поиска цепочек умеет перебирать кандидатов (и нам и не надо этого знать, незачем), да ещё и реализации функции могут быть разными и уметь перебирать с разными шагами (одна - только с 1х, другая получше уже с 2х, третья ещё лучше с шагом 3х или 6х, четвёртая с шагом 210 и проверкой 48 из них, и так далее). Вы же хотите универсальности - тогда это не про n0, m, i, величину шага, это всё внутренние сущности функции поиска цепочек. Мы их используем потому что так код проще и лень писать универсально (хотя я для каких-то паттернов писал именно что универсально).

[wrest]

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

И да, получается (показываю с учётом модулей и 2 и 3):

Прекрасно! Тут ведь получается, что в вероятность растёт быстрее чем падает.
EUgeneUS ранее писал в том духе, что увеличение n на 2 порядка снижает вероятность в 2 раза. А тут вцходит, что мы увеличиваем НОК на 0.3 порядка и вероятность растёт почти вдвое. Профит налицо. Увеличение НОКа еще на попорядка (умножением на три) ещё увеличивает плотность. Поэтому наверное Yadryara делает шестикратные шаги.
И даже умножение НОКа на 30 (2*5*3) и на 210 (2*3*5*7) всё ещё выгодно.

-- 27.04.2026, 00:20 --

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

Достаточно: и эта вся информация есть в паттерне. Мы же сами её оттуда вытаскиваем, просто усложнённо, но именно из паттерна, не откуда-то ещё.

Это так пока вы вставляете "необязательные" простые подряд без пропусков. А если какое-то не вставили, оно же может само пролезть. Ну например пропустили 19, а оно пролезло само в разложение какого-нибудь n0+i. А... погодите. Если 19 нет в разложении m но есть в разложении n0+i тогда делаем вывод что оно не в паттерне, да?

А я там собрался не проверять по таблице все простые больше нижнего порога и меньшие верхнего, а проверять все не вставленные меньшие верхнего порога. То есть таблица может начинаться не так[59,61,67,...] а например так: [17,39,43,59,61,67,...]

[Dmitriy40]

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

Это так пока вы вставляете "необязательные" простые подряд без пропусков.

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

-- 27.04.2026, 00:49 --

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

[wrest]

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

И ради поиска редких цепочек (а лёгкие уже все нашли) скорость важнее универсальности.

Тут наверное вы правы, но я и не рассчитываю на рекорды, к счастью, что исключает конфликты на почве соревновательности. У меня и считать-то не на чем, нет настольного компа

[Yadryara]

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

Для D(6,48) бюджет побольше, там больше попадаются в паттерне t_R=8

Перепутали? Видимо, D(48,6). Потому что D(6,48) не бывает, бывает максимум D(6,5).

«Ровно шесть делителей - II»

А с 96-ю делителями ещё легче. Вот и сейчас у меня есть паттерны и кортежи, где t_R=8 на всех 13-ти местах.

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

Изменилась (заметно) только вероятность (частота) pos 3

Ну я понял: вы просто на более ранней стадии находитесь. Разбираетесь со второй фильтрацией.

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

Поэтому наверное Yadryara делает шестикратные шаги.

Рад что вы больше не жалуетесь на терминологию и жаргонизмы. То есть понятно, что шестикратный шаг, это просто шаг, который в 6 раз больше чем LCM (он же НОК)?

Вот увеличил интервал в 10 раз по вашему паттерну. Теперь koli = 1e6.

? {print;
v = [833, 338, 75, 32, 2299, 18]; bazmod = chinese(vector(6,i,Mod(-i+1,v[i])));

st = 0*10^5; koli = 1e6; q=vector(6); svalids=vector(7);

for(i=st,st+koli-1,

n = lift(bazmod) + bazmod.mod*(6*i + 0);

q+=(w=[numdiv(n+t)==24|t<-[0..5]]); svalids[vecsum(w)+1]++;

if(vecsum(w) >= 6, print(n, "   ", factor(n+5));
));
print;print(q); print(svalids); print(vecprod(q)/koli^5*1.)}

97886643827322973     [2, 1; 3, 5; 201412847381323, 1]
213401971598366173    [2, 1; 3, 5; 439098706992523, 1]
1992312852534354973   [2, 1; 3, 5; 4099409161593323, 1]
2379125616769852573   [2, 1; 3, 5; 4895320199114923, 1]
2836405247619494173   [2, 1; 3, 5; 5836224789340523, 1]
3222211342331932573   [2, 1; 3, 5; 6630064490394923, 1]
3351190874973892573   [2, 1; 3, 5; 6895454475254923, 1]
3383404299711786973   [2, 1; 3, 5; 6961737242205323, 1]
3427194423964862173   [2, 1; 3, 5; 7051840378528523, 1]
3434996112768570973   [2, 1; 3, 5; 7067893236149323, 1]
3526477205676575773   [2, 1; 3, 5; 7256125937606123, 1]
4588010217742502173   [2, 1; 3, 5; 9440350242268523, 1]
4599586917257682973   [2, 1; 3, 5; 9464170611641323, 1]
4880573547881582173   [2, 1; 3, 5; 10042332403048523, 1]
5031070641578932573   [2, 1; 3, 5; 10351997204894923, 1]
5764681056508324573   [2, 1; 3, 5; 11861483655366923, 1]
6220954017834906973   [2, 1; 3, 5; 12800316909125323, 1]
6278837515410810973   [2, 1; 3, 5; 12919418755989323, 1]
6471992230147794973   [2, 1; 3, 5; 13316856440633323, 1]
6837790768089431773   [2, 1; 3, 5; 14069528329402123, 1]
7152626661426196573   [2, 1; 3, 5; 14717338809518923, 1]
8045794195760471773   [2, 1; 3, 5; 16555132090042123, 1]
8181317080302316573   [2, 1; 3, 5; 16833985761938923, 1]
8365537603022150173   [2, 1; 3, 5; 17213040335436523, 1]
8677730988860884573   [2, 1; 3, 5; 17855413557326923, 1]
9044410362635198173   [2, 1; 3, 5; 18609897865504523, 1]
9658101270630162973   [2, 1; 3, 5; 19872636359321323, 1]
10426064283033950173  [2, 1; 3, 5; 21452807166736523, 1]
11955698623322404573  [2, 1; 3, 5; 24600202928646923, 1]
12656592278752372573  [2, 1; 3, 5; 26042370943934923, 1]
13186226281571894173  [2, 1; 3, 5; 27132152842740523, 1]
13886113267478802973  [2, 1; 3, 5; 28572249521561323, 1]

[300573, 336645, 287676, 353337, 325254, 11737]
[142078, 340056, 322991, 154097, 37029, 3717, 32]
39.264008417701264601090392665960000000
?

Как думаете, это случайно, что все 32 находки экзотические, с 3-кой именно в 5-й степени? Она там случайно нашлась или это вы обязали её туда встать?

[EUgeneUS]

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

EUgeneUS ранее писал в том духе, что увеличение n на 2 порядка снижает вероятность в 2 раза. А тут вцходит, что мы увеличиваем НОК на 0.3 порядка и вероятность растёт почти вдвое. Профит налицо.

Это говорилось в другом контексте.
Правило "увеличение n на 2 порядка снижает вероятность в 2 раза" применяется уже после фильтрации по запрещенным остаткам.

А вообще,
1. Проверка по запрещенным остаткам - мощная штука. Сильно снижает количество проверок.
2. Но чем больше простое, которое учитывается в фильтрации по запрещенным остаткам, тем меньше его вклад в фильтрацию (при одном запрещенном остатке на простое число, что всегда выполняется для: а) простых больше $3$ и б) цепочек длиной меньше 26, и в)для паттернов с простыми больше 5 в степени как минимум квадрат).
3. Поэтому шаг в виде удвоенного LCM даёт хороший выигрыш при нулевых затратах.
4. Что касается шестикратного шага, то
а) если запрещенных остатков по модулю 3 - один, то шестикратный шаг может и не дать выигрыша. Выигрыш будет "съеден" необоснованным ростом чисел в два раза.
Нужно именно исключать запрещенный остаток, а разрешенные обрабатывать оба.
б) если запрещенных остатков по модулю 3 - два, то шестикратный шаг даёт выигрыш "за бесплатно" в рамках заданного паттерна. Но тогда можно задать вопрос - о будет ли этот паттерн оптимальным?

[VAL]

Очередные (129-й и 130-й) шаги антирекорда:

49646841524311976899957398211781695856639493571800063694840
880815114275879132200843777433668865977681594317585975502840

[wrest]

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

Но тогда можно задать вопрос - о будет ли этот паттерн оптимальным?

Ага, а какие паттерны мы считаем "оптимальными"?

[EUgeneUS]

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

Ага, а какие паттерны мы считаем "оптимальными"?

Тут два альтернативных критерия:
1. Максимальная вероятность найти цепочку за одну проверку.
2. Максимальная вероятность найти цепочку за единицу времени.

-- 27.04.2026, 16:53 --

1. Оптимальность по первому критерию - это "функция" только свойств паттерна.
2. Конечно, более правильный, что ли, второй критерий. Но оптимальность по этому критерию - это "функция" не только свойств паттерна, но и программы поиска цепочек.