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

[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$.