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

[Yadryara]

Конкретика.

Вот тот самый мультипустой паттерн(b1165) :

[ 1, 12, 1, 242, 75, 32, 637, 18, 1, 20, 3, 2, 1]

Наименьший куар, который можно поставить на 27-е место — 3131.

Поставил. Теперь наименьший куар, который можно поставить на 39-е место — 8903.

Поставил. Теперь наименьший куар, который можно поставить на 29-е место — 8917.

Поставил. Теперь наименьший куар, который можно поставить на 35-е место — 72451. Он единственный меньше 200 тысяч.

Ставлю и его:

[ 3131, 12, 8917, 242, 75, 32, 637, 18, 72451, 20, 3, 2, 8903]

Совершенно очевидно, что этот паттерн с огромным LCM порядка 1e25 проверится за долю секунды.

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

[EUgeneUS]

Ага, теперь понятно.
То есть расставляя $qr$ в одну позицию, мы получаем дополнительные ограничения на оставшиеся.

У меня бродили такие смутные мысли , но не вылились в конкретику. Впрочем, у меня эти мысли были вокруг расстановки $p^2$ всё таки.

Что касается идеи с расстановкой $qr$, даже расстановки двух будет достаточно для быстрой, моментальной проверки.
Так как получим Пёлль-подобное уравнение.

[Huz]

Yadryara I'm not quite sure what you are aiming at with the new focus on $qr$. If the idea is to avoid the need to iterate over all large $p^2$ by instead iterating over the possible $qr$, then it may be of interest to consider at what value the expected number of primes $p$ balances the expected number of semiprimes $qr$.

For known upper limits of $D(12,k)$, using $|p \le n| = n/\ln{n}, |qr \le n| = n \ln{\ln{n}}/\ln{n}$, I find the following results:

$k=12, p \le 71344704, |p| = 3945394$
$k=13, p \le 1228226700, |p| = 58685854$
$k=14, p \le 187746592315, |p| = 7232606363$
$k=15, p \le 649195465122, |p| = 23868358122$

Of course if a high proportion of the $qr$ can efficiently be rejected as impossible, then the balance changes; however it is not clear to me how you are rejecting them - could you clarify that please?

[EUgeneUS]

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

however it is not clear to me how you are rejecting them - could you clarify that please?

In each pattern ($sq=0$) there are fixed numbers that are multiples: 32, 9, 25, 7, 11 and 13.
However, numbers of the form $p^2$ do not have all possible remainders in these modules.
And from this it follows that $qr$ cannot have all possible remainders with respect to these modules. This means that some of them are forbidden (for a specific pattern and for a specific location in the pattern).

[Yadryara]

Huz

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

Of course if a high proportion of the $qr$ can efficiently be rejected as impossible, then the balance changes; however it is not clear to me how you are rejecting them - could you clarify that please?

I check modules. This check is effective only for factors of prime squares. If you understand PARI/GP, I can publish the program.

[Dmitriy40]

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

In each pattern (sq=0) there are fixed numbers that are multiples: 32, 9, 25, 7, 11 and 13.
However, numbers of the form $p^2$ do not have all possible remainders in these modules.

Реализовал это на асме+PARI (перебор всевдопростых с проверкой по этим модулям для каждого возможного варианта из всех паттернов), перебор $p^2$ идёт вдесятеро быстрее чем на чистом PARI, вместо 22ч оценка 2ч на одно qr (от паттернов не зависит, влияет на все). Надеюсь за несколько часов проверятся все 22<qr<600 (-p1e12).

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

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

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

[Yadryara]

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

И всё же, почему бы не проверять места с одним простым?

Я пока не дошёл до этого. То есть ещё не думал над этим.

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

[Huz]

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

In each pattern ($sq=0$) there are fixed numbers that are multiples: 32, 9, 25, 7, 11 and 13.
However, numbers of the form $p^2$ do not have all possible remainders in these modules.
And from this it follows that $qr$ cannot have all possible remainders with respect to these modules. This means that some of them are forbidden (for a specific pattern and for a specific location in the pattern).

Thank you, that is quite clear.

I was thinking this could be an interesting avenue to explore for speeding up the calculation of the minimum, but since the restrictions are location-specific it is not simply a question of preparing a single list of valid semiprimes. I assume that almost all primes $p$ have $(p-1)/2$ quadratic residues, so would expect roughly one in $2^6$ of the semiprimes to be valid in a single location; fixing one at that location would then leave about one in $2^8$ valid in a second location, and so on.

(In fact it is slightly better than that, since residues of $2^3$ and $3$ already give a 6-fold improvement.)

[EUgeneUS]

Huz
In general, I agree. But we can look at the problem from the other side.
Suppose, for simplicity,
a) we have 3000 patterns
b) each of them has 4 places to place $p^2qr$
c) We have limited $qr$ from above and consider the first 1000 options from them.

Then the number of location variants $qr$ will be:
$N = 3000 \cdot 4! \cdot C_{1000}^4 = 3000 \cdot 24 \cdot 41417124750 = 2982032982000000$

And modulo filtering will reduce this huge number by $64^4 = 16777216$ times.

[Yadryara]

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

so would expect roughly one in $2^6$ of the semiprimes to be valid in a single location;

Half as much(one in $2^7$) because we need to look at the module 64, not 32.

[EUgeneUS]

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

Реализовал это на асме+PARI (перебор всевдопростых с проверкой по этим модулям для каждого возможного варианта из всех паттернов), перебор $p^2$ идёт вдесятеро быстрее чем на чистом PARI, вместо 22ч оценка 2ч на одно qr (от паттернов не зависит, влияет на все). Надеюсь за несколько часов проверятся все 22<qr<600 (-p1e12).

ЗдОрово!

Насколько понимаю, что это может сильно помочь в уменьшение времени для ограничения на простые в квадратах для доказательства минимальности 13-ки (а в перспективе 14-ки и 15-ки) - через более быстрое уменьшение порога в ключе -p.

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


Считаем "перспективными" паттерны с количеством проверяемых мест 10 и 11.
Таких есть
а) три группы с $LCM=7214407200$. Насколько понимаю, там и осуществлялся ранее поиск 14-к (или отдельно 14-к, или в рамках поиска 15-к).
Эти группы мы сейчас обсчитываем с DemIS'ом, с ключом -p500.
Цель обсчитать их до 21e31, что примерно в 10 раз меньше, чем минимальная известная 14-ка.
б) три группы с $LCM > 7214407200$. Эти обсчитываются у меня в один поток. Цель та же - обсчитать их до 21e31.
Это всё не быстро. Но сроки выглядят приемлемыми (единицы месяцев).

в) и есть три группы паттернов с $LCM < 7214407200$
А вот с ними проблемы. Оценки для худшего LCM дают время расчета около 13 млн. секунд (полгода) с тем же ключом: -p500. Для одного паттерна.
Меня гложут смутные сомнения, что вероятность найти цепочку в этих паттернах все таки не настолько велика, насколько велико прогнозируемое время расчета. Но каких-то идей, уменьшить время расчета для них пока нет

-- 20.01.2023, 18:33 --

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

Half as much(one in $2^7$) because we need to look at the module 64, not 32.

Тут у Хуго верно.
Проверка по каждому модулю уменьшает количество $qr$ примерно в два раза (для конкретного места в конкретном паттерне).
А разным модулей - 6 штук. Итого в $2^6$ раза.

[Yadryara]

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

Проверка по каждому модулю уменьшает количество $qr$ примерно в два раза (для конкретного места в конкретном паттерне).
А разным модулей - 6 штук. Итого в $2^6$ раза.

А вы сами-то проверяли?

Существует 8591 $qr$ до 100 тысяч. Согласны?

Я нашёл только по 68 подходящих на 29-е и 39-е места. В 126 раз меньше. И это гораздо ближе к 128 чем к 64-м.

А сколько нашли вы?

[EUgeneUS]

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

А вы сами-то проверяли?

Нет, выкладки теоретические. Если модули взаимно просты, то они работают "независимо".

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

Я нашёл только по 68 подходящих на 29-е и 39-е места. В 126 раз меньше. И это гораздо ближе к 128 чем к 64-м.

Насколько понимаю, речь о конкретном паттерне. В котором 11 и 13 в квадратах.
Это несколько улучшает "фильтрацию по модулям". Но не в два раза.

Но применение модуля $64$ не должно улучшить фильтрацию по сравнению с модулем $32$.

Согласен. Применение модуля $64$ улучшает фильтрацию в два раза, по сравнению с модулем $32$:
$p^2$ даёт 8 вариантов по модулю $64$, а нам нужен ровно один.
$p^2$ даёт 4 варианта по модулю $32$, а нам нужен ровно один.

[Dmitriy40]

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

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

Как-то она не очень оправдывается: для этого (b1165) паттерна с qr<60000 есть 584 варианта расстановки таких qr по 4-м пустым местам. Из них 18 вариантов с 3131 на левом месте, вот парочка из них:
[3131,12,6613,242,75,32,637,18,51811,20,3,2,36623]
[3131,12,49573,242,75,32,637,18,1411,20,3,2,15503]

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

ЗдОрово!

Насколько понимаю, что это может сильно помочь в уменьшение времени для ограничения на простые в квадратах для доказательства минимальности 13-ки (а в перспективе 14-ки и 15-ки) - через более быстрое уменьшение порога в ключе -p.

Как-то оно не особо помогает, уменьшение порога до 2e12 заняло 3.5ч и до 1e12 собирается уменьшать ещё часов 10. А при уменьшении порога количество разных qr быстро растёт, соответственно падает и скорость уменьшения -p, примерно квадратично (т.е. типа сутки до 3e11 и неделю до 1e11).

[EUgeneUS]

О!
Эту идею можно распространить и на другие модули.
Например, проверять не по модулю $9$, а по модулю $27$. Тогда
а) всего остатков - 11 штук.
б) остаток $0$ исключается и из знаменателя, и из числителя.
в) остаётся $10$ остатков, из которых подходит только один.
Итого фильтруем $1/10$, а не $1/3$, как при применении модуля $9$.

-- 20.01.2023, 19:25 --

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

Как-то оно не особо помогает, уменьшение порога до 2e12 заняло 3.5ч и до 1e12 собирается уменьшать ещё часов 10. А при уменьшении порога количество разных qr быстро растёт, соответственно падает и скорость уменьшения -p, примерно квадратично (т.е. типа сутки до 3e11 и неделю до 1e11).

ИМХО. А дальше применять при расчете конкретных паттернов. А-ля, увеличить скорость "W-стадии". Нет?