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

[Yadryara]

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

На самом деле в рассматриваемом паттерне 98 стояло в 14-й. А частотность вполне себе верная.

$\dfrac{694+679+673+666+700+690+672+724}8\approx687$

На 16% меньше чем для 28. Такой результат?

[VAL]

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

Если одни варианты действительно имеют приоритет над другими, перебор сократится ...

Конечно, варианты не абсолютно равновероятны. Но разницы в разы, как мне представляется, нет. При этом дисперсия довольно высока. Как следствие, искомый набор вполне может раньше встретиться для паттерна, не являющегося лидером с точки зрения вероятностной оценки.

Приведу один классический и один сногсшибательный пример.

1. Конечно тройки последовательных чисел, имеющих в точности 6 делителей, встречаются гораздо реже, чем четверки. И тем не менее первая четверка встречается в натуральном ряду намного раньше, чем первая чистая (без четвертого числа) тройка.
Первая четверка начинается с числа 242. А первая чистая тройка начинается с числа 603.

2. Будем рассматривать арифметические прогрессии с шагом 6, все элементы которых имеют по 4 делителя.
Если $n$ не превышает 186778, максимальная длина такой прогрессии не больше 9. А прогрессия, начинающаяся с 186779 содержит сразу 15(!) чисел, имеющих в точности 4 делителя.

-- 22 фев 2022, 20:49 --

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

$\dfrac{694+679+673+666+700+690+672+724}8\approx687$

На 16% меньше чем для 28. Такой результат?

Корректнее сравнивать не отдельные числа, паттерны в целом. А там выигрыш в одной позиции вполне может уравновесится проигрышем в другой.

Вот если Вы (или кто-то другой) найдете паттерн, который дает убедительное суммарное превосходство...
Тогда другое дело.
Я много времени убил на такой поиск. И несколько раз казалось, что нашел. Эмпирическое мат. ожидание успеха для двух паттернов, испытанных на одном и том же участке (10000 наборов) отличалась не на 16%, а раз в 5-6. Ура!?
Но стоило испытать те же паттерны на слегка смещенном диапазоне и весь эффект исчезал.

[Yadryara]

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

Если $n$ не превышает 186778, максимальная длина такой прогрессии не больше 9.

Да ладно! А как же 18799 или 60499 ??

[VAL]

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

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

Если $n$ не превышает 186778, максимальная длина такой прогрессии не больше 9.

Да ладно! А как же 18799 или 60499 ??

Уговорили 12, а не 9 (я почему проверил только числа вида $6k+5$, а не $6k+1$

[Dmitriy40]

VAL, Yadryara
А тем временем расширил список проверяемых простых, не до $2^{16}$, но до $2^{15}$ при желании. Фильтровать стала на порядок лучше. Но разумеется замедлилась, хотя за счёт качества фильтрации снизившееся с 200 до 55 раз ускорение при сокращении проверяемых чисел с 14 до 11 удалось повысить обратно до 260 раз. Но 600 раз уже никак не получается, даже без PARI. Хотя мысли по оптимизации ещё остались.

Выкладываю снова в облако, там огромный (120М) архив с кучей вариантов скомпилённых вариантов exe (с одинаковым паттерном), не обязательно качать весь архив, облако позволяет скачать только выбранный файл: https://cloud.mail.ru/public/sE61/pg1UNw4mF
Данные статистики (которые и собирал весь вечер) прилагаются. Основную часть процитирую здесь:

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

Образцовая программа (на меньшем интервале, лишь 10^35):
T:\gp64 -q VAL1.gp
183800000000000000000000000000000000000 - start
183900000000000000000000000000000000000 - stop
183880930406850062548257966254326127641: 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 48, 24,  len=11
N=16879446, 154.598s,  N - это сколько кандидатов в цепочки было передано на проверку первой ispseudoprime во всём интервале.

Проверка простых до 256 в интервале 10^37:
T:\gp64 -q M12nv.gp
180000000000000000000000000000000000000 - start
190000000000000000000000000000000000000 - stop
183880930406850062548257966254326127641: 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 48, 24,  len=11
N=19538289, 278.404s / 213.518s in PARI,  N - это сколько кандидатов в цепочки было передано в PARI на проверку во всём интервале.

Далее все проверки выполняются в том же интервале, показываю только время работы.
Простые до 384: N=8914512, 153.040s / 100.044s in PARI
Простые до 512: N=5282567, 111.883s / 60.637s in PARI
Простые до 768: N=2718596, 82.486s / 32.245s in PARI
Простые до 1024: N=1717028, 70.635s / 20.842s in PARI
Простые до 1536: N=929979, 61.937s / 11.622s in PARI
Простые до 2048: N=612964, 58.756s / 7.831s in PARI
Простые до 2560: N=446093, 73.259s / 5.788s in PARI
Простые до 3072: N=347042, 58.460s / 4.727s in PARI
Простые до 3584: N=281895, 58.215s / 3.729s in PARI
Простые до 4096: N=235933, 59.634s / 3.073s in PARI
Простые до 5120: N=176715, 61.253s / 2.293s in PARI
Простые до 6144: N=141014, 61.852s / 1.982s in PARI
Простые до 8192: N=113100, 77.968s / 0.905s in PARI
Простые до 10240: N=113100, 64.382s / 1.451s in PARI
Простые до 12288: N=113100, 70.137s / 1.622s in PARI
Простые до 14336: N=113100, 65.015s / 1.591s in PARI
Простые до 16384: N=113100, 64.726s / 1.544s in PARI
Простые до 20480: N=113100, 64.780s / 1.560s in PARI
Простые до 24576: N=113100, 66.418s / 1.684s in PARI
Простые до 28672: N=113100, 67.262s / 1.528s in PARI
Простые до 32768: N=113100, 64.030s / 1.451s in PARI

Проверка влияния размера интервала перебора при вызове программы на версии с проверкой 3584 простых (выше везде использовался 10^8):
1e6: 174.190s / 6.271s in PARI
3e6: 99.232s / 4.258s in PARI
1e7: 70.175s / 3.697s in PARI
3e7: 61.668s / 3.853s in PARI
1e8: 58.215s / 3.729s in PARI
3e8: 57.470s / 3.712s in PARI
1e9: 57.971s / 3.822s in PARI

Отдельно один вариант exe (быстрейший, с проверкой по простым до 3584), с примером программы PARI: https://dropmefiles.com/6pXNT
Yadryara, и новый вариант по Вашему паттерну (он есть и в облаке), тоже 3584 и с проверкой лишь 11 чисел в паттерне, с примером PARI программы — по этой же ссылке.

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

-- 23.02.2022, 01:23 --

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

Dmitriy40, а можно Вас попросить как-то по-другому изображать паттерны?

Можно просто перечислять 15 чисел через запятую, будет не слишком удобно, но компактно.

-- 23.02.2022, 01:48 --

Да, забыл самое главное — выводы.
На проверенном интервале (около $1.8\cdot10^{38}$) проверять делимость на большие простые (больше 8000) смысла нет, таковых вариантов просто не встретилось, остальные делители больше $2^{16}$.
Достаточное качество фильтрации достигается уже при проверке простых до 3000. Дальше выигрыш мизерный, а размер файла растёт.
Из общего количества 3.8 миллиардов возможных цепочек в тестируемом интервале на выходе остаются от сотни тысяч до полумиллиона, PARI их проверяет единицы секунд. Фильтровать ещё лучше уже бессмысленно. Вот теперь можно побиться за скорость ...
Почему иногда (варианты 2560, 8192, 12288) время работы резко увеличивается я не понял. Перепроверял трижды, эффект стабильный. Возможно это эффект промахов кэша из-за специфического расположения таблиц ...

-- 23.02.2022, 19:23 --

UPD. Приложены файлы описания ReadMe.txt и подробной статистики Statistics.txt.

Вложение:

ReadMe.txt [7.02 Кб]
Скачиваний: 286

Вложение:

Statistics.txt [5.2 Кб]
Скачиваний: 282

[Dmitriy40]

Сделал учёт делимостей индекса первой проверкой. Ускорилось с 260 до 350 раз, с 58с до 44с, фильтрация с 281895 до 236264, на том же тестовом интервале $10^{37}$. Время счёта до выхода за предел чисел уменьшилось с 7000 до 1100 лет в одном потоке.
Замечательно что не пришлось править ассемблерный код, только генератор таблиц для него, вот за эту универсальность и боролся.
Пока не выкладываю, ещё потестирую.

Заодно нашёл мелкий глюк в выложенных выше программах: иногда редкие цепочки напрасно считаются допустимыми (с лишними делителями $7\ldots41$ на непроверяемых местах $n+0, n+10, n+12$). Это не страшно, не пропуски ведь, всё лишнее отрежет PARI, влияние же на скорость незначительное (с 58с до 54с).

[Yadryara]

Dmitriy40, я вчера скачал файлы из последней партии, но там не было реадми. Может быть стоит его-то выложить прямо здесь в теме, под катом.

[Dmitriy40]

Yadryara
Да думал файла статистики хватит, там примеры запуска есть ...
Поправил текст под адекватное (вчерашнее) состояние и приложил к предыдущему сообщению, чтобы всё было в одном месте.

[Yadryara]

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

Ехешник не запускается пока. У меня 32 разряда.

Dmitriy40, а Вам как-то может помочь то, что, например, $p$ в конструкции $32p$ не любое нечётное, а может иметь остатки только $311$, $533$, $817$ или $1039$ по модулю $1350$.

При точном старте и точном шаге в этом уточнении вроде нет нужды.

[Dmitriy40]

Разумеется под x32 виндой программа не запустится.
Переделать под x32 в принципе можно, 64 бита вроде нигде не необходимы, основная работа идёт в регистрах AVX которые от разрядности не зависят, а уж инициализацию переделать не так сложно, заодно и диапазон входных чисел придётся расширить (ведь $2^{32}$ индексов просчитаются за десяток секунд), но работать будет чуть медленнее (потому что AVX регистров доступно вдвое меньше и придётся больше работать с памятью). Я подумаю. Скажите если Вам это критично.

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

Dmitriy40, а Вам как-то может помочь то, что, например, $p$ в конструкции $32p$ не любое нечётное, а может иметь остатки только $311$, $533$, $817$ или $1039$ по модулю $1350$.

Не поможет — это уже учтено в используемом паттерне: там $(n+7)/32\equiv1039\pmod{1350}$ (при утроенном/ушестерённом модуле/шаге). Заранее не знал, обнаружил только что калькулятором. Про другие паттерны не скажу, не проверял.
Помочь может любое сильное условие, сильное в смысле редко срабатывающее (или часто не срабатывающее). А если таких условий несколько независимых, то их пересечение (объединение) ещё лучше.

[Yadryara]

Как же это я забыл. У чисел, имеющих ровно 4 делителя есть своё название: полупростые(semiprimes).

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

Я подумаю. Скажите если Вам это критично.

В каком смысле критично. Я хотел поиграться с прогой, названной моим ником, она у меня не работает.

Но, нужна прога, заточенная под поиск 11-ти огромных простых(и 4-х полупростых). И не только под конкретный паттерн, а под весь список паттернов для КМК37-11. Для этого я и приводил пример формирования паттерна. Кстати, сколько их по-Вашей оценке?

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

Не поможет — это уже учтено в используемом паттерне: там $(n+7)/32\equiv1039\pmod{1350}$ (при утроенном/ушестерённом модуле/шаге). Заранее не знал, обнаружил только что калькулятором. Про другие паттерны не скажу, не проверял.

А я знал. Здесь у нас некоторое взаимное непонимание всё ещё сохраняется. О каком модуле/шаге речь?

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

a = 722
m = 3660987554487982120802400
p1 = 5028162941065848674776261

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

На самом деле базовый шаг остаётся прежним для всех подобных программ: $2643233014340323091219332800 \approx 2.6 \cdot 10^{27}$.

Этот базовый шаг назовём $Step$. Я тогда имел в виду, что для других паттернов и других $a$ и $m$ всё равно будет выполняться

$$2^63^3\prod_{i=3}^{12}p_i^2=Step = ma$$

Закон Ньютона и здесь работает. Конечно $Step$ делится и на $1350$ и на $10800$.

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

Помочь может любое сильное условие

Вроде бы сильных условий куча, но они должны быть уже учтены.

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

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

$5$ из них точно дают произведения: $12p_1$ , $18p_2$ , $32p_3$ , $45p_4$ , $50p_5$.

Для всех 5 чисел посчитал обязательные остатки:

$p_1\equiv\pm829, \pm1421\mod{3600}$

$p_2\equiv\pm553, \pm947\mod{2400}$

$p_3\equiv\pm311, \pm533\mod{1350}$

$p_4\equiv\pm221, \pm379\mod{960}$

$p_5\equiv\pm199, \pm341\mod{864}$

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

При точном старте и точном шаге в этом уточнении вроде нет нужды.

Не только одно, все 5 сильных условий должны выполняться при правильном выборе $p1$, $m$ и $a$.

[Dmitriy40]

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

В каком смысле критично. Я хотел поиграться с прогой, названной моим ником, она у меня не работает.

Критично в том смысле что нет рядом под рукой другого компа под x64 виндой, или виртуалки с ней же, или ещё какого неизвестного мне варианта поиграться с x64 прогой.
Что же, раз нет, то сделаю вариант под x32, сегодня-завтра-послезавтра (надо ещё поработать успеть). Общий или конкретно под Вас - ещё подумаю, будет ли выигрыш/проигрыш от такой переделки (и насколько большой).

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

Но, нужна прога, заточенная под поиск 11-ти огромных простых(и 4-х полупростых). И не только под конкретный паттерн, а под весь список паттернов для КМК37-11. Для этого я и приводил пример формирования паттерна. Кстати, сколько их по-Вашей оценке?

Я не оценивал ни количество возможных паттернов, ни принципы их построения: генератор паттернов у меня работает очень странно, в зависимости какие условия ему дать проверять он выдаёт от сотен до сотен тысяч паттернов (это ещё до кучи вариантов подстановок малых простых в квадратах в каждый), какие из них недопустимы мне на взгляд не всегда понятно (например оказалось что поставив лишь одно вроде бы очевидное условие не получил ни одного допустимого паттерна с произведением коэффициента на квадрат простого, а я так надеялся на такие паттерны, даже перебирал их неделю, что-то даже находил (8-9 совпадений из 15)). Т.е. тут у меня путаница в основном в логике и/или математике. Мне проще написать генератор перестановок и заставить его отбирать допустимые паттерны, чем разбираться в правилах (не)делимости чисел. Потому я не берусь оценивать их общее количество.

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

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

Здесь у нас некоторое взаимное непонимание всё ещё сохраняется. О каком модуле/шаге речь?

О модуле/шаге конкретного паттерна, без домножения на 6 для учёта недопустимых вариантов по модулю 2 и 3 он выглядит так: $106022957662445288229350041 + 440538835723387181869888800 k$ и получается прямо из паттерна командой chinese именно в такой форме, я уже показывал выше. Если его пересчитать в $6$ раз больше (потому что по модулю 2 и 3 допустимы лишь по единственному варианту остатка $k$) и поделить на $722$, то получится (после одной малопонятной хитрости) $5028162941065848674776261+3660987554487982120802400 i$, как в программе VAL.

[Dmitriy40]

Yadryara
Держите x32 вариант программы с проверкой простых до 3584 по Вашему паттерну: https://dropmefiles.com/Og63g
Там оба варианта, и x32 и x64 (вдруг пригодится), плюс PARI демопрограмма замера скорости, результат запуска записал в неё же.

(Продублирую файл .gp тут)

start=17100*10^35;
stop=start+200*10^35;

\\   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=[   45,   722,   841,   12,   49,   50,   507,   32,   961,   18,   605,   28,   867,   1058,   1369   ];
pp=Mod(0,1); for(i=1,#v, pp=chinese(pp,Mod(-i+1,v[i]))); print(pp);
print(start," - start");
print(stop," - stop ");
t0=getwalltime(); gettime(); q=0;

{forstep(ii=floor(start/pp.mod),ceil(stop/pp.mod),10^8,
   printf("%0.2fe35%c",(lift(pp)+pp.mod*ii)/1e35,13);
   vi=extern(Strexpand("Yadryara.exe ",ii," ",10^8)); q+=#vi;
   if(#vi>0, foreach(vi,t,
      n=lift(pp)+pp.mod*t;
      if(
         !ispseudoprime((n+0)/v[1]) || !ispseudoprime((n+1)/v[2]) ||
      \\!   !ispseudoprime((n+3)/v[4]) || !ispseudoprime((n+5)/v[6]) ||
         !ispseudoprime((n+6)/v[7]) || !ispseudoprime((n+7)/v[8]) ||
      \\!   !ispseudoprime((n+9)/v[10]) ||
         !ispseudoprime((n+10)/v[11]) || !ispseudoprime((n+11)/v[12]) ||
         !ispseudoprime((n+12)/v[13]) || !ispseudoprime((n+13)/v[14]) ||
         0
      ,
         next;
      );
      s=vector(15,d,numdiv(n+d-1)); k=#select(x->(x==12),s);
      if(k>=1, printf("%d:",n); foreach(s,d, printf("%3d,",d)); print("  len=",k); );
      if(k==15, print("FOUND!!!"));
   ));
)}
printf("N=%d, %0.3fs / %0.3fs in PARI\t\t\t\n",q,(getwalltime()-t0)/1e3,gettime()/1e3);
quit;


Выдача:
T:\>gp32 -q Yadryara.gp
Mod(438957010505237256671215545, 440538835723387181869888800)
1710000000000000000000000000000000000000 - start
1730000000000000000000000000000000000000 - stop
1712084152981999171831531924917603912345: 12, 12,  6, 12, 12, 24, 12, 12, 12, 24, 12, 12, 12, 12, 24,  len=11
1718475518460662821245608915647563585945: 12, 12, 24, 48, 24, 12, 12, 12, 12, 24, 12, 12, 12, 12, 48,  len=10
1723647561535737193966646941181694393945: 12, 12, 24, 12, 12, 24, 12, 12, 48, 24, 12, 12, 12, 12, 24,  len=10
1728525439430677205335450306830937157145: 12, 12, 24,192, 12, 96, 12, 12, 12, 48, 12, 12, 12, 12, 12,  len=11
N=472842, 103.113s / 16.927s in PARI

Для справки:
вызов x64 программы из x32 PARI: N=472842, 98.852s / 17.269s in PARI
вызов x32 программы из x64 PARI: N=472842, 91.815s / 6.676s in PARI
вызов x64 программы из x64 PARI: N=472842, 87.100s / 6.552s in PARI

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

[Yadryara]

Dmitriy40, не пошла программа. Секунд через 5 после запуска сообщает о прекращении работы программы. Вы её проверяли на 32-разрядной Винде ?

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

У меня получилось $2\cdot (12+20) \cdot 720=46080$ вариантов. Впрочем, считал наспех. Но порядок числа, видимо, такой.

Не-а. Я считал не наспех и у меня получилось $1\;353\;600$ паттернов.

Кстати, задача подсчёта количества паттернов для КМК37-11 довольно сложная и подошла бы для МатМарафона. Заодно привлечь внимание к проблеме.

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

Т.е. тут у меня путаница в основном в логике и/или математике.

Скорее просто лень вникать. У меня то же самое по отношению к Maple.

[Dmitriy40]

Yadryara
Мне доступны два компа с x32 виндой: виртуалка WinXP и ноут Win7. Ни один из них не поддерживает AVX регистры (в XP тотально, в 7 только с SP1) и соответственно программа вылетает с ошибкой. Потому в чём проблема у Вас я выяснить не могу, может тоже в принципе не поддерживается AVX, может есть другие ошибки у меня. Остаётся вариант переделать программу под SSE, полностью исключив все AVX фичи, другого быстрого пути не вижу. Но SSE требуется не ниже 4.1, иначе будет существенно медленнее.

Переделал (всего за час): https://dropmefiles.com/p8JYV
Теперь работает даже под WinXP (и на процессоре 12-ти летней давности). Кроме времени работы вывод не изменился (он добавлен в конец .gp файла для справки).
Скорость работы чуть упала, что вполне ожидаемо: вместо 103с выполняется 118с в x64 винде и 124с в виртуалке WinXP (время под Win7 x32 не привожу, там медленный ноут, но там тоже работает). И всё увеличение времени от переделки с AVX на SSE приходится естественно на мою программу, не PARI. В сумме скорость упала почти в полтора раза (118.5с против 87.1с, цифры есть в .gp файле).

-- 02.03.2022, 16:52 --

Обнаружил цепочку с 14-ю из 15-ти чисел:
176394399749303520412335701680709124287641: 12, 12, 12, 96, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, valids=14