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

[Yadryara]

Продолжаю разбираться в вопросе. Синтаксис PARI всё ещё недостаточно знаю. Понял, но долго не мог привыкнуть к "==".

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

 i%37!=17

Что сие значит?

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

Отмечу, что каждая программа перебирает цепочки с одним и тем же шагом $2^63^3\prod_{i=3}^{12}p_i^2$.
Является ли он произвольным? Думаю, он оптимален.

Я совершенно не уверен в оптимальности. И пока работаю с гораздо меньшими шагами. Много всяких интересностей подмечено.

Но очень долго это описывать.

Посему, пока скажу только вот о чём. Порядок проверки на псевдопростоту в представленной Вами проге: 722, 2883, 2645, 18, 847, 32, 4107, 50, ...

Тогда как более оптимальным представляется 12, 18, 32, 45, 50, 98, ...

То есть сначала проверяем самые-самые огромные числа.

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

Разумеется, вероятность наткнутся на простое среди 38-значных выше, чем среди 40-значных (а поиск идет примерно в таком диапазоне). Но разнятся они несущественно.

Более внимательное рассмотрение показало, что отличие здесь ещё менее существенное, не в 100, а в 3.5 раза. То есть вместо 98 будет проверяться 28:

12, 18, 28, 32, 45, 50, ...

А вот отличие моей цепочки проверок от Вашей гораздо больше чем 100-кратное.

[VAL]

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

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

 i%37!=17

Что сие значит?

$i$ не сравнимо с 17 по модулю 37

Цитата:

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

Отмечу, что каждая программа перебирает цепочки с одним и тем же шагом $2^63^3\prod_{i=3}^{12}p_i^2$.
Является ли он произвольным? Думаю, он оптимален.

Я совершенно не уверен в оптимальности. И пока работаю с гораздо меньшими шагами.

Я уже приводил здесь аргументы и даже оценки. В чем Вы с ними не согласны?

Цитата:

Порядок проверки на псевдопростоту в представленной Вами проге: 722, 2883, 2645, 18, 847, 32, 4107, 50, ...

Тогда как более оптимальным представляется 12, 18, 32, 45, 50, 98, ...

То есть сначала проверяем самые-самые огромные числа.

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

[Yadryara]

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

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

Я совершенно не уверен в оптимальности. И пока работаю с гораздо меньшими шагами.

Я уже приводил здесь аргументы и даже оценки. В чем Вы с ними не согласны?

Вроде бы я аккуратно сформулировал. "Не уверен" и "не согласен" — разные вещи.

Я решал задачу трёх тел($37$, $31$ и $29$). И мне понадобился гораздо меньший шаг, чем $37^231^229^2$. Впрочем, для подробных объяснений время ещё не пришло.

[VAL]

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

"Не уверен" и "не согласен" — разные вещи.

Я не то, чтобы не согласен с этим утверждением, но не уверен, что согласен
А если серьезно, раз мои аргументы Вас не убедили, значит, к ним есть какие-то претензии. Это и имелось в виду.

[Yadryara]

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

А если серьезно, раз мои аргументы Вас не убедили, значит, к ним есть каки-то претензии.

Полагаю, что и я и Dmitriy40 стараемся в том числе и тщательно рассматривать Ваши наработки по задаче с разных сторон и под увеличительным стеклом, в надежде хоть как-то уменьшить перебор и/или увеличить его скорость. Плюс исследуются и другие подходы.

[Dmitriy40]

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

Полагаю, что и я и Dmitriy40 стараемся в том числе и тщательно рассматривать Ваши наработки по задаче с разных сторон и под увеличительным стеклом, в надежде хоть как-то уменьшить перебор и/или увеличить его скорость. Плюс исследуются и другие подходы.

Не то чтобы я рассматривал наработки, мне интереснее самому разобраться. И после этого переписать на нормальном языке с глубокой оптимизацией под скорость.
Пока ни одна из моих идей толку не дала, остаётся оптимизировать линейный перебор $n$ (или $p$ как у VAL, что одно и то же). О первой попытке я уже писал, оно работает, но есть и следующая мысль: полностью отказаться от умножений и делений и переходить к следующему $n$ одновременным вычислением всех интересующих остатков по малым простым. Это делается лишь сложениями (и сравнениями), которые во первых весьма быстры, во вторых все числа малы по величине, и в третьих потому позволяют задействовать AVX — и ориентировочно в среднем за 10 тактов получать факт делимости 400 чисел на малые модули, например проверить делимость 10-ти чисел на 40 первых простых, т.е. эффективно исключить огромное множество точно неподходящих вариантов со скоростью порядка 300млн/с ($10^{12}$ в час). Замечательно что при этом величина самих чисел вообще не важна, все операции кроме начальной настройки производятся в поле (кольце?) модулей. Т.е. я знаю на уровне идеи как это написать, аналогичное уже было написано и использовалось при поиске магических квадратов, осталось сесть и написать всё, включая самое главное — правильную инициализацию процесса перебора. Но тут работы навалилось и свободного времени нет ...

VAL
Никак у меня не дойдут руки детально проанализировать собранную статистику о пользе подстановки в модуль квадратов простых. Уже неделю лежит. Потому выложу как есть, лишь с небольшими комментариями.
Исследовалось на простом модельном паттерне без оптимизирующих проверок на делимость на малые простые — всё ради более частого выполнения условий делимости и псевдопростоты, для набора статистики. Паттерн следующий:

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

\\      n+0     n+1     n+2     n+3     n+4     n+5     n+6     n+7     n+8     n+9     n+10    n+11    n+12    n+13    n+14
\\%32:  %25     %26     %27     %28     %29     %30     %31     %0      %1      %2      %3      %4      %5      %6      %7
\\Без подстановки 2645:
? v=[   1,      722,    1,      1,      1,      1,      1,      32,     1,      1,      1,      1,      1,      98,     1       ]; pp=Mod(25,64); for(i=1,#v, pp=chinese(pp,Mod(-i+1,v[i]))); print(pp);
Mod(188441, 1132096)
\\С подстановкой 2645:
? v=[   1,      722,    1,      1,      2645,   1,      1,      32,     1,      1,      1,      1,      1,      98,     1       ]; pp=Mod(25,64); for(i=1,#v, pp=chinese(pp,Mod(-i+1,v[i]))); print(pp);
Mod(2807786521, 2994393920)

В остальном программа не отличалась (специально сделал похожей на Вашу):

{n0=0; n1=0; n2=0; n3=0; n4=0; n5=0; mm=pp.mod/722; st=(ceil(1e40/pp.mod)*pp.mod+lift(pp)+1)/722;
for(i=0,10^9-1,
   p=st+i*mm; n0++;
   if(!ispseudoprime(p), next);
   n=722*p-1; n1++;
   if(ispseudoprime((n+7)/32) && ispseudoprime((n+13)/98),
      n2++; if((n+4)%2645==0, n3++; if(ispseudoprime((n+4)/2645), n4++)); if(numdiv(n+4)==12, n5++); DispIf(n);
   );
);
print("Num=",n0,", prime19=",n1,", test=",n2,", div=",n3,", prime=",n4,", numdiv=",n5);}
\\Для проверки, без подстановки 2645:
10000000000000000000000000092932350135321: 16, 12, 16, 12, 12,192, 12, 12, 64, 16,128, 12, 32, 12, 48,  len=7
10000000000000000000000000357301276013721: 32, 12, 16, 12, 12, 12,  8, 12, 64,128, 12,384, 32, 12,192,  len=7
10000000000000000000000000560136707614425: 12, 12, 16, 12, 12,128, 64, 12, 16,  4,  4, 24,  8, 12, 12,  len=7
\\Для проверки, с подстановкой 2645:
10000000000000000000000156142307231891481:  8, 12, 32, 12, 48, 12, 32, 12,  8, 32, 12, 48,  4, 12, 12,  len=7
10000000000000000000000405361329400792601: 12, 12,  8, 12, 12,384,128, 12, 16,384, 16, 12, 16, 12,  8,  len=7
10000000000000000000000616302211592763161: 12, 12, 16,144, 12, 16,128, 12,  4,192, 16, 12, 64, 12, 12,  len=7
10000000000000000000000741907170008796761: 12, 12, 32, 12,384, 16,512, 12, 12,128, 32, 96, 16, 12, 12,  len=7
10000000000000000000001141901139544651161:  8, 12, 16, 12, 12, 32, 16, 12, 24,256, 12, 12, 16, 12, 96,  len=7
10000000000000000000001836845425491398361:  8, 12, 16, 12,192, 64, 32, 12, 12, 32, 12, 12, 32, 12,128,  len=7
10000000000000000000002121610475675076761: 16, 12,  8, 12,192, 32, 12, 12, 32,512, 16, 12, 16, 12, 12,  len=7
10000000000000000000002245404559396020761:  8, 12,  8, 12, 12, 32,128, 12, 16, 64,  4, 12, 32, 12, 12,  len=7
10000000000000000000002387807124469169561: 12, 12,  8, 12, 96, 32, 64, 12, 16,256, 32, 12, 32, 12, 12,  len=7
10000000000000000000002664845485497588761: 48, 12, 12, 12,128, 16, 96, 12, 16,128, 16, 12, 32, 12, 12,  len=7

Объём перебора составил $10^9$ разных $p$ в $n=n_0+722pm$ с наименьшим подходящим $n_0>10^{40}$.
Проверялись следующие величины (без подстановки 2645 / с подстановкой 2645):
1. Количество $p$ (т.е. возможных цепочек) на проверку: 1000000000 / 1000000000 (разницы очевидно быть и не должно, оставлено для контроля).
2. Сколько из них оказались простыми (ispseudoprime(p)): 27284151 / 35653087 — разница вызвана разными $n_0$ и $m$.
3. Сколько из них проходит тест на простоту после деления на 32 и 98 (и требуют дальнейшей проверки на количество делителей прочих чисел): 29392 / 83768. Все они отправлялись на вычисление делителей всех чисел (выполнялось в DispIf()) для пунктов 6 и далее.
4. Сколько из них оказывается кратными 2645 на месте $n+4$: 29 / 83768 (вторая цифра очевидна, оно так по построению).
5. Сколько из них после деления оказались простыми: 3 / 3426.
6. Длины трёх найденных цепочек без подстановок: 4,6,4 — только в одной из трёх ещё какие-то позиции тоже дали ровно 12 делителей.
7. Сколько из цепочек из пункта 3 (т.е. прошедших проверку на прочие числа, но до проверки на 2645) дали ровно 12 делителей на месте $n+4$: 490 / 3426 (вторая цифра опять очевидна по построению).
8. Максимальная длина найденных цепочек после прохождения пункта 3: 7 / 7, 3 и 10 штук соответственно (все приведены в листинге программы). Причём пункт 4 прошли лишь 4 цепочки из варианта с подстановками, т.е. в остальных на месте $n+4$ стоит какое-то другое не кратное 2645 число.
9. Количество найденных цепочек длины 6: 80 / 236.
10. Из-за большой разницы чисел в пункте 3 и соответственно сильно разным временем работы вариантов теста отдельно проверялось влияние служебных операций на время работы, на сокращённом переборе в $10^7$ разных $p$ с удалённой строкой кода правее n2++ время счёта составило: 36.2с / 45.5с. Влиянием инкремента счётчиков пренебрёг. Практически всю разницу можно списать на разное количество простых в диапазонах в пункте 2.

Предварительные выводы.
Из пункта 3 следует что на каждые миллиард цепочек лишь от 30 до 85 тысяч требуют дополнительной проверки на количество делителей прочих чисел, в зависимости выполнялась или нет соответственно подстановка квадратов малых простых в паттерн с увеличением модуля. Именно этот результат в общем и интересовал.
Из него же следует что любая дополнительная проверка займёт в общем времени работы долю $10^5/10^9=10^{-4}$ или менее 0.01%. Даже если она будет в сто раз дольше первых проверок, всё равно общее замедление составит лишь 1%, что считаю явно несущественным. Т.е. добавление проверок на не подставленные квадраты простых в первом варианте на общем времени работы сказываться практически не должно.
Из разницы для первого варианта цифр в пунктах 5 и 6 видно что в 487 цепочках из 490 на месте $n+4$ стоит другая допустимая комбинация простых, не 2645q. Ограничение перебора лишь кратными 2645 приводит к сокращению находимых цепочек на два порядка. Вероятно примерно аналогичные цифры будут и для других подставляемых чисел. Но важность этого вывода весьма спорна, ведь пункты 8 и 9 показывают что после подстановки количество кандидатов выросло втрое.
В итоге ситуация двойственная: с одной стороны без подстановки найдено на два порядка больше разных кандидатов в каждом конкретном месте паттерна, с другой стороны на всех 15-ти местах кандидатов втрое меньше. Плюс подстановка приводит к росту чисел и замедлению работы PARI. Что полезнее реально я не понимаю. На первый взгляд очевидных кардинальных преимуществ нет ни у одной из сторон.
Ну и никаких отличий в $10^{17}$ не обнаружено. Возможно из-за слишком простого метода проверки и маленького объёма перебора.

[VAL]

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

Ну и никаких отличий в $10^{17}$ не обнаружено.

Пересчитал аккуратнее (не по одной позиции, а по всем). $10^{17}$ действительно не получается. Получается $10^6 - 10^{7}$.

Про быструю вероятностную проверку с помощью модульной арифметики, является ли число квадратом, знаю (есть у Кнута во втором томе). Но не уверен, что это приведет к убыстрению. Во-первых, событие остается редким. А во-вторых, в случае положительного ответа придется еще проверять, будет ли это квадрат простого числа.

Больше доверия вызывают Ваши идеи ухода от PARI к чему-то более быстрому.

[Yadryara]

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

Отмечу, что каждая программа перебирает цепочки с одним и тем же шагом $2^63^3\prod_{i=3}^{12}p_i^2$.
Является ли он произвольным? Думаю, он оптимален.

Да, похоже что меньший шаг в итоге не годится. При постепенном переходе от системы трёх тел к полноценной звёздной системе с 14-ю планетами, был момент, когда пришлось увеличить шаг сразу в 64 раза. А подходящие числа стали встречаться в 768 раз реже.

Я тоже пока не могу понять, почему в шаге $3^3$, а не $3^2$, но это работает.

Кстати, Dmitriy40, похоже, что Вы вместо "шаг" говорите "модуль". И довольно трудно всё же воспринимать Ваш текст. Понятно, что Вы понимаете о чём пишете. Но понимают ли другие...

Всё-таки самостоятельно нашёл $9$ (а не $6$) чисел по $12$ делителей. Первое число — $561669046047030331487641$.

Итак, всё же придётся искать целых $11$ огромных простых. А что мы про них знаем?

$5$ из них точно дают произведения: $12p_1$ , $18p_2$ , $32p_3$ , $45p_4$ , $50p_5$. Например, про самое большое, $p_1$ известно, что три последних десятичных цифры не выходят за пределы этого набора: $029$, $171$, $179$, $221$, $371$, $379$, $421$, $429$, $571$, $579$, $621$, $629$, $779$, $821$, $829$, $971$.

На самом деле известно больше, но мне это пока лень расписывать.

А 6-е простое вроде бы лучше брать всё-таки $28p_6$ , а не
$98p_6$. То есть всё-таки ставить 7-ку на 4-е либо 12-е место. Ибо подходящих простых в этом случае пока находится в $4$ раза больше. Опять-таки, подробнее пока не буду.

[VAL]

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

Я тоже пока не могу понять, почему в шаге $3^3$, а не $3^2$

Потому что среди 27 последовательных чисел, есть два, кратных 9, но не 27. Они-то нам и нужны. А число, кратное 27, нам только мешает.

[Yadryara]

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

А 6-е простое вроде бы лучше брать всё-таки $28p_6$ , а не $98p_6$. То есть всё-таки ставить 7-ку на 4-е либо 12-е место. Ибо подходящих простых в этом случае пока находится в $4$ раза больше.

Попытаюсь объяснить, что имею в виду. Я решил зайти с другой стороны, сделав перебор 6-ти самых больших простых и посмотреть какими они могут быть.

Сначала использовал forprime, потом более быструю конструкцию, пока взяв шаги по остаткам по модулю $1000$.

{ print(); k = 0; j=0; i=29; c=vector(16);
 c[1]= 142; c[2]= 8; c[3]= 42; c[4]= 150; c[5]= 8; c[6]= 42; c[7]= 8; c[8]= 142; c[9]= 8; c[10]= 42;  c[11]= 8;
 c[12]= 150; c[13]= 42; c[14]= 8; c[15]= 142; c[16]= 58;

for ( j = 0, 10^10, 
if ( isprime(i) && isprime(round(i*2/3)) && isprime(round(i*3/8)) && isprime(round(i*4/15)) && abs(i*12 - round(i*4/15)*45)<>21 && isprime(round(i*6/25)) && isprime(round(i*3/7)) ,
k = k + 1; print(k, "   ", i, "   ", i*12 - round(i*2/3)*18 ,"   ", i*12 - round(i*3/8)*32,"   ", i*12 - round(i*4/15)*45, "   ", i*12 - round(i*6/25)*50 , "   ", i*12 - round(i*3/7)*28 ); print();)
; ind = j%16 + 1; i = i + c[ind];  )  }

Выдача:

1   131779   -6   4   3   -2   -8

2   51669971   6   4   -3   2   8

3   58378429   -6   -4   3   -2   -8

4   140827571   6   4   -3   2   8

Слева то самое большое простое $p_1$, а справа разности $12p_1 - 18p_2$, $12p_1 - 32p_3$, ..., $12p_1 - 28p_6$.

Как видим, разности получаются те самые, что и должны быть в нашей искомой 15-шке. То есть все простые попадают на свои места.

Теперь запущу ту же прогу, заменив везде $28p_6$ на $98p_6$. Что эквивалентно перемещению 7-ки с мест 4 и 12, на места 7 и 9.

{ print(); k = 0; j=0; i=29; c=vector(16);
 c[1]= 142; c[2]= 8; c[3]= 42;
 c[4]= 150; c[5]= 8; c[6]= 42; c[7]= 8;
 c[8]= 142; c[9]= 8; c[10]= 42;  c[11]= 8;
 c[12]= 150; c[13]= 42; c[14]= 8;
 c[15]= 142; c[16]= 58;

for ( j = 0, 10^10, 
if ( isprime(i) && isprime(round(i*2/3)) && isprime(round(i*3/8)) && isprime(round(i*4/15)) && abs(i*12 - round(i*4/15)*45)<>21 && isprime(round(i*6/25)) && isprime(round(i*6/49)) ,
k = k + 1; print(k, "   ", i, "   ", i*12 - round(i*2/3)*18 ,"   ", i*12 - round(i*3/8)*32,"   ", i*12 - round(i*4/15)*45, "   ", i*12 - round(i*6/25)*50 , "   ", i*12 - round(i*6/49)*98 ); print(); )
; ind = j%16 + 1; i = i + c[ind];  )  }

Выдача:

1   23969629   -6   -4   3   -2   -38

2   143750179   -6   4   3   -2   -26

3   276030829   -6   -4   3   -2   34

4   660537971   6   4   -3   2   -46

5   813096829   -6   -4   3   -2   2

Опа! Сначала разности не получаются те самые, которые должны быть в нашей 15-шке. В конце-то $\pm 2$-ка должна стоять. Но только с 5-й попытки все простые попадают на свои места.

Когда $p_1$ достигает 10 миллиардов, то находится только 13 таких $\pm 2$-к.

А первая программа на том же отрезке находит 64 необходимых $\pm 8$-к. И только их. Вот это и есть 4-кратное превосходство такой расстановки.

В дальнейшем преимущество сильно возрастает и уже на отметке в 50 миллиардов доходит до 8-кратного: уже 207 против 24.

Экстраполировать на наш диапазон простых ($10^{25}-10^{38}$) пока не берусь, но надежды радужные.

[Dmitriy40]

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

c=vector(16);
c[1]= 142; c[2]= 8; c[3]= 42; c[4]= 150; c[5]= 8; c[6]= 42; c[7]= 8; c[8]= 142; c[9]= 8; c[10]= 42; c[11]= 8; c[12]= 150; c[13]= 42; c[14]= 8; c[15]= 142; c[16]= 58;

Это можно сделать короче:

c=[142,8,42,150,8,42,8,142,8,42,8,150,42,8,142,58];

Ещё совет: ispseudoprime на больших числах (начиная от $2^{64}\approx1.8\cdot10^{19}$) сильно быстрее isprime:

? a=10^20; w=10^6;
? print1("isprime(): "); gettime(); n=0; forstep(p=a+1,a+w,2, n+=isprime(p)); printf("%0.2fs, n=%d\n", gettime()/1e3,n);
isprime(): 17.89s, n=21632
? print1("ispseudoprime(): "); gettime(); n=0; forstep(p=a+1,a+w,2, n+=ispseudoprime(p)); printf("%0.2fs, n=%d\n", gettime()/1e3,n);
ispseudoprime(): 1.12s, n=21632

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

Я тоже пока не могу понять, почему в шаге $3^3$, а не $3^2$, но это работает.

Ещё это можно так объяснить: из каждых трёх последовательных шагов на двух из них какое-то число (может и не одно) после деления на заданное число (18,32,98,50,45,12 и остальные) обязательно разделится ещё и на три, т.е. окажется составным. Потому можно или проверить условие типа if(i%3==2, (аналогично проверке условий на простые от 5 до 37 в выложенной VAL программе), или сразу увеличить шаг втрое с коррекцией при необходимости начального числа.

Кстати отдельный вопрос почему в шаге $2^6$ вместо $2^5$, но тут объяснение может быть проще (хотя и предыдущее про $3$ тоже подходит): надо чтобы при делении на $32$ получалось нечётное число ибо чётными простые быть не могут (а $2$ уже задействована).

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

Кстати, Dmitriy40, похоже, что Вы вместо "шаг" говорите "модуль".

Поясню: любое решение $n=n_0+km$, где $n_0$ начальное число и $m$ шаг, будет равно начальному числу по модулю шага: $n=n_0+km \to n=n_0 \bmod m$.
К тому же PARI позволяет прямо из массива расстановок (который стараюсь звать паттерном) получить сразу правильные и $n_0$ и $m$ (правда не увеличенные в 6 раз):

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

? \\    n+0     n+1     n+2     n+3     n+4     n+5     n+6     n+7     n+8     n+9     n+10    n+11    n+12    n+13    n+14
? v=[   17^2,   722,    2883,   1,      2645,   18,     847,    32,     4107,   50,     29^2,   12,     13^2,   98,     45      ];
? pp=Mod(0,1); for(j=1,#v, pp=chinese(pp,Mod(-j+1,v[j]))); print(pp);
Mod(106022957662445288229350041, 440538835723387181869888800)
\\n=106022957662445288229350041+440538835723387181869888800*i

Тоже явно видна отсылка к понятию модуля.
Ну и у меня в программе внутренний цикл разворачивается и шаг проверки становится не равен и даже не кратен модулю $m$ и вообще переменным. Аналогичное условие if(i%5!=1 && i%7!=2 && i%11!=5 && i%13!=4 && i%17!=0 && i%19!=4 && i%23!=4 && i%29!=11 && i%31!=9 && i%37!=17, в выложенной VAL программе тоже приводит к переменному шагу проверки последующими командами ispseudoprime.
Вот потому и предпочитаю модуль вместо шага так как модуль привязан к исходному размещению чисел (паттерну), а шаг зависит от конкретной реализации программы. Но это конечно на мой вкус, согласен.

Кстати, до кучи, сразу добавлю наблюдение об эффективности указанного условия на индекс в выложенной программе на числах около $10^{40}$: из $10^6$ последовательных индексов i проверку на делимости прошли и попали на первую ispseudoprime 446173 индекса, после которой осталось 35048 индекса. 44% от величины чисел не зависит, а 3.5% постепенно уменьшается с ростом чисел, но весьма медленно (логарифм, понятное дело).

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

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

...кстати у Вас неточность для модулей больше $11$, там надо не по одному $i$ исключать, а по 7 разных

Почему?

Кстати тут я был не прав, если смотреть на запрещенные значения именно для полного паттерна (с вставленными всеми квадратами простых), то для всех использованных простых (кроме 2 и 3 понятно) будет ровно один запрещённый вариант. В этой части беру свои слова назад и извиняюсь за некорректный (поспешный) совет.
Вот для больших простых вывод остаётся верен, там по 14 (для 14-ти занятых позиций в паттерне) запрещённых вариантов индекса. И проверив их можно сильнее ускорить программу чем проверяя делимость на простые до 37 (например $5/4=1.2500 < 41/27=1.5185$, $7/6=1.167 < 43/29=1.483$).
Как коварно Вы промолчали и оставили разбираться самому ...

(PS. Информация о ходе дел.)

Программу быстрой проверки делимости чисел (для проверки на псевдопростоту) с использованием AVX2 написал (на ассемблере), скорость замерил, выигрыш от выложенной программы на том же паттерне без учёта последующих тормозов PARI с верификацией найденных кандидатов составил 600 раз, с учётом снизится до 300 раз (прикидка, ещё не проверил). Из миллиона индексов остаётся на валидацию в PARI примерно 1070, многовато (потому и ускорение вдвое снижается), думаю как ещё уменьшить. Осталось исправить мелкие ошибки (выдаёт чуть больше чисел чем должна ) и сделать распараллеливание на все доступные ядра (или явно указанное количество) и можно выкладывать.
От величины чисел не зависит, их на вход просто не получает, работает исключительно в поле вычетов (модулей) по малым простым. Единственное ограничение: в $n=n_0+km$ должно быть $k<2^{64}$ (сделать до $2^{128}$ тоже не слишком сложно). Ни $m$ ни $n_0$ при работе не используются и могут быть любой величины (нужны лишь на этапе компиляции для правильного формирования таблиц). Под каждый вариант расстановки чисел в паттерне программа к сожалению своя. Генератор таблиц (на PARI) сделал, ручного "допиливания" для оптимизации скорости требует совсем чуть. Размер файла exe от сотни килобайт до пары мегабайт, больше не делаю специально: выигрыш скорости мал, а "засирание" кэша L3 резко тормозит всю остальную систему несмотря на все ухищрения с приоритетами и отдачей управления системе. По желанию (например для VAL с 64М L3) можно и увеличить, настраивается в генераторе таблиц на PARI.

[Yadryara]

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

Это можно сделать короче:

c=[142,8,42,150,8,42,8,142,8,42,8,150,42,8,142,58];

Спасибо. Я, правда, с целью ускорения уже перешёл к перебору по остаткам по модулю 2000. Поэтому 16 прибавок почти все другие:

c = [150,42,150,58,150,42,208,342,208,42,150,58,150,42,150,58];

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

Ещё совет: ispseudoprime на больших числах (начиная от $2^{64}\approx1.8\cdot10^{19}$) сильно быстрее isprime

Уже замечал, спасибо.

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

Ещё это можно так объяснить:

Да-да, это всё я уже раньше понял, поэтому и вопросов больше не задавал. Но Ваше подробное объяснение может пригодиться другим.

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

Вот потому и предпочитаю модуль вместо шага так как модуль привязан к исходному размещению чисел (паттерну), а шаг зависит от конкретной реализации программы. Но это конечно на мой вкус, согласен.

На самом деле базовый шаг остаётся прежним для всех подобных программ: $2643233014340323091219332800 \approx 2.6 \cdot 10^{27}$.
Именно поэтому искомая пятнашка не может содержать менее чем 28-значные числа. В рамках КМК37, конечно.

Вы теперь уже признаёте, что дальнейшие поиски надо прежде всего вести в рамках Концепции Минимальных Квадратов, с наибольшим подквадртным числом — 37 ?

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

18,32,98,50,45,12 и остальные

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

А кроме того, у меня много (порядка двух тысяч) программок. И в большинстве 7-ка стоит на 7-м или 9-м местах

Ну вот и я клоню к тому, чтобы отказаться от 98, то есть ставить 7-ку только на 4-е или 12-е места, то есть пока как раз отказаться от большинства, а значит, по меньшей мере вдвое, сократить перебор. Прошу вас обоих изучить мои аргументы.

Теперь, на отметке 130 миллиардов, счёт 397:48. То есть 8-кратное превосходство 28 над 98 пока сохраняется.

[Dmitriy40]

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

Прошу вас обоих изучить мои аргументы.

Насколько я понял у VAL и так используются все возможные варианты размещения чисел, именно поэтому более двух тысяч программ. Если запускать их с преимуществом одних перед другими ... Ну может быть.
А мои усилия направлены вообще в другую сторону — я пишу универсальную программу, которой всё равно что за сотни чисел там проверяются на псевдопростоту. Хоть 14 чисел, хоть 44, хоть слева направо, хоть наоборот, хоть вперемешку — она их просто проверит на делимость на первые простые и всё. Ни о каких вариантах размещений ей дела нет, это регулируется таблицами остатков, которые она использует при работе и которые рассчитываются другой программой (на PARI) один раз по заданному паттерну (варианту размещения чисел в цепочке). Например выложенный (см. ниже) вариант программы проверяет делимость 14-ти чисел на первые 54 простых (до 256), это 756 проверок для каждого варианта цепочки, оставляя вероятно подходящим лишь в среднем 1 из 6000 индексов $k$ в $n=n_0+km$.


Тем временем я исправил ошибки, проверил правильность работы и довёл до нормального для публикации состояния. Не идеал, но уже нормально работающее (во всяком случае у меня ).
Выкладываю: https://cloud.mail.ru/public/7K8X/ssgsFeie7
Архив с файлом exe и двумя примерами программ на PARI, одна как образец использования и измерения скорости, вторая чуть модифицированная программа VAL для сравнения (и скорости и правильности работы).
Честно предупреждаю: Virustotal на exe ругается: https://www.virustotal.com/gui/file/1dd ... 3540aab792
Но это честно не моя проблема, вирусов там не должно быть, скомпилено из асм исходника. Ну и вот есть пояснение что "Win64:Evo-gen [Susp]" не совсем вирус: https://forum.ixbt.com/topic.cgi?id=22:86228
В общем на ваше усмотрение, доверять или игнорировать.

Перед использованием очень рекомендую прочитать ReadMe.txt из архива! Не зря же я его писал.

Что сказать, ускорение перебора 600 раз после интеграции в PARI снизилось до 200 раз ... Печалька.
Запущенная проверка за 15 минут добралась с нуля до $n>10^{38}$ и нашла лишь три десятки (10 чисел из 15 имеют ровно 12 делителей), более короткие не считаю.

Yadryara, VAL
Если объясните какие числа на каких позициях Вы ставите, то могу скомпилить exe и под ваш вариант.
И под любой другой, главное понятно (мне) объяснить что где.
В принципе могу и несколько тысяч вариантов скомпилить, только надо исходные данные в понятном виде (и лучше удобоваримом для вставки в PARI). Включая например "а вот на этих местах выполнить все возможные перестановки". Генератору таблиц на вход нужен вектор v[] как в выложенных выше примерах.
Это конечно если работа программы устроит.
Если не устроит, то жду предложений/возражений/замечаний/глюков.

[Yadryara]

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

Если запускать их с преимуществом одних перед другими ...

А есть ли это преимущество? Может я где-то ошибся и чего-то не учёл.

Да, и новые подсчёты по-прежнему показывают, что при прочих равных подходящие простые для $98p$ встречаются в 8 раз реже, чем для $28p$. И я уже стал подозревать, что имеется принцип наименьших множителей и надо распространить его и на другие числа.

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

Если объясните какие числа на каких позициях Вы ставите, то могу скомпилить exe и под ваш вариант.

Тогда предлагаю попробовать, например, такой паттерн.

45p 722p 841qr 12p 49qr 50p 507p 32p 961qr 18p 605p 28p 867p 1058p 1369qr

Слева направо перечислены конструкции для мест $1...15$ соответственно. Здесь $p$ — 11 разных огромных простых и $qr$ — 4 пары различных простых. Вроде бы выбрал самые маленькие множители. Но в законности такого расположения немного сомневаюсь.

[VAL]

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

Если объясните какие числа на каких позициях Вы ставите, то могу скомпилить exe и под ваш вариант.
И под любой другой, главное понятно (мне) объяснить что где.

Спасибо за предложение!
С удовольствием воспользуюсь. Если это действительно даст то ускорение, которое Вы обещаете, искать добровольцев не потребуется.

Но сначала попробую разобраться с тем, что тут за выходные понаписали. Я за вами не успеваю
А то я даже пока не понял, что вы предложите для запуска: exe'шник или программу на RARI