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

[DemISdx]

Huz в сообщении #1703332 писал(а):

I hope you didn't miss me too much.

It's nice to see you in an active state!

[VAL]

Hi, Hugo!
I am happy to welcome our team in almost its entirety.
Waiting for mathematician123

-- 26 сен 2025, 19:02 --

DemISdx в сообщении #1703322 писал(а):

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

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

Похоже третий вариант...

Он самый

Цитата:

Разминка завершена.

Нет, будем разминаться дальше в параллель с основными соревнованиями

-- 26 сен 2025, 19:26 --

(Продолжение разминки)

91705289347458030051204972447109082193782584570781489984713125518614545459971526753219060569027148298676850111002427996882112256663193507671 (140 digits)

3 prime factors are desirable

[EUgeneUS]

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

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

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

Обозначим $a_i$ - произведение всех фиксированных в шаблоне множителей для числа на i-м месте.
Мы нашли цепочку-кандидат (где-то в районе числа $N$, пусть первое число в цепочке - $N$), для которой выполняются условия: все числа в цепочке кандидата делятся на фиксированные в шаблоне множители.

1. Какая вероятность, что первое число будет подходящим?
$P_1 = P(N/a_1, 4, 0 ...)$

2. Какая вероятность, что 2-е число будет подходящим?
$P_2 = P((N+1)/a_2, 4, 0 ...)$

Числа $N/a_1$ и $(N+1)/a_2$ не будут соседними, так как $a_1$ и $a_2$ довольно таки различаются.
Можем для целей оценки считать вероятности $P_1, P_2 ...$ независимыми. Нет?

Тогда вероятность найти цепочку будет:
$P_{win}(N) = \prod\limits_{i=1}^{10} P((N-i+1)/a_i, b_i, 0 ...)$

где $b_1=4, b_2=4, b_3=1, b_4=1, b_5=4, b_6=4, b_7=1, b_8=4, b_9=4, b_{10}=4$

Скорее всего асимптотика от $N$ будет зависеть, как логарифм (как это происходит для одиночного простого).
Тогда
$P_{win}(N) \approx \prod\limits_{i=1}^{10} P((\ln(N) - \ln(a_i)), b_i, 0 ...)$

-- 26.09.2025, 19:31 --

Huz
It's good to see you again!

[Dmitriy40]

Интересный паттерн M48n31 обнаружил:
[322161, 578, 4693, 540, 1, 2, 3, 4312, 5, 6, 1, 4, 9, 10, 7, 1248, 1, 2,30855, 4, 1, 2394, 1, 4600, 3, 2, 1, 12, 5915,18502, 27]
В него нужны ещё 16 простых 31-101 в квадрате (в любом порядке на места с числами <100 кроме 4, 9, 12), но если обрезать справа 7 мест, то останется M48n24 с 7-ю проверяемыми числами и 12 простыми 31-79 в квадрате. Да, из M48n24 он очевидно не самый оптимальный, но даёт чуть больше надежду найти укороченные кортежи при поиске полного.

[EUgeneUS]

UPD.

Для оценки вероятности, что нашли подходящее число (на каком-то месте),
вероятноcть $P(N, k, 0 ...)$ нужно трактовать так: вероятность, что число $N$ - произведение $k$ различных простых, при условии, что оно не делится на простые числа уже использованные в шаблоне.
Это условие "выбивает" много вариантов, и вероятность будет сильно ниже, чем просто оценка "по асимптотике", да.

[VAL]

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

Числа $N/a_1$ и $(N+1)/a_2$ не будут соседними, так как $a_1$ и $a_2$ довольно таки различаются.
Можем для целей оценки считать вероятности $P_1, P_2 ...$ независимыми. Нет?

Они не соседние, но не случайные. В частности, ни одно из них не может делиться на простые, использованные при построении других $a_i$.
И это, конечно влияет на интересующие нас вероятности.

Пока набирал, увидел добавку к Вашему сообщению. Примерно о том же.

[ozheredov]

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

I am happy to welcome our team in almost its entirety.

Догадайтесь, кого не хватает.

[VAL]

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

(Продолжение разминки)

91705289347458030051204972447109082193782584570781489984713125518614545459971526753219060569027148298676850111002427996882112256663193507671 (140 digits)

3 prime factors are desirable

Уже разложилось. На 2 простых

[DemISdx]

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

Уже разложилось. На 2 простых

Надо же как быстро!
Понял, снимаю его с очереди исполнения.

[Huz]

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

UPD.

Для оценки вероятности, что нашли подходящее число (на каком-то месте),
вероятноcть $P(N, k, 0 ...)$ нужно трактовать так: вероятность, что число $N$ - произведение $k$ различных простых, при условии, что оно не делится на простые числа уже использованные в шаблоне.
Это условие "выбивает" много вариантов, и вероятность будет сильно ниже, чем просто оценка "по асимптотике", да.

I've long wanted to know how to calculate such things; see https://math.stackexchange.com/questions/4585836/ for an earlier question I asked. I thought I had also asked for something exactly like what you are seeking, but I can't find that question back (and in any case it certainly received no responses). I have tried searching for more information, but have found little beyond some crude estimates for semiprimes.

Since perfect squares in the region of $n$ are spaced about $2\sqrt{n}$ apart, I think we can say that the probability that an arbitrary $n$ is of the form $p^2$ is (asymptotically) $\frac{1}{2\sqrt{n} \ln{\sqrt{n}}} = \frac{1}{\sqrt{n}\ln{n}}$, and similarly for higher powers. The probability of "$n$ prime given that it is $5 \pmod{6}$" is also calculable. However I have no idea about the probability it is of a form such as $pq^2$.

[EUgeneUS]

Huz
Thanks for the answer!

Your probability estimate clearly shows that patterns where the unknown $p^2$ is searched for can only give a result in fantastic cases. As the respected VAL said.

Even for not very large numbers, like $n=10^{20}$: $P(n=p^2)=\frac{1}{\sqrt{n}\ln{n}} \approx 2.2 \cdot 10^{-12}$

Therefore, to assess the "quality of pattern", approximations for the product of primes in the first power are more interesting.
The respected VAL said that they exist:

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

Частные случаи безусловно изучены. Например, хорошо известна асимптотика чисел свободных от квадратов.

But they need to be adjusted to the condition that these primes are not from the first primes already used in the pattern.

[Huz]

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

Huz
Thanks for the answer!

Your probability estimate clearly shows that patterns where the unknown $p^2$ is searched for can only give a result in fantastic cases. (...)

You need to be careful here - if the only unknown is $p^2$ then that is true (but it also means you can search through a given space very quickly, particularly combined with any modular constraints). However if you are looking for $p^2q$ then the probability for a given $n$ is something more like $\sum_{p \in \mathbb{P}}{ \frac{1}{p^2 \ln{n/p^2}} }$, i.e. the probability over all primes in the appropriate range that a) $n$ is divisible by $p^2$, and b) the result of the division is a prime. That's a much higher chance than for $p^2$, and it grows again for $p^2qr$ - and of course more possibilities means more work searching through them all.

Certainly the cases solved so far have mostly involved only small primes to higher powers, but there are exceptions notably when modular constraints force a square such as for $D(18,4) = 2 \cdot 13^2 \cdot 442729363^2$.

[Dmitriy40]

Ради интереса проверил вероятности степеней больших (больше 100) делителей для миллиона случайных чисел в диапазоне 1e19-1.8e19. Получилось следующее:
42% вариант $pq$
28% вариант $pqr$
21% вариант $p$
7.8% вариант $pqrs$
0.9% вариант $pqrst$
Варианты с квадратами, как и вариант с 6-ю простыми, все менее 0.1%.
Варианты с кубами или с 7-ю простыми - штучно, т.е. менее 0.001%.
Варианта $p^2$, как и вариантов со степенью больше 3, вообще не встретилось.

Для 10млн случайных чисел в том же диапазоне картина качественно не изменилась, хотя появились два числа с 4-й степенью и варианты с двумя квадратами и одним-двумя-тремя простыми в первой степени (7шт, 4шт, 2шт).

[VAL]

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

Ради интереса проверил вероятности степеней больших (больше 100) делителей для миллиона случайных чисел в диапазоне 1e19-1.8e19. Получилось следующее:

Опять хорошо забытое старое.
Мы уже делали подобную статистику. Причем не для произвольных чисел, а для тех, которые возникают в наших алгоритмах.
В этой теме упомянутая статистика где-то выложена.
И картина там принципиально иная.
Можно поискать точные значения, но по памяти скажу, что с отрывом наиболее популярны случаи $pqr$ и $pqrs$.
Далее идут $pq$ и $pqrst$ и только потом $p$.
Размеры исследуемых чисел были существенно больше, 30-40 знаков.
Картина для 30-значных и 40-значных схожа. Хотя с ростом чисел мода ожидаемо мигрирует от $pqr$ к $pqrs$.

-- 27 сен 2025, 16:18 --

То что выкладывалось здесь, пока не нашел (многовато пишем )
Но аналогичную статистику я проводил перед поиском достаточно длинных цепочек для каждого $k$.
Вот, например, для 17 чисел по 96 делителей:

[7.350000, 22.64000, 29.67000, 23.38000, 11.93000, 3.840000, 1.190000]

Здесь слева направо процент: $p; pq; pqr; pqrs; pqrst; pqrstu;$ более 6-и простых.
Проверяемые числа имеют по 48 знаков.
Картина немного отлична от той, что я вспомнил. По-видимому, это связано с тем, что для $k=96$ в шаблоне участвует мало фиксированных простых. Или просто память подвела

-- 27 сен 2025, 16:30 --

PS:
Уточнение.
Это статистика не для цепочек длины 17, а для цепочек длины 10. Соответственно числа 30-значные и список фиксированных модулей меньше.
Просто в программку для длинных цепочек она перекочевала по наследству

[VAL]

А вот статистика для чисел, с помощью которых искалась 10-ка для $k=72$. Числа 44-значные.

[6.61, 21.72, 30.23, 23.58, 11.98, 4.47, 1.41]

Видно, что картина меняется не сильно.

Пора бы завершить разминку, идущую параллельно поиска рекорда . Это почти гарантировано можно сделать одной факторизацией.

(2 prime factors wanted)

509562375280524362136320293261120283041279785753884888244145194356349740254034836192041791475412215036355843721 (111 digits) = pq?