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

[Dmitriy40]

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

но запретил Пелль.

Пелль ничего не запрещает. Это численное решение уравнений.

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

Численные запреты я пока не обсуждаю, чтоб не напутать.

Однако возможно их проверить быстрее чем математические. Ну и Пелль ведь тоже численный.

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

Чётные проверяю только по модулю 64. Это правильно делаю?

Думаю да.

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

В ключах я мало что понимаю. А что Хьюго теперь предпроверку(фильтрацию) простых(на Асме) тоже делает?

Клюс -p ограничивает использование простых в квадрате (и в пятой степени) до указанной величины. Ключ -W делает то же самое, только за счёт предварительной проверки что простые в диапазоне от -p до -W действительно не дают решений. Они хоть и похожи по эффекту, но реализуются принципиально разными способами, потому и два разных ключа.
И нет, очевидно (зайдите на github Хуго и убедитесь) он делает это на C. Реализует ли компилятор векторные вычисления не знаю, не проверял (но сильно сомневаюсь, слишком код под них не заточен).

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

Как такое может быть, что Ваша прога не обгонит pcoul ???

Мои ускорители работают в линейном режиме, но если количество итераций для линейного перебора слишком мало (меньше порядка миллиона), то на компиляцию ускорителя времени уйдёт больше чем он выиграет.
Количество итераций Вы легко сами можете посчитать: LCM известен, домножаете на выбранные 5 или 6 простых в квадратах и получаете шаг проверки, делите порог (stop=2e33 для D12n14) на него и получаете количество итераций. По моему больше 90% затрат времени уходит на переборы с малым количеством итераций (простые то большие подставляются) и компиляция ускорителей может лишь замедлить, а оставшиеся 10% если и посчитаются ускорителями хоть мгновенно, то на общее время это повлияет не более тех же 10%.
Что будет если не запускать последний (или даже пару) глубокий квадратичный перебор и вместо него выполнить линейный перебор с ускорителями я не знаю, это надо внимательно проверять.

[Huz]

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

Планирую понизить границу простых до -p500.
Любые мысли и советы по этому поводу - приветствуются.

With recent versions of pcoul one can run with "-X" to have it report all results up to the specified maximum. It might be useful to use this to get statistics on a shorter chain such as $D(12,9)$, first to see how often additional chains appear above the smallest, and second to see how the maximum squared prime is distributed across them.

Results from that could be a useful guide for what parameters would be most effective in reducing the upper limit for $D(12,14)$. I would suggest experimenting with something very fast like $D(12,6)$ to work out a methodology, then using full runs of $D(12,9)$ or runs over a subset of patterns for $D(12,10)$ to get more realistic data.

For example, taking $m=D(12,6)$, a run up to $10^3m$ finds 306 distinct solutions. Grouped by powers of 2, they distribute as $(3, 0, 3, 5, 9, 9, 18, 49, 69, 141)$ where the first number implies 3 solutions in the range $m ... 2m-1$. I get that (in 170s) using:

./pcoul -x368431323000 -X -Ls0 12 6 | \
  perl -nle 'print $1 if /^202 Candidate (\d+)/' | \
  sort | uniq | \
  perl -nle '$s=log($_/368431323)/log(2); ++$a[$s]; END { print join " ", @a }'

I imagine you'd work with Pari rather than with perl, but the principle is straightforward.

[Yadryara]

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

Пелль ничего не запрещает. Это численное решение уравнений.

Тоже решили попридираться? Это бывает заразительно

Если у уравнения нет решений(окромя тривиальных) это и есть запрет.

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

D12n14

Кстати, отдельная благодарность, что заменили-таки M на D. Помните, сколько мы копий сломали. Разрастался диалог

Вот скажите как-то более по-простому. Прога Хьюго сильно изменилась с тех пор?

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

Ну, судя по его объяснениям и примеру с $T(6,3)$ (исходники не смотрел), товарищ пытается единым махом перекрыть все возможные низины, рекурсивно получая все возможные паттерны и выходя по каждому из них на примерно нашу же проверку (только не по isprime, а сразу по numdiv). Насколько корректно (перекрывая все возможности и строго по возрастанию чисел) генерятся паттерны я не смотрел.

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

выбранные 5 или 6 простых в квадратах

Но ведь под конец-то мы порой брали уже 4 доп. простых в квадратах. Так называемая вторая таблица. И время на компиляцию было намного-намного меньше времени счёта. Маруся месяц считала и дошла до 300е30.

[Dmitriy40]

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

Если у уравнения нет решений(окромя тривиальных) это и есть запрет.

В интересующих нас видах уравнений Пелля они имеют бесконечные серии решений. И наше счастье что этих решений до 8e34 всего с полсотни, а не триллионы.

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

Вот скажите как-то более по-простому. Прога Хьюго сильно изменилась с тех пор?

Очень сильно: вместо где-то года-двух проверки D12n12 оно проверилось за пару недель. Впрочем выше в теме была куча тестов скорости (про D12n11), поищите. Насколько помню там выходило что вместо 18-20 дней проверка паттерна занимала полсуток-сутки.

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

Но ведь под конец-то мы порой брали уже 4 доп. простых в квадратах. Так называемая вторая таблица. И время на компиляцию было намного-намного меньше времени счёта. Маруся месяц считала и дошла до 300е30.

Это я чуть выше и назвал исключением последнего квадратичного перебора.
Вот прикинул: $2\cdot10^{33}/LCM/(17\cdot19\cdot23\cdot29\cdot31\cdot37)^2=4.54\cdot10^6$, пока выгодно, но стоит увеличить любое простое вдесятеро (или все в полтора раза) и всё, выгода исчезает. И выходит выгоднее сразу исключить перебор 6-го простого, 6.2млрд итераций ускоритель выполнит секунд за 5-10, перебор же 6-го простого в квадрате будет где-то до 1e10-1e12, что намного дольше. И с увеличением первых 5-ти простых ускоритель будет выполняться быстрее, а квадратичный перебор нет.
Вообще похоже для D12n13 выигрыша от ускорителей особо не будет, линейные переборы слишком короткие, да и квадратичные не столь уж длинные. А вот для D12n14 и D12n15 линейные переборы уже в десятки миллионов и до миллиардов, тут ускорители могут сильно сэкономить время.

-- 23.12.2022, 22:25 --

Озадачился тут измерением скорости pcoul для D12n14 с малым -p, вот что получилось (время в секундах):

Используется синтаксис Text

                6+10    6+11    6+12            5+11    5+12
                b319    b392    b467            b74     b65
-p50 -x1e27     0.6     0.6     0.6             2.1     2.1
-p50 -x1e28     0.8     0.9     0.8             19      19
-p50 -x1e29     2.2     2.3     2.1             182     183
-p50 -x1e30     16      17      15              .       .
-p50 -x1e31     147     150     147             .       .

-p100 -x1e27    19      19      19              17      17
-p100 -x1e28    51      49      51              91      86
-p100 -x1e29    98      100     97              767     .
-p100 -x1e30    232     238     230             .       .
-p100 -x1e31    1243    .       .               .       .

-p150 -x1e27    78      76      77              65      63
-p150 -x1e28    194     188     186             192     193
-p150 -x1e29    482     .       .               1213    .

-p200 -x1e27    180     .       .               142     .

-p300 -x1e27    365     .       .               272     .

-p400 -x1e27    558     .       .               413     .

-p500 -x1e27    767     .       .               563     .

-p700 -x1e27    1200    .       .               870     .

-p1000 -x1e27   1770    .       .               1270    .

Видно что практически нигде кроме -p50 скорость не вышла на линейную, т.е. при таких небольших -x тормоза в квадратичных переборах, не линейных.
Ну и характерна разница на порядок между 6+ и 5+ вариантами (там где приблизилось к линейной зависимости от -x).

[Yadryara]

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

Впрочем выше в теме была куча тестов скорости (про D12n11), поищите. Насколько помню там выходило что вместо 18-20 дней проверка паттерна занимала полсуток-сутки.

Это я помню. Но разве эти ускорения не из-за предложенного Вами снижения порогов проверки(глобального и локального) ? Разве тот же эффект от снижения порога не может быть использован в Ваших прогах?

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

А вот для D12n14 и D12n15 линейные переборы уже в десятки миллионов и до миллиардов, тут ускорители могут сильно сэкономить время.

Вот именно! Ведь Евгений как раз 14-ку ищет. Так что конкретика интересна.

[Dmitriy40]

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

Это я помню. Но разве эти ускорения не из-за предложенного Вами снижения порогов проверки(глобального и локального) ? Разве тот же эффект от снижения порога не может быть использован в Ваших прогах?

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

[Yadryara]

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

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

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

То есть я просил сравнить как раз новый вариант Ваших прог с компиляцией на лету и автоматическим выбором метода (Асм или PARI).

А Вы сравнили старый, линейный вариант. И он всё равно оказался быстрее для 14-к и 15-к. Как я и думал.

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

Другое дело, если у Вас нет времени и/или желания делать эти новые варианты.

Тогда этим нужно заняться другим людям. Про Hugo я уже говорил. Евгению, например, раз уж он стал искать 14-ки.

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

А PARI я уже знаю гораздо лучше чем весной. Всё-таки три системы паттернов сделал.

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

[Dmitriy40]

Yadryara
Насчёт запретов паттернов.
Как мы недавно с Хуго выяснили решения могут быть только с $408<h=Ap^2<424\pmod{576}$, иначе или $32p$ не даёт $p=\pm1\pmod6$, или $18p$ не даёт $p=\pm1\pmod6$ или $h$ не влезает в цепочку:

len=lcm([32*6,18,12]); print1("Mod ",len,":");
{for(i=0,len-1,
   n=round(i/32); h=32*n; z=n%6; x=round(h/18)%6; y=round(h/12)%6;
   if(abs(i-h)>7 || (x!=1 && x!=5) || (z!=1 && z!=5) || (y!=1 && y!=5), next);
   print1(" ",i);
)}

Вывод:
Mod 576: 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423

Но такие значения $h=Ap^2$ нельзя получить ни с каким $p^2$ если перед ним будет коэффициент 10,21,22,27:

? foreach([10,14,15,21,22,3^3,5^3,7^3,11^3,13^3],qr, print1(qr,":"); forstep(p=1,576,2, x=(qr*p^2)%576; if(x>=409&&x<=423, print1(" ",p))); print)
10:
14: 21 27 69 75 117 123 165 171 213 219 261 267 309 315 357 363 405 411 453 459 501 507 549 555
15: 45 51 141 147 237 243 333 339 429 435 525 531
21:
22:
27:
125: 17 143 145 271 305 431 433 559
343: 39 53 57 107 135 153 181 231 235 249 327 341 345 395 423 441 469 519 523 537
1331: 119 137 151 169 407 425 439 457
2197: 23 41 247 265 311 329 535 553

А все коэффициенты из двух простых $14>q>r$ больше 22 и меньше 144 я запретил для цепочек длиной 12+ на 140-й странице темы.
$5^3p^2$ может быть только на 32p-3, но тогда на 32p+2 будет $10p^2$, что запрещено, так что $5^3p^2$ тоже запрещёно.
$7^3p^2$ может быть только на 32p-1, но тогда на 32p+6 будет $14p^2$, что запрещено, значит цепочек длиной 14+ с $7^3p^2$ нет.
Интересно есть ли у Вас в списках паттерны с $10p^2, 21p^2, 22p^2, 27p^2, 125p^2$?

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

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

Вообще-то ни в асм, ни в PARI компилятор таблиц для асм лезть не надо, там всё работает, надо написать обёртку (например на PARI). И в ней осталось сделать лишь корректно вызов рекурсии и (автоматическое) определение точки переключения режимов, и квадратичный перебор и линейный перебор и вызов компиляции ускорителя и его запуск уже есть и работают.

[Yadryara]

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

Как мы недавно с Хуго выяснили решения могут быть только с $408<h=Ap^2<424\pmod{576}$,

Перепроверю. Я вот спрашивал про модуль $192=64\cdot3$, а надо было ещё на 3 умножить: $576=64\cdot9$. Логично, молодцы.

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

Интересно есть ли у Вас в списках паттерны с $10p^2, 21p^2, 22p^2, 27p^2, 125p^2$?

Ну, $27p^2$ и $125p^2$ я исключил давно. Этих кубов ведь даже нет в моём списке проверяемых модулей, хотя другие кубы есть:

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

При переходе к 13-ке расширил список до

64, 3, 5, 7, 9, 11, 13, 25, 49, 121, 169, 243, 343, 1331, 2197, 16807, 161051, 371293.

Паттерны с остальными числами конечно пока есть.

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

Вообще-то ни в асм, ни в PARI компилятор таблиц для асм лезть не надо, там всё работает, надо написать обёртку (например на PARI).

Догадывался. Просто привычка, если уж разбираться, то досконально, чтоб каждая строчка была понятна.

[Dmitriy40]

Для цепочек длиной 13+ запретил все варианты $p^2 q r, 14>q>r$. Сложнее всего запретить $15p^2$, там семёрку некуда поставить.

[Yadryara]

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

Насчёт запретов паттернов.
Как мы недавно с Хуго выяснили решения могут быть только с $408<h=Ap^2<424\pmod{576}$, иначе или $32p$ не даёт $p=\pm1\pmod6$, или $18p$ не даёт $p=\pm1\pmod6$ или $h$ не влезает в цепочку:

Не-а. Проверял другим способом. Решения не только вокруг $416 \pmod{576}$, но и вокруг $160 \pmod{576}$.

Касаемо Вашей проги. У Вас ошибка вот здесь:

{for(i=0,len-1,

А надо было хотя бы на 2 умножить, а лучше на 6:

{for(i=0,6*len-1,

И как это Вас не насторожило, что $18p$ всё время слева, а $12p$ всё время справа от $32p$ ??

[Yadryara]

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

Проверял другим способом.

Проверял вот так:

{print();
u=[32,32,18,18,12,12]; 
print(u);print();
ost576=matrix(6,16,i,j,-1);
for(i=1,6,v=vector(576,n,-1);
for(j=1,576, x=(u[i]*(6*j+(-1)^i))%576; v[x+1]=x);
vres=setminus(Set(v),[-1]);
print1(u[i],"      ");
for(j=1,#vres, ost576[i,j]=vres[j];print1(vres[j]," "));
print();print());}
quit;

Ну а дальше просто глазками посмотрел и увидел, что нужное кучкование остатков происходит вокруг 160(N-паттерн) и 416(S-паттерн).

А если принять, что могут только вокруг 416-ти, то что же получается, Вы все N-паттерны запретили ?? А это примерно половина всех паттернов и непрерывные N-цепочки встречаются до 15-к включительно.

Ну и проверка для 153-167 показала, что $10p^2$, $21p^2$ и $22p^2$ пока вполне подходят.

[Dmitriy40]

Да, я был не прав.
Правильная проверка такая:

? len=lcm([32*6,18*6]); print1("Mod ",len,":");forstep(i=0,len-1,32,n=round(i/32);h=32*n;z=n%6;x=round(h/18)%6;if(abs(i-h)>7||(x!=1&&x!=5)||(z!=1&&z!=5),next);print1(" ",i);)
Mod 1728: 416 736 992 1312

[Yadryara]

Ну-у-у, зачем же нам 1728?

Пока что ни модуль 576, ни модуль 1728 вроде не помогают отбросить ещё хотя бы один паттерн. Как было 3704, так и осталось.

Но зато моя прога уже сгенерила паттерны и для 14-к, и для 15-к.

Итого, системы паттернов исчерпываются такими количествами паттернов:

$D(12, 11)$ — 1163 (1044);
$D(12, 12)$ — 578 (504);
$D(12, 13)$ — 3704 (3408);
$D(12, 14)$ — 1116 (1044);
$D(12, 15)$ — 528 (488).

В скобках количество основных(бесквадратных) паттернов.

Это не опечатка, ровно 1044 основных паттерна нашлись и для 11-к, и для 14-к.

Ещё буду перепроверять. Все-все найденные паттерны есть и у Хьюго.

Лишних, хоть и с $32p$ у Хьюго тоже хватает: 48, 36, 234, 156 и 102 для 11-15-к соответственно.

[Dmitriy40]

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

Ну-у-у, зачем же нам 1728?

Вот зачем: это более правильно математически; это в полтора раза ускоряет выполнение кода (допустимы 60/1728 комбинации против 30/576).


Забавное наблюдение: все квадраты $10p^2, 14p^2, 15p^2, 21p^2$ встречаются исключительно вместе. Т.е. в цепочках длиной 14+ они присутствуют все, а в цепочках длиной 13 квадрата $10p^2$ может и не быть, в цепочках длиной 10-12 может не быть и $21p^2$. А следовательно достаточно перебирать лишь один любой из них (для 14+), а не все. Впрочем у Хуго во всех паттернах для D12n14 они все и включены, отдельных не заметил, так что это наблюдение не для исключения паттернов, а для перебора без опоры на Пелля.