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

[Huz]

Note that '-p1:4000000' will be slightly slower than '-p4000000' - it does extra checks when the minimum prime is set to a non-zero value.

It is also worth experimenting for the optimal value of -g before assessing the acceleration. In my experience, adding a restriction with -p will usually increase the optimal value.

[EUgeneUS]

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

Note that '-p1:4000000' will be slightly slower than '-p4000000' - it does extra checks when the minimum prime is set to a non-zero value.

Thank you.
It was not clear to me from the description of the key in the README that the -p4000000 format would limit primes from above, not from below.

2 ALL. Вот тут я был не точен:

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

$p^3 q^2 \le 10^{22}$, при этом $q \ge 13$. Ограничение сверху на $q$ в данном случае неважно.
Тогда $p \le \sqrt[3]{10^{22} / 13^2} \approx 3,9 \cdot 10^6$

Так как, вообще говоря, есть места с $2^2, 3^2, 5^2, 7^2, 11^2$, то правильная оценка:
$p \le \sqrt[3]{10^{22} / 2^2} \approx 13,6 \cdot 10^6$

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

А почему, кстати, продолжается обсуждение кубоквадратов? Если Дмитрий ещё месяц назад установил что их нет:

Это Вы удачно вспомнили, что Дмитрий исключил кубоквадраты. А обсуждается, хотя бы потому, что при сведении результатов в кучу об этом нужно не забыть, а весь код, которым результат получался хорош бы сложить в единое место.

Таким образом, схема выглядит так:
1. Исключаем паттерны с $8p^2$, можно прямым расчетом, можно кратким доказательством. Остаются паттерны с $32p$.
2. Для паттернов с $32p$ исключаем кубо-квадраты для всех паттернов. Прямым расчетом до верхней границы (до известной цепочки) в PARI/GP. При этом исключаются как паттерны с уже расставленными кубо-квадратами, так и паттерны, где кубо-квадраты могут возникать при переборе.
3. Для всех паттернов с $32p$ уменьшаем границу простых, которые подставляются в степенях, до $10^9$. Расчетом в PARI/GP.
4. Для "сложных" паттернов, отдельным расчетом под конкретный паттерн уменьшаем границу простых, которые подставляются в степенях, до $1..4 \cdot 10^6$. Расчетом в PARI/GP.
6. Считаем паттерны в pcoul с ключом для ограничения на простые (значение - из пункта 3 или пункта 4). Факторизации с $p^5$ все проверятся в pcoul, так как ограничения простых будет в любом случае выше, чем простое в пятой степени.

[Yadryara]

Нижеследующее является ещё одной попыткой объяснить работу программ Дмитрия. Предназначено не только для Hugo. Речь идёт только о 12 делителях.

Итак установлено, что в составе искомой 11-ки обязательно есть $32p_1$ и $18p_2$. И числа 32 и 18 действительно присутствуют во всех 1211 признаваемых мною паттернах Hugo.

С помощью Chinese Remainder Theorem мы выбираем начальное число. С него и начинаем проверку того или иного паттерна.

Нам нужно установить являются ли числа $p_1$ и $p_2$ простыми. Ведь тогда и только тогда числа $32p_1$ и $18p_2$ будут иметь по 12 делителей каждое.

Как будем проверять?

Дмитрий здесь применяет предпроверку. Его код на Ассемблере последовательно проверяет число $p_1$ на делимость на числа 13; 17; 19; ... 4093. Как только разделится нацело, становится понятно, что число $p_1$ составное и дальнейшая проверка не имеет смысла.

Тоже на Ассемблере(Асме) делается определённый для этого паттерна шаг и проверяется следующий по величине кандидат в простые $p_1$. Снова код на ассемблере последовательно проверяет число $p_1$ на делимость на числа 13; 17; 19; ... 4093.

Если все проверки до 4093 включительно пройдены, то $p_1$ пока сохраняет статус кандидата. Теперь Асм начинает проверку $p_2$, последовательно проверяя число $p_2$ на делимость на числа 13; 17; 19; ... 4093.

Как только разделится нацело, становится понятно, что число $p_2$ составное и дальнейшая проверка не имеет смысла. Снова на Асме делается определённый для этого паттерна шаг и проверяется следующий по величине кандидат в простые $p_1$.

Если оба числа $p_1$ и $p_2$ наконец пройдут эту предпроверку, то аналогичным образом будет проверяться $p_3$.

Допустим и $p_3$ прошло эту предпроверку.
Согласно моей таблице в основных 1044 паттернах может быть от 3 до 7 проверяемых мест. Если их всего 3, то после успешной предпроверки этих самых трёх чисел $p_1$, $p_2$ и $p_3$ работа Асма заканчивается и дальше работает уже PARI, которая допроверяет эти 3 числа, а также и другие 8 чисел.

В случае неуспеха вновь на Асме делается определённый для этого паттерна шаг и проверяется следующий по величине кандидат в простые $p_1$.

И это продолжается вплоть до 1e22.

Hugo, пока всё понятно?

Если я объяснил неточно, Дмитрий, надеюсь, поправит. Ну и предел предпроверки 4093 вполне мог быть скорректирован. Ведь сейчас мы работаем с гораздо меньшими числами чем при поиске 15-ки.

[Yadryara]

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

Это Вы удачно вспомнили, что Дмитрий исключил кубоквадраты.

Я об этом и не забывал. Неужто Вы с Дмитрием забыли?

Неслучайно я делил паттерны именно так:

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

Я пока разделил 2471 паттерн Hugo так:

1044 — основные;
99 — БКП(под Быстрый Квадратичный Перебор);
68 — с кубоквадратами;
1260 — лишние.

И уже говорил почему разделил именно так:

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

Видимо, всё-таки удобней различать математически невозможные паттерны, как те 1260 с $8p^2$, и паттерны, где перебор всё-таки был необходим.

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

Уже писал, что из 99 БКП-паттернов, видимо, остаётся исключить только 6 с $22p^2$.

b59: 7^2 2.5^2 3 2^5 . 2.3^2 5 2^2.7 3         2.11  . [22]
b70: 7^5 2.5^2 3 2^5 . 2.3^2 5 2^2.7 3         2.11  . [22]
b82: 7 2.5^2 3 2^5 . 2.3^2 5 2^2.7 3           2.11  . [22]
b572: 2^2.3 7^2 2.5^2 3 2^5 . 2.3^2 5 2^2.7 3  2.11    [22]
b580: 2^2.3 7^5 2.5^2 3 2^5 . 2.3^2 5 2^2.7 3  2.11    [22]
b589: 2^2.3 7 2.5^2 3 2^5 . 2.3^2 5 2^2.7 3    2.11    [22]

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

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

Тоже об этом уже писал:

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

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

По аналогии с 1-й и 100-й, выберите страницу, где Ваше сообщение расположено в самом верху и правьте его многократно. Так всем заинтересованным будет легче ориентироваться.

Надеюсь, Дмитрию уже вернули "бесконечную" правку постов.

[Dmitriy40]

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

Если я объяснил неточно, Дмитрий, надеюсь, поправит.

В общем всё правильно. За исключением порядка проверки (проверяются сразу все числа $p_i$ на делимость на 13, потом все на 17, потом все на 19, ..., а если $i$ мало и в регистры влезают несколько чисел $p_i$, то проверяется их делимость одновременно и на 13 и на 17, возможно частично, смотря сколько влезло в регистр) и вопросов оптимизации по скорости.
В принципе я могу и на инглишь перевести (и подсократить) свой рассказ сильно выше в теме про работу ускорителей, когда думали статью писать. Плюс где-то там несколько ниже был псевдокод ускорителей в виде 3-4-х циклов и одного if (кажется когда про видюхи заговорили).

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

Так как, вообще говоря, есть места с $2^2, 3^2, 5^2, 7^2, 11^2$, то правильная оценка:
$p \le \sqrt[3]{10^{22} / 2^2} \approx 13,6 \cdot 10^6$

Согласен, для простых ниже этого порога надо бы или добавить в последнюю программу проверку цепочек с $p^3 q^2$ для всех возможных $q$ при данном $p$, или лучше однократно проверить все $10^5<p<14\cdot10^6$ ($10^5$ это с большим запасом) перебором по $q<\sqrt{10^{22}/p^3}$. Да Антон, снова, мало ли что я там напроверял месяц назад.

-- 21.11.2022, 11:08 --

Программа уменьшения порога $p$ из формулы $p^3 q^2$ для цепочек длиной 10+:

stop=1e22;
pmax=ceil((stop/2^2)^(1/3));
{forstep(p=pmax,13,-1,
   if(!isprime(p), next);
   qq=sqrt(stop/p^3);
   forprime(q=2,qq,
      h=p^3*q^2; nn=round(h/32); if(!ispseudoprime(nn), next);
      h=nn*32; x=h%18;
      if(x==2,   if(!ispseudoprime((h-2)/18) || numdiv(h+2)!=12, next);
      , x==16,   if(!ispseudoprime((h+2)/18) || numdiv(h-2)!=12, next);
      ,      next;
      );
      if(numdiv(h-1)!=12 || numdiv(h+1)!=12, next);\\Все 4 ближайших числа вокруг 32x должны быть правильными
      print("32x=",h);\\Что-то возможно нашли
   );
)}

Она за пару минут уменьшает порог $p$ до $10^3$, а за 6 минут и до $10^2$, и завершается за 20 минут так ничего и не найдя.

[Yadryara]

Маруся досчитала 10 паттернов. Вот три самые интересные находки.

Непрерывная 10-ка:

LCM42688800-29157241-4:7470542326090073404441: 32, 8, 16, 48, 64, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, valids=10, maxlen=10

И 12-ки лишь с одним плохим числом:

LCM42688800-23186745-8:7374757146451181145: 12, 12, 8, 12, 12, 12, 12, 12, 12, 12, 12, 12, 32, 64, 16, valids=11, maxlen=9

LCM42688800-19502041-4:4568948183281621252441: 8, 16, 8, 12, 12, 12, 12, 12, 12, 12, 12, 12, 4, 12, 12, valids=11, maxlen=9

[Huz]

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

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

Таким образом, схема выглядит так:
1. Исключаем паттерны с $8p^2$, можно прямым расчетом, можно кратким доказательством. Остаются паттерны с $32p$.
2. Для паттернов с $32p$ исключаем кубо-квадраты для всех паттернов. Прямым расчетом до верхней границы (до известной цепочки) в PARI/GP. При этом исключаются как паттерны с уже расставленными кубо-квадратами, так и паттерны, где кубо-квадраты могут возникать при переборе.
3. Для всех паттернов с $32p$ уменьшаем границу простых, которые подставляются в степенях, до $10^9$. Расчетом в PARI/GP.
4. Для "сложных" паттернов, отдельным расчетом под конкретный паттерн уменьшаем границу простых, которые подставляются в степенях, до $1..4 \cdot 10^6$. Расчетом в PARI/GP.
6. Считаем паттерны в pcoul с ключом для ограничения на простые (значение - из пункта 3 или пункта 4). Факторизации с $p^5$ все проверятся в pcoul, так как ограничения простых будет в любом случае выше, чем простое в пятой степени.

Thank you, this is a very useful summary. I will put a (translated) copy on the divrep wiki if that's ok with you.

It is also worth noting that the PARI code relies on additional proofs:
- after (1) above, not only must some $32p$ be in any chain of 10 or more, but also each of $32p-2, ..., 32p+2$;
- we require $p > 3$, so one of $\\{32p-2,32p+2\\}$ must be divisible by 3, and that value must be of the form $6q^2$ or $18q$.
I think there must be at least one more, since the code does not seem to allow for $6q^2$.

[EUgeneUS]

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

I will put a (translated) copy on the divrep wiki if that's ok with you.

Of course I don't mind.
But I would like to draw your attention to the fact that both ideas for acceleration were proposed by Dmitry. As for the text, in addition to translation, it will most likely require editorial changes.

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

I think there must be at least one more, since the code does not seem to allow for $6q^2$.

No, AFAIR, $6p^2$ is not possible in $32p-2$ or in $32p+2$. This is being proved, but I didn't immediately remember the details.
In the end, you can look at the list of patterns with $32p$ and make sure of this

[Dmitriy40]

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

we require $p > 3$, so one of $\\{32p-2,32p+2\\}$ must be divisible by 3, and that value must be of the form $6q^2$ or $18q$.

$6p^2$ is not allow in chains of length 10+:

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

$6p^2$.
Может быть только на чётных местах (нумерация здесь и далее относительно 32p). Места -6 и +6 запрещены так как тогда тройка попадёт на место 32p.
Места -4,-2,+2,+4: $6p^2=32x+\{-4,-2,+2,+4\}$ - недопустимы по модулю 8.
Итого: вариантов нет.

Цитата:

$6p^2$.
Can only be on even numbered places (numbering here and hereafter relative to 32p). Places -6 and +6 are forbidden because then 3 will fall on place 32p.
Places -4,-2,+2,+4: $6p^2=32x+\{-4,-2,+2,+4\}$ are not allowed by modulo 8.
Result: no options.

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

Сначала исправление неточности:

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

Места -4,-2,+2,+4: $6p^2=32x+\{-4,-2,+2,+4\}$ - недопустимы по модулю 8.

Место 32p-2 по модулю 8 допустимо, но зато недопустимо по модулю 32.

Цитата:

First, the correction of an inaccuracy:
Place 32p-2 in modulo 8 is acceptable, but not admissible in modulo 32.

-- 21.11.2022, 17:29 --

EUgeneUS
Пример извращения: потратив 31ч на уменьшение порога до 0.33e6 для b1952 (плюс 5.5ч на уменьшение с 2e10 до 1e9 если не сделано для всех, плюс 20м на проверку кубоквадратов для всех) потом его удалось проверить за 5.8ч:

T:\M12minimal\Hugo>pcoul -f11 -g3 -x1e22 -p33e4 -b1952 -v 12 11
001 pcoul(12 11) -p330000 -f11 -g3 -x10000000000000000000000 -b1952 *RT*
367 coul(12, 11): recurse 3199314730, walk 3419705215, walkc 12497747459 (20818.01s)

[Huz]

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

$6p^2$ is not allow in chains of length 10+:

Thanks. For the code being used, we require only $6p^2 \ne \pm 2 \pmod{32}$, and that is clearly correct. But it should be on the list as well.

[Dmitriy40]

Huz
Example of a glitch on the screen under windows:

T:\M12minimal\Hugo>pcoul -f11 -g3 -x1e22 -p3e5 -b2102 -v 12 11
001 pcoul(12 11) -p300000 -f11 -g3 -x10000000000000000000000 -b2102 *RT*
111111.1087^2 2 3 2^2 5.26597^2 2.3^2 7^2 2^5 3 2.5^2 23^2

111111 on the left should be 11, but not 111111.
It is only on the screen, in the logs is not noticed.
The reason is unclear, often the number is added when selecting and copying from the screen by system means (through the console menu of the window Select-Copy).

[EUgeneUS]

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

Пример глюка на экране под windows:

I have seen like this.
But the line was shifted only one position to the right. $223^2$ was displayed at the beginning of the line instead of $23^2$

[Huz]

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

stop=1e22; qrmin=13*2; qrmax=10000;\\Границы перебора решений и qr
...
pmax=sqrt(stop/qrmin); rmax=precprime(sqrt(qrmax));\\Перебирать меньшее из двух чисел q и r достаточно лишь до корня из максимума произведения
{forprime(p=0e9,pmax,
   M=stop/p^2; rr=min(rmax,M/13);\\Максимально безопасная граница перебора r
   forprime(r=2,rr,
      q0=max(qrmin/r,r+1); qq=min(qrmax,M)/r;\\Максимально безопасные границы перебора q
      forprime(q=q0,qq,
         h=p^2*q*r; nn=round(h/32); if(h>stop, break, !ispseudoprime(nn), next);\\Получаемая цепочка и начало её проверки
         h=nn*32; x=h%18;\\В h величина 32x
         if(x==2,   if(!ispseudoprime((h-2)/18) || numdiv(h+2)!=12, next);
         , x==16,   if(!ispseudoprime((h+2)/18) || numdiv(h-2)!=12, next);
         ,      next;\\Другие варианты исключены
         );
         if(numdiv(h-1)!=12 || numdiv(h+1)!=12, next);\\Все 4 числа вокруг 32x должны быть правильными
         WriteLog(p,q,r);\\Что-то нашли
      );
   );
)}

Some of the calculations of limits here are not clear to me, I hope Dmitry or Eugene can clarify.

I think the intention is to rule out $p^2$ for $p$ greater than some threshold "pmin", but that threshold does not seem to be set in the program. I suspect that I should read "qrmax=10000;" as an abbreviation of "pmin=1e9; qrmax=stop/pmin^2;".

I'm not sure if "0e9" in "forprime(p=0e9,pmax,..." is a typo or some PARI construct with a special meaning.

It is not clear why "qrmin=13*2;". I think there are some additional assumptions embedded here, but I'm not sure which ones. Why are we not interested in, for example, $166p^2$?

It is not clear why "rr=min(rmax,M/13);", I think this is perhaps another way of involving qrmin, but I don't understand it.

I think that if qrmax were derived from pmin as above it would guarantee M <= qrmax, so we can replace "qq=min(qrmax,M)/r;" with "qq=M/r;".

-- 21.11.2022, 15:16 --

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

Example of a glitch on the screen under windows:

Yes, this happens if you type a character in the console: it is echoed to the window, so everything shifts one character to the right.

You can fix it with backspace, or pause the program and resume. (On Linux you can pause with Ctrl-Z, then resume by entering the command "fg". I think under PowerShell you can do the same in Windows, not sure if there is an equivalent under the normal shell.)

[EUgeneUS]

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

But it should be on the list as well.

$6p^2$ is possible for patterns with $8p^2$ only, not for patterns with $32p$.

-- 21.11.2022, 19:07 --

Результаты тестового запуска. Паттерн b2155. Все три файла - с одного компьютера. Нагрузка на комп практически идентична.

Полные логи выложены на гуглодиске.

Небольшие куски:
"Типовой запуск"

001 pcoul(12 11) -f11 -g16 -x9887353188984012120346 -b2155 *RT*
305 13^2 2 3 2^2.7 5.2362174951^2 2.3^2 17^2 2^5 3.11^2 2.5^2 7^2 (598.30s)
...
305 19^5 2 3 2^2.7 5 2.3^2 . 2^5 3.11^2 2.5^2 7^2: 30416545 / 46770078 (315733.44s)
367 coul(12, 11): recurse 310062433, walk 310062960, walkc 7784821960 (315821.72s)

Ограничение простых до 1e9, -g16

001 pcoul(12 11) -p1:1000000001 -f11 -g16 -x9887353188984012120346 -b2155 *RT*
305 13^2 2 3 2^2.7 5.17^2 2.3^2 23^2 2^5 3.11^2 2.5^2 7^2: 1711644 / 4482247 (597.17s)
...
305 13^5 2 3 2^2.7 5 2.3^2 731752223^2 2^5 3.11^2 2.5^2 7^2 (136843.94s)
367 coul(12, 11): recurse 7447375944, walk 7447379243, walkc 11230460517 (137281.00s)

Ускорение 2.3 раза.

Ограничение простых до 1e9, -g3

001 pcoul(12 11) -p1:1000000001 -f11 -g3 -x9887353188984012120346 -b2155 *RT*
305 13^2 2 3 2^2.7 5.17^2 2.3^2 23^2 2^5 3.11^2 2.5^2 7^2: 223984 / 4482247 (597.62s)
...
305 17^5 2 3 2^2.7 5 2.3^2 . 2^5 3.11^2 2.5^2 7^2: 48311586 / 81562682 (158369.72s)
367 coul(12, 11): recurse 4119723010, walk 4119725076, walkc 31061305194 (158571.13s)

Ускорение 1.99 раза.

В полных логах видно, как в конце по-разному переключается алгоритм подстановки простых, и как это влияет на быстродействие.

[EUgeneUS]

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

think the intention is to rule out $p^2$ for $p$ greater than some threshold "pmin", but that threshold does not seem to be set in the program. I suspect that I should read "qrmax=10000;" as an abbreviation of "pmin=1e9; qrmax=stop/pmin^2;".

It's pmax in the code.

pmax=sqrt(stop/qrmin);

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

I'm not sure if "0e9" in "forprime(p=0e9,pmax,..." is a typo or some PARI construct with a special meaning.

AFAIU, $\text{0e9} = 0 \cdot 10^9 = 0$

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

It is not clear why "qrmin=13*2;". I think there are some additional assumptions embedded here, but I'm not sure which ones. Why are we not interested in, for example, $166p^2$?

qrmin=13*2 = 26

(I read also wrong earlier )

The last two questions, I hope, Dmitry will comment.