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

[VAL]

Пятерка по 402 делителя нашлась не так стремительно, как по 366. Но, все равно, гораздо быстрее, чем по 318.

(Оффтоп)

11207723812975104889815905346078689211265012606429723931733738727967383817107796675816819911738566518340876426179144550736580207003819166334177571849687313023839907923052228847788776403619954501987894806952819825048782806628062489612063176298759900333486541834905209923744874675859349844822160676312159543548069548781398829117884537645144721197241701775160315004417821755205854344649604127223417374523553589736808830306101349696220881688804794071357959766386231253809549566341496884547268564347177743911743164062497

Ищу пятерку по 426 делителей.

[EUgeneUS]

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

M48n21: за 6.5ч и 5e52 (и 5e8 вероятных цепочек) по прежнему лишь один кандидат длиной 13 и всего лишь 7 кандидатов длиной 12 (и только один из них может и правда дать цепочку длиной 12), более же длинных нет вовсе. До цепочки 21 как до Седны
.

Это довольно странно. Когда запускал программы уважаемого VAL по поиску 20-ки, то
а) 19-ка не нашлась ни разу.
б) 18-ка нашлась один раз.
в) А вот мЕньшие находились довольно таки регулярно.
Это за некосколько суток счета, порядка недели, в два потока. Вечером ещё логи посмотрю более подробно и напишу.
Тут имеются в виду не непрерывные цепочки (maxlen), а количество подходящих чисел в кандидате (valids).

В порядке мозгового штурма , возможно, вероятность $pqr$ сильно переоценена, и будет выгоднее одно из простых "прибить гвоздями" и искать $pq$?

[VAL]

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

M48n21: за 6.5ч и 5e52 (и 5e8 вероятных цепочек) по прежнему лишь один кандидат длиной 13 и всего лишь 7 кандидатов длиной 12

Как-то слишком скудно Может, где-то какой-то баг...

Прикинул для каких еще $k$ отыскать длинные (больше 7) цепочки.
В частности, для $k=108$ нахождение восьмерки и даже девятки (а может и больше) представляется вполне реальной задачей.
Сейчас попробую эмпирическое мат. ожидание посчитать

-- 20 июн 2022, 09:09 --

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

Это довольно странно. Когда запускал программы уважаемого VAL по поиску 20-ки, то
а) 19-ка не нашлась ни разу.
б) 18-ка нашлась один раз.
в) А вот мЕньшие находились довольно таки регулярно.

Вот и я о том же.

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

возможно, вероятность $pqr$ сильно переоценена, и будет выгоднее одно из простых "прибить гвоздями" и искать $pq$

Гарантирую, что это ГОРАЗДО хуже.
pq - самая невыгодная ситуация. По вероятности выигрывает только у p (но при этом катастрофически проигрывает по скорости проверки).
В том диапазоне, в котором идет поиск длинных цепочек, самое выгодное pqr, а затем pqrs.
Посмотрите на мои таблицы с шаблонами паттернов: я стараюсь изживать pq всеми силами. И это не вкусовщина

-- 20 июн 2022, 09:16 --

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

У меня-то в таблице на 62-й странице она имеется с точностью до порядка.

Найти на 62-й (или 1328-й) странице - задача не из легких.
Возможно, назрела необходимость попросить модераторов сделать закрепленное сообщение (тему) с таблицами?
И обновлять их путем правки.

-- 20 июн 2022, 09:29 --

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

Возможно, назрела необходимость попросить модераторов сделать закрепленное сообщение (тему) с таблицами?

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

[Yadryara]

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

Может, просто разместить таблицы в первом сообщении данной темы?

Ну наконец-то. Именно эта мысль возникла у меня, как только я опубликовал свою таблицу на 56-й странице. Вот в точности такая же.

НО. Править их смогут только ЗУ или начальство. Что же я опубликую таблицы и буду регулярно напрягать людей, чтобы они их правили ??

А теперь, раз уж Вы сами об этом заговорили, прямой вопрос:

Будете ли Вы своевременно править не только свои, но и мои таблицы ?

[VAL]

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

Будете ли Вы своевременно править не только свои, но и мои таблицы ?

Править не буду. Иначе, там вскоре концов никто не найдет...
Но обязуюсь выкладывать обновленные таблицы, которые Вы мне будете высылать, взамен старых.

[VAL]

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

Прикинул для каких еще $k$ отыскать длинные (больше 7) цепочки.
В частности, для $k=108$ нахождение восьмерки и даже девятки (а может и больше) представляется вполне реальной задачей.
Сейчас попробую эмпирическое мат. ожидание посчитать

Прикинул для девятки.
Делал паттерн на 9 isprime, полагая, что числа будут слишком велики, чтобы факторизовать. Оказалось, что не слишком.
Но даже если считать через 9 isprime, потребуется порядка двух триллионов цепочек прошерстить. Многовато, конечно. Но на 3 порядка меньше, чем для 21 числа по 48 делителей с 5-ю isprime.

Полагаю при 6 или 7 isprime прогноз будет совсем хороший.

[EUgeneUS]

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

Гарантирую, что это ГОРАЗДО хуже.
pq - самая невыгодная ситуация. По вероятности выигрывает только у p (но при этом катастрофически проигрывает по скорости проверки).
В том диапазоне, в котором идет поиск длинных цепочек, самое выгодное pqr, а затем pqrs.

А может быть у Вас и оценки вероятностей есть для чисел от 50 до 100 десятичных знаков?

[EUgeneUS]

Нашел статью с оценкой вероятности, что число полупростое. Например, тут.

Там даётся такая оценка: $P(y=pq) \approx \tilde{g}(y) = \frac{\ln{\ln{y}}}{\ln{y}} + \frac{0.265}{\ln{y}} - \frac{1.540}{\ln^2{y}} $

Я сравнил вероятности, что число простое ($P(y=p) \approx \frac{1}{\ln{y}}$), и что число полупростое для разных порядков числа. Получилось, что отношение вероятностей изменяется от $\approx 5$ при десятичном порядке числа $50$, до $\approx 6.5$ при десятичном порядке числа $200$.
С учетом применения ускорителей, отношение не очень большое. Ускорители ускоряют больше. Так и подмывает заменить в паттернах $pq$ на $p$, путём прибития гвоздями $q$. Но это плохой путь. Так как резко снижает вероятность нахождения цепочки (для 15-ки на 36 делителей - примерно на четыре порядка). А значит искать придется в бОльших числах, что опять же снизит вероятность нахождения цепочки

Поэтому предложение следующее:
1. Не уменьшать искусственно число позиций $pq$ за счёт увеличения позиций $p$.
2. Числа в позициях $pq$ тоже "пропустить через ускорители" по следующей схеме:
а) если число разделилось ровно на одно среднее простое - отправить остаток в isprime
б) если число разделилось более чем на одно среднее простое - отправить всю цепочку в треш.
в) если число не разделилось ни на какое среднее простое, то тут вопрос, что с этим делать. Может просто в лог сложить (если цепочка не выкинулась по другим причинам).

Кстати, в упомянутой работе есть оценка вероятности того, что число - "сильно полупростое", то есть такое, которое будет факторизоваться тяжело.

-- 20.06.2022, 18:05 --

И ещё некоторые соображения по поиску длинных цепочек с количеством делителей $k=12n$
Ранее я заявлял, что по наблюдениям применение ускорителей позволит улучшить цепочки на 1-2 позиции.
Но эти наблюдения были сделаны по цепочкам с $k=12n$, где $n$ - нечетное.
Такие цепочки характеризуются "дефицитом" простых (в первой степени), в результате в них
а) относительно много позиций, где нужно искать $p$.
б) в остальных позициях нужно искать $pq$.
За счёт пункта "а" ускорители оказываются весьма эффективны.

Если же $n$ - четное, то наблюдается "избыток" простых (в первой степени), в результате в таких цепочках:
а) относительно мало позиций, где нужно искать $p$.
б) имеются, но опять же их немного, позиции, где нужно искать $pq$.
в) в остальных позициях $pqr$ или даже $pqrs$.
За счет того, что ускорители не применяются к позициям $pq$, $pqr$ или $pqrs$ их эффект оказывается снижен. И получается соревнование мощностей в "голом" PARI/GP", а у уважаемого VAL их больше

Возможно, применение ускорителей к $pq$ по схеме, как описано выше, сможет как-то улучшить ситуацию.

[Huz]

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

Нашел статью с оценкой вероятности, что число полупростое.

I don't fully understand how you're using this info, but a note of caution: as soon as you say, for example, that $y$ is odd, you change the probabilities. In this case I assume that by fixing factors for each of the numbers in the chain you are ensuring that $y$ is not divisible by any of the first several primes, and I'd expect that to change the probabilities quite a lot.

I assume also that $P(y = p)$ would increase much faster than $P(y = pq)$ as you rule out the possibility that $y$ is divisible by a given small prime, so the relative probabilities will also change.

[VAL]

Солидаризируюсь с Hugo.
Вероятность того, что число из данного диапазона полупростое вообще и в случае нашей задачи - это две разные вероятности.
В нашей требуется найти вероятность того, что число из данного диапазона, заведомо взаимно простое с данными небольшими простыми числами, является полупростым. Конечно ее тоже можно решить аналитически. Но это непростая задача и я обходился эмпирическими оценками. Практика показывает, что они весьма точны и устойчивы, если массив проверяемых чисел велик.
Но отсюда следует, что стозначные так не измерить. Для эмпирической оценки вероятности требуется большая статистика. А тут одно число сутками не раскладывается
С другой стороны, судя по тому, как плавно меняются искомые вероятности при изменении диапазона рассматриваемых чисел, например, от 30 знаков до 50, можно сделать правдоподобные предположения и о 100-значных.

-- 20 июн 2022, 20:53 --

Где-то ближе к началу темы есть мои таблицы с оценками (кажется для $k=12$). Но, кроме Антона, найти их вряд ли кто-то сможет

[VAL]

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

Где-то ближе к началу темы есть мои таблицы с оценками (кажется для $k=12$).

Нашел. Там оказалось не $k=12$, а $k=48$:
сообщение #1552349"
Там, кстати, вероятности для pq и pqrs близки.
Это для малых чисел. А с ростом идет смещение в пользу pqrs.

[VAL]

$M(340)=7$

(Оффтоп)

45675565861352053649773853116051589154528195516620684897686445905813648733823710311166419039310679925285451884621735545286435514110617480163574218749

Сейчас запущу поиск девятки по 108 делителей.

[Dmitriy40]

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

Может, где-то какой-то баг...

Действительно, это я лажанул в оценке количества делителей при неполной факторизации в PARI (огрехи погони за скоростью). Сейчас нашёл, поправил, запустил, за круг 1e52 нашлось 6 кандидатов длиной 21 после первого теста (factor(x,2^18)), из которых один дал возможную длину 20 и два длину 11 после второго теста (factor(x,2^26)), остальные ещё меньше, до третьего и четвёртого теста не дошло (так как длина меньше 21). Время на круг если и изменилось, то меньше флуктуаций, те же 71 минута. Посмотрю что к утру будет.
14 чисел по 72 делителя ещё не делал ускорителей, но помню. Их-то накомпилить несложно, пары часов хватит, но вот с PARI перебором наверняка снова будет затык ... но надеюсь не на дни, хватит и часов.

[VAL]

$M(426)=5$

(Оффтоп)

107057023075389029709754291558753739342911704440358081459361866851854378830457475973803268601725061846247437589531445422011268935458066920240154199123169309940905439297795839147436513484835060316352229828128427720834489915074240410283257547342515967538528916840052431757428507547372670159417119544971760728775256864211489381640236528171879285817832062900970882319555431351222511504077219396521031588860868548678811084195987743958601645666057560542656625856719815747323577717003236953725069159521134803687153480566962571174371987581253051757812497

[VAL]

$T(54,9)\le 263834570016843006878958155491532724466457518421525444391932469557457332386577148$