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

[wrest]

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

Ну так вот. У вас есть программа которая ищет D(48,21). Есть программа Владимира с первой страницы, которая ищет D(12,15).

Вы примерно понимаете как работает ваша. А понятно ли вам, что для того интервала, где ведётся поиск D(12,15), найти 11 простых и 4 полупростых гораздо вероятнее чем 12 простых и 3 полупростых?

"Моя" программа это просто ускоренный вариант алгоритма Dmitriy40 в переложении на язык pari/gp
Там очень ясные цели: есть последовательность (арифметическая прогрессия, заданная формулой $n=n0+i\cdot m$) из большого (я за ориентир беру миллион, т.е. $i=0 \dots 10^6$ ) количества цепочек, их надо проверить на эквиделимость. Заранее известно, что числа в цепочке делятся на некие "внедрённые" множители. Всё. Как формируется первый член прогрессии n0 и её шаг (модуль) m, откуда берутся "внедрённые" множители (паттерн) - было за пределами моего интереса. Мой интерес был исключительно в ускорении проверки этого миллиона цепочек, и исключительно средствами pari/gp и gp2c.
То же самое было когда я ускорял вашу (полученную от вас через личку) программу. Я не вникал там в тонкости КТО, результат ускорения работал алгоритмически эквивалентно.

[Yadryara]

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

Как формируется первый член прогрессии n0 и её шаг (модуль) m, откуда берутся "внедрённые" множители (паттерн) - было за пределами моего интереса. Мой интерес был

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

Это же вроде несложно: среди 30-значных чисел полупростых гораздо больше чем простых. А среди более длинных — тем более .

[wrest]

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

А понятно ли вам, что найти D(24,6) и уж тем более D(48,6), D(96,6) гораздо вероятнее именно по паттерну?

Да, но хотелось бы получить "гораздо" в виде формулы.
Я так э... смутно понимаю, что речь идёт об увеличении вероятности на примерно 1,5..2 порядка по каждому числу в цепочке куда паттерном уже вставлены множители, если цепочка из 10 чисел, то соответственно на 15-20 порядков (при допущении независимости вероятностей иметь нужно количество делителей, но тут есть большой вопрос а независимы ли они).

[Yadryara]

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

Да, но хотелось бы получить "гораздо" в виде формулы.

Давайте пока для D(12,15).

$P = p_1^{11}p_2^4$

Вот и вся формула.

Здесь $p_1$ — вероятность* числа оказаться простым на определённом интервале.
$p_2$ — вероятность* числа оказаться полупростым примерно на том же интервале.

Кубы пока игнорим.

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

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

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

Конечно считаем независимыми. И вот как раз чтобы сильно не сомневаться, проверяем теорию практикой.

[Dmitriy40]

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

при допущении независимости вероятностей иметь нужно количество делителей, но тут есть большой вопрос а независимы ли они

Разумеется они не совсем независимы: если простое число p попало в разложение места i, то оно уже не может попасть в разложения p-1 мест слева и справа.
Но вот пусть 20 простых чисел самых наименьших 59...151 уже попали в 20 мест кроме интересующего 21-го, значит вероятность разложить 21-е место уменьшилась со 100% до $\prod\limits_{p=59}^{151}\dfrac{p-1}{p}\approx80\%$, что в общем не так уж сильно. Для предыдущих мест с меньшим количеством уже попавших чисел уменьшение разумеется слабее. И с ростом величины попавших простых процент уменьшения вероятности быстро падает (например для 20-и попавших простых чисел перед $2^{15}$ вероятность падает со 100% до 99.94%).
Потому разумно считать вероятности по каждому месту достаточно независимыми.

[wrest]

Dmitriy40
Хотелось бы разобрать, если можно, вот такой пример:

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

Допустим, у нас есть два числа $n0$ и $m$. Например,
$n0=4011862715648=2^8\cdot 47 \cdot 9857 \cdot 33827$
$m=5908599496800=2^5 \cdot 3^4 \cdot 5^2 \cdot 7^3 \cdot 11^2 \cdot 13^3$
Какова вероятность $P$, что все числа $n_j$ в цепочке длиной 6 с первым числом равным $n=n0+k\cdot m$ для $k \approx 10^6...10^9$ будут иметь ровно $\tau=24$ делителя каждое. Ну и вопрос на который который надо ответить до: а чему равны вероятности $P_j$ иметь $\tau$ делителей для каждого из чисел $n_j=n0+k\cdot m + j$ где $j=0..5$

Тут мы собираемся искать D(24,6)

[Yadryara]

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

$m=5908599496800=2^5 \cdot 3^4 \cdot 5^2 \cdot 7^3 \cdot 11^2 \cdot 13^3$

4-ю степень тройки-то вы откуда взяли? Надеюсь, не от балды? Ведь 24 на 5 не делится.

[Dmitriy40]

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

Хотелось бы разобрать, если можно, вот такой пример:

? q=vector(6); s=vector(7); for(k=1,1e5, n=4011862715648+5908599496800*k; q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++; ); print(q); print(s)
[17528, 8052, 28014, 988, 0, 549]
[53559, 38219, 7761, 454, 7, 0, 0]
time = 19,843 ms.
? q=vector(6); s=vector(7); for(k=10^6,10^6+10^5-1, n=4011862715648+5908599496800*k; q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++; ); print(q); print(s)
[16455, 7489, 26803, 869, 0, 486]
[55822, 36716, 7005, 452, 5, 0, 0]
time = 28,518 ms.
? q=vector(6); s=vector(7); for(k=10^9,10^9+10^5-1, n=4011862715648+5908599496800*k; q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++; ); print(q); print(s)
[15007, 6857, 24167, 787, 0, 398]
[59351, 34410, 5914, 322, 3, 0, 0]
time = 1min, 20,934 ms.

Числа в тысячных процента (штук на 100 тысяч).
Первый вектор - вероятности по 6-ти местам +0...+5.
Второй вектор - сколько раз совпало ровно i-1 мест (с 0 по 6).

Ноль в первом векторе намекает что в позиции +4 никогда не может быть 24 делителя.

-- 15.04.2026, 11:30 --

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

4-ю степень тройки-то вы откуда взяли?

Разве это проблема в m? Его же можно хоть m=1 взять (идиотизм, но формально можно). Ну будет у него перебор втрое большего количества n, пока каждый третий не получит 3^5, вопрос ведь не про скорость, а про вероятности.

[Yadryara]

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

Разве это проблема в m?

Вспомнился разговор с vicvolf-ом. Который нам объяснял какие паттерны "проходимые", а какие нет. И я ему сказал, что мы только допустимые и обсуждаем, на кой нам какие-то другие.

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

Вот это же неслучайно:

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

Ноль в первом векторе намекает что в позиции +4 никогда не может быть 24 делителя.

Вот поэтому и вопрос, какое число wrest воткнул в 5-е место паттерна.

[Dmitriy40]

wrest
А вот как выглядит с корректными n0 и m:

? q=vector(6); s=vector(7); for(k=1,1e5, n=502923550+7214407200*k; q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++; ); print(q); print(s)
[31282, 27147, 9138, 26769, 33966, 26317]
[16094, 35256, 30919, 13856, 3438, 417, 20]
time = 6,490 ms.

Заметна разница, не правда ли.
Найдено 20 штук D(24,6).
Да и работает быстрее.

-- 15.04.2026, 12:01 --

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

Вот это же неслучайно:

Так проблема в n0, а не в m (и не в 3^4 в m).
Смотрите, искривлю код выше, тоже понижу степень 3 в m до первой и повышу до четвёртой:

? q=vector(6); s=vector(7); for(k=1,1e5, n=502923550+7214407200\3*k; q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++; ); print(q); print(s)
[31806, 26836, 6263, 26294, 34193, 9237]
[20591, 38723, 28373, 10270, 1871, 166, 6]
time = 5,163 ms.
? q=vector(6); s=vector(7); for(k=1,1e5, n=502923550+7214407200*9*k; q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++; ); print(q); print(s)
[30050, 27710, 8431, 27517, 32669, 37278]
[14155, 33421, 32233, 15557, 4091, 525, 18]
time = 9,970 ms.

Ну и, работает же и с обоими кривыми m!
Вероятности другие, но совсем не нулевые.
Так что проблема исключительно в n0.

-- 15.04.2026, 12:06 --

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

Хотелось бы разобрать, если можно, вот такой пример:

Надеюсь Вы не ожидали что будем считать теоретически, да ещё и все варианты паттернов (и с кубами, и с 5 степенью, и с 7, и с 11)? Ведь не ожидали же? Прогу написать и запустить на порядки быстрее.

-- 15.04.2026, 12:09 --

Заодно видна разница в вероятностях разложений на p (место +2) 9%, pq (места +0, +4, +5) 26%-34%, pqr (места +1, +3) 27%.

[Yadryara]

Я, ещё когда увидел 4-ю степень тройки, чуть позже подумал, что шаг не однократный, но и не 6-кратный (потому что степень двойки не 6-я), а получается необычный, 3-кратный.

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

Так что проблема исключительно в n0.

И вопрос откуда wrest взял эту так называемую добавку, то есть n0.

-- 15.04.2026, 12:23 --

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

Заодно видна разница в вероятностях разложений

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

[EUgeneUS]

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

Да, но я хотел бы и "логику" - что и почему учитывается/не учитывается при подсчёте.

Я же Вам предлагал прислать в электронной почте табличку и комментарии к ней.

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

$10^{-17}$ довольно высокая вероятность.

Ну как, высокая.
Для нахождения цепочки скриптом (без компиляции) на PARI\GP нужно десятки тысяч лет в один поток. pcoul раза в два быстрее, но всё равно - десятки тысяч лет в один поток.

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

Она же - не больше произведения вероятностей по каждому месту в цепочке?

Она ($P(1)$) в точности равна этому произведению

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

Я бы сделал даже 10-100млн проверок, пусть будет 1.5e17, зато >90% времени будут именно проверки, а не накладные расходы. Тут должен быть оптимум, но надо точнее знать время подготовки и скорость итераций, а это надо иметь готовый полнофункциональный код, со всеми подготовительными расчётами и всеми стадиями проверок. Если заморочимся, то можно будет потестировать перед запуском глобального процесса.

Да, конечно. Нужно будет как-то оценить на пробных запусках и оценках скорости - где будет оптимум.

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

Если при работе AVX кода частота не падает (у меня на сервере вот падает),

У меня два серверных Ксеона, так что скорее всего тоже будет падать. Невеселая новость, конечно

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

Разумеется размазывает. Причём если винда новая (новее 7 или 8, не помню), то ещё и в зависимости от прогрева конкретных ядер....

Спасибо за разъяснения, надо будет не забыть вернуться к этому вопросу перед "боевым" расчетом.

[Yadryara]

wrest, вот паттерн, по которому Дмитрий считал:

lcm ([50, 169, 96, 121, 98, 45]) = 7214407200

Подробнее:

mesta     123456

2         1 5 1 
3           1  2
5         2    1
7             2 
11           2  
13         2    

nu        231322

Это та самая легендарная серия с одним простым: 1-3-2-3! Здесь попросту перечислены количества nu, то есть количество факторов в 6-ти частных, которые нужно найти.

Посчитаю и я. Пока по простому:

? v = [50, 169, 96, 121, 98, 45]; ip = 0;
? for(j = 1, #v, if(v[j]% 32 == 0, m32  = j));
? for(j = 1, #v, if(v[j]%  9 == 0, m9   = j));
? obmod = chinese(Mod(33-m32, 64), Mod(10-m9, 27))
%46 = Mod(1246, 1728)
? m = 6 * lcm(v)
%47 = 43286443200
? n0 = lift(chinese(chinese([Mod(-j+1, v[j]) | j<-[1..#v]]), obmod ) + ip)
%48 = 502923550
? q=vector(6); s=vector(7); for(i=1,1e5, n=n0+m*i; q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++; ); print(q); print(s)
[30350, 27596, 17106, 27379, 32808, 37685]
[12712, 31654, 32398, 17359, 5032, 801, 44]
?

Ну вот, 44 цепочки D(24,6) нашлись. В два раза больше чем у Дмитрия Забыл как быстро время посмотреть, но посчитал: секунд за 5-6.

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

И, заметьте, это при отсутствии других фильтраций. То есть, грубо говоря, сейчас была единственная фильтрация — по КТО.

[Dmitriy40]

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

Забыл как быстро время посмотреть,

Последней команды - ##.
Выводить всегда - default(timer,1).

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

Ну вот, 44 цепочки D(24,6) нашлись. В два раза больше чем у Дмитрия

Так у Вас интервал в 6 раз больше. В котором Вы нашли лишь 44% кортежей, зато гораздо (в 6 раз) быстрее:

? q=vector(6); s=vector(7); for(k=1,6e5, n=502923550+7214407200*k; q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++; ); print(q); print(s)
[182054, 166221, 51415, 164468, 196697, 153339]
[100461, 212567, 183570, 81648, 19327, 2327, 100]
time = 53,681 ms.

[Yadryara]

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

Так у Вас интервал в 6 раз больше.

Об этом и говорю. Я так уже привык.

Более того, для длинных цепочек у меня была гипотеза, что если в паттерне стоит $3^2$, то шаг надо брать 6-кратный, а если $3^5$, то 3-кратный и я сразу закладываюсь на две программы.

Вот и хорошо, что по-новой теорию освежаю. Я точно не помню, но у меня было обоснование, почему для $3^2$ можно прям не глядя сразу брать 6-кратный шаг. Кстати, может и не париться с обоснованием, а перечитать первые страницы темы, ведь там шаг тоже был 6-кратный.

Надеюсь, wrest заметил, как и m и n0 считаются прямо по паттерну.

-- 15.04.2026, 16:12 --

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

Последней команды - ##.
Выводить всегда - default(timer,1).

Спасибо. Ну да, 6 секунд:

? ##
  ***   last result computed in 6,281 ms.
?