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

[Dmitriy40]

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

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

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

Если я правильно понял, тут беда: числа 841, 49, 961, 1369 проверить невозможно так как после деления $n+x$ на них должно получаться составное число, а моя программа проверяет частное на (псевдо)простоту.
Если эти числа исключить, то получится следующее (оболочка на PARI):

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

start=0;
stop=start+10^28;
\\      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,    1,      12,     1,      50,     507,    32,     1,      18,     605,    28,     867,    1058,   1       ];
pp=Mod(0,1); for(i=1,#v, pp=chinese(pp,Mod(-i+1,v[i])));
print(start," - start");
print(stop," - stop ");

t0=getwalltime(); gettime();
{forstep(ii=ceil(start/pp.mod),oo,10^8,
        printf("%0.5fe30%c",(lift(pp)+pp.mod*ii)/1e30,13);
        vi=extern(Strexpand("M12nv2.exe ",ii," ",10^8));
        foreach(vi,t,
                n=lift(pp)+pp.mod*t;
                if(n>stop, break(2));
                if(
                        !ispseudoprime((n+11)/28) || !ispseudoprime((n+1)/722) || !ispseudoprime((n+12)/867)
                        || !ispseudoprime((n+3)/12) || !ispseudoprime((n+5)/50) || !ispseudoprime((n+6)/507)
        \\!             || !ispseudoprime((n+7)/32) || !ispseudoprime((n+9)/18) || !ispseudoprime((n+10)/605)
                        || !ispseudoprime((n+13)/1058) || !ispseudoprime((n+0)/45)
                ,
                        next;
                );
                s=vector(15); k=0;
                for(d=1,15, s[d]=numdiv(n+d-1); if(s[d]==12, k++););
                if(k>=1, printf("%d:",n); foreach(s,d, printf("%3d,",d)); print("  len=",k); );
                if(k==15, print("FOUND!!!"));
        );
)}
printf("%0.3fs / %0.3fs in PARI\t\t\t\n",(getwalltime()-t0)/1e3,gettime()/1e3);
quit;

Три проверки закомментировал специально, чтобы был хоть какой-то результат. Запуск с нуля до $10^{28}$:

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

T:\>gp64 -q M12nv2.gp
Mod(45865455726667545, 56880489879813600)
0 - start
10000000000000000000000000000 - stop
1108892787254924811019857945: 12, 12,  8, 12,  8, 12, 12, 24,  4, 48, 12, 12, 12, 12,  8,  len=9
1568079740795230210263893145: 12, 12,  2, 12, 16, 12, 12, 12,  8, 24, 48, 12, 12, 12,  2,  len=9
2089102811575393149687528345: 12, 12, 16, 12,  8, 12, 12, 24, 32, 24, 96, 12, 12, 12,  4,  len=8
2613340695632862965939145945: 12, 12,  8, 12,128, 12, 12, 24,  2, 48, 12, 12, 12, 12, 16,  len=9
2741167503845595583567785945: 12, 12,  8, 12, 32, 12, 12, 96,  2, 96, 24, 12, 12, 12,  4,  len=8
3930508058721117480680049945: 12, 12, 16, 12, 64, 12, 12, 24,  2, 24, 48, 12, 12, 12,  4,  len=8
5397672551645072232278721945: 12, 12,  4, 12, 32, 12, 12, 12,  8, 96, 24, 12, 12, 12,  2,  len=9
5768712128549373822558917145: 12, 12,  2, 12,  8, 12, 12, 24, 32, 96, 24, 12, 12, 12, 64,  len=8
5932790968894802738839089945: 12, 12,  4, 12, 16, 12, 12, 24,  4, 96, 24, 12, 12, 12,  8,  len=8
6778584728139235741833480345: 12, 12, 32, 12,192, 12, 12, 48,  4, 48, 12, 12, 12, 12,  8,  len=9
6885158962776410852090131545: 12, 12,  8, 12,  8, 12, 12, 48,  8, 12, 12, 12, 12, 12,  8,  len=10
7672785830148850115563435545: 12, 12,  4, 12,  8, 12, 12, 96, 32, 24, 96, 12, 12, 12, 16,  len=8
8029079592365465554321377945: 12, 12,  8, 12, 16, 12, 12, 48,128, 24, 12, 12, 12, 12,  8,  len=9
8833278664409025353912361945: 12, 12,  4, 12, 16, 12, 12, 24, 32, 96,192, 12, 12, 12,  8,  len=8
9546182745150018479498563545: 12, 12, 16, 12,  8, 12, 12, 48,  2, 24, 48, 12, 12, 12,  4,  len=8
725.153s / 433.449s in PARI

Программа: https://dropmefiles.com/FyI3p (копия: https://ru.files.fm/u/qb4avpfzs)
Virustotal тоже ругается, но уже по другому: https://www.virustotal.com/gui/file/7d1 ... 1851989cf3

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

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

EXE. Программа на PARI лишь оболочка и финальная проверка кандидатов, выдаваемых моим exe. Но можно и как-то по другому использовать (перенапрвить в файл и потом чем угодно разбирать/проверять).

-- 20.02.2022, 21:30 --

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

Если это действительно даст то ускорение, которое Вы обещаете,

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

[VAL]

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

EXE. Программа на PARI лишь оболочка и финальная проверка кандидатов, выдаваемых моим exe. Но можно и как-то по другому использовать (перенапрвить в файл и потом чем угодно разбирать/проверять).

А сколько логических ядер запускает один ваш exe?

[Yadryara]

Dmitriy40, Спасибо, я ещё подумаю на свежую голову.

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

Например выложенный (см. ниже) вариант программы проверяет делимость 14-ти чисел на первые 54 простых (до 256),

Основная трудность ведь найти 11 огромных простых. Делимость на крошечные простые-то нам зачем?

[Dmitriy40]

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

А сколько логических ядер запускает один ваш exe?

Один поток:

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

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

ReadMe.txt писал(а):

Ограничения:
...
Программа выполняется в одном потоке, без смены приоритета задачи.

Распараллеливание на много потоков осталось пока в планах. И не факт что буду делать: возможно удобнее запускать разные варианты цепочек чем одну во всех потоках.

[VAL]

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

Основная трудность ведь найти 11 огромных простых. Делимость на крошечные простые-то нам зачем?

Это дополнительное сито, ускоряющее проверку.

[Yadryara]

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

Если я правильно понял, тут беда: числа 841, 49, 961, 1369 проверить невозможно так как после деления $n+x$ на них должно получаться составное число,

Именно! В 4-х случаях составное(произведение ровно двух простых) и об этом уже говорили неоднократно. И это во всех паттернах так. 4 пары простых и 11 огромных простых. Надо под это затачивать, деваться пока некуда.

[Dmitriy40]

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

Делимость на крошечные простые-то нам зачем?

Это аналог isprime, частные проверяются на мелкие простые, вдруг какое-то разделится и тогда оно точно составное и можно переходить к следующей цепочке.
Фактически моя программа выполняет 14 (или 11) функций ispseudoprime(n) для 14-ти (или 11-ти) чисел $(n+x)/y$. И ищет такие $k$, которые в формуле $n=n_0+km$ не дают точно составных частных. Но не факт что они все простые, они лишь не имеют малых делителей, для этого и нужна финальная проверка в PARI или чем ещё.

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

Это дополнительное сито, ускоряющее проверку.

В общем да.

[VAL]

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

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

А сколько логических ядер запускает один ваш exe?

Один поток:

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

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

Я планирую это прочесть. Но, как уже писал, пока не успел.

Цитата:

ReadMe.txt писал(а):

Ограничения:
...
Программа выполняется в одном потоке, без смены приоритета задачи.

Поясните дилетанту: последнее означает, что будут загружены одни и те же ядра или что-то другое?

Цитата:

Распараллеливание на много потоков осталось пока в планах. И не факт что буду делать: возможно удобнее запускать разные варианты цепочек чем одну во всех потоках.

Меня вполне устроит такой вариант. Сейчас я запускаю одновременно 22 экземпляра PARI.
Сейчас вижу такой вариант: Я запускаю 22 программки типа моей, только значения $i$ не меняются в цикле, как сейчас у меня, а берутся из списка, возвращенного Вашим ситом.
Кстати, именно так я искал цепочку из 7 чисел, имеющих по 560 делителей.

[Dmitriy40]

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

В 4-х случаях составное(произведение ровно двух простых) и об этом уже говорили неоднократно. И это во всех паттернах так. 4 пары простых и 11 огромных простых.

Не во всех, выше была выложена программа от 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
v=[     17^2,   2*19^2, 3*31^2, 1,      5*23^2, 2*3^2,  7*11^2, 2^5,    3*37^2, 2*5^2,  29^2,   3*2^2,  13^2,   2*7^2,  5*3^2   ];

где на свободных местах расставлены квадраты малых простых, а произведение неизвестных простых лишь одно на месте $n+3$. Именно этот паттерн использован в первом варианте программы (именно ради сравнения с уже рабочей программой).
Я находил паттерны и вовсе без произведения, но не уверен на 100% что они корректные, например:

Используется синтаксис 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
                2pq^2   3pq^2   52p     5pq^2   18p     7pq^2   32p     363p    50p             12p             98p     45p     

-- 20.02.2022, 22:06 --

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

Поясните дилетанту: последнее означает, что будут загружены одни и те же ядра или что-то другое?

Т.е. программа выполняется на том же ядре что и родительская программа (PARI или окно консоли). Т.е. они работают строго по очереди. На одном ядре.
Точнее в одном потоке, ядра то могут меняться динамически, это дело ОС. А вот поток выполнения (нить, thread) один и загрузит в каждый момент времени не более одного ядра (физическое и/или логическое, смотря как ОС решит).

[VAL]

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

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

В 4-х случаях составное(произведение ровно двух простых) и об этом уже говорили неоднократно. И это во всех паттернах так. 4 пары простых и 11 огромных простых.

Не во всех, выше была выложена программа от 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
v=[     17^2,   2*19^2, 3*31^2, 1,      5*23^2, 2*3^2,  7*11^2, 2^5,    3*37^2, 2*5^2,  29^2,   3*2^2,  13^2,   2*7^2,  5*3^2   ];

где на свободных местах расставлены квадраты малых простых, а произведение неизвестных простых лишь одно на месте $n+3$.

Все же в этой позиции не $1$, а $2^2$.

Цитата:

Точнее в одном потоке, ядра то могут меняться динамически, это дело ОС. А вот поток выполнения (нить, thread) один и загрузит в каждый момент времени не более одного ядра (физическое и/или логическое, смотря как ОС решит).

Спасибо! Понял.

PS: И преисполнился оптимизма

[Dmitriy40]

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

Все же в этой позиции не $1$, а $2^2$.

По идее да, но там не 4p, а 4pq (и в текстах у себя сохраняю форму 4pq) - и снова моя программа не может проверить что частное должно быть составным.
А добавление 4 в паттерн никак не меняет ни $n_0$ (начальное число), ни $m$ (модуль, шаг), это проверял. Потому в программах для простоты 1, как удобный признак неиспользуемого места (0 же недопустим), который нормально обрабатывается chinese в PARI.

-- 20.02.2022, 22:42 --

Радость: за 3.5ч запущенная программа на том самом модельном паттерне нашла 13:

1451506113374998608422675946219072604441: 12, 12, 12, 12, 12, 12, 12, 24, 12, 96, 12, 12, 12, 12, 12,  len=13

И шесть штук 11. А 12 не нашла ни одной.
Так что дело это совсем не монотонное.

[Yadryara]

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

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

В 4-х случаях составное(произведение ровно двух простых) и об этом уже говорили неоднократно. И это во всех паттернах так. 4 пары простых и 11 огромных простых.

Не во всех, выше была выложена программа от 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
v=[     17^2,   2*19^2, 3*31^2, 1,      5*23^2, 2*3^2,  7*11^2, 2^5,    3*37^2, 2*5^2,  29^2,   3*2^2,  13^2,   2*7^2,  5*3^2   ];

где на свободных местах расставлены квадраты малых простых, а произведение неизвестных простых лишь одно на месте $n+3$.

Во всех! В рамках КМК37, во всех. Я, как и Вы видел только одну программу VAL, но полагаю, что во всех 2 тысячах программ 4 пары простых и 11 огромных простых.

И в этой тоже. Они стоят на местах $n+0$, $n+3$, $n+10$, $n+12$. Как раз там, где как Вы правильно заметили, "расставлены квадраты малых простых". Ну а на что, по-Вашему, нужно умножить $17^2$, чтобы получить число, имеющее $12$ делителей? Можно на куб простого, но таких чисел очень мало. Остаётся произведение двух простых.

Вот ведь я же старательно изображал схему ещё 10 дней назад:

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

$\text{Малые}\hspace{3.7cm}1\; 1\; 1\; 1\; 2\; 2\; 3\; 3 \hspace{1.7cm} 5$
$\text{квадраты}\hspace{1.8cm} 3\; 3\hspace{0.46cm} 5\; 7\; 1\; 3\; 7\; 9\; 3\; 9\; 1\; 7 \hspace{0.76cm} 2\; 2\hspace{0.36cm} 2$

$\text{Позиции}\hspace{1.91cm} 6\, \text{F} \hspace{0.4cm} \text{A}\text{B}\; 7\; \text{D}\; 1\; 5 \; 9\; \text{E} \;3 \;2\hspace{0.65cm} 4 \,\text{C}\hspace{0.36cm} 8$

$\text{Множитель раз}\hspace{0.8cm} 2\; 5\hspace{0.45cm} 2\; q\; q\; q\; q\; 5\; 3\; 2\; 3\; 2 \hspace{0.77cm} 7\; 3 \hspace{0.36cm} q$
$\text{Множитель два}\hspace{0.8cm} r\; r \hspace{0.48cm} r\; r\; r\; r\; r\; r\; r\; r\; r\; r \hspace{0.8cm} r\; r$

Видно же, что здесь 4 пары qr ? По вертикали они стоят.

А вот что VAL писал тоже 10 дней назад:

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

Для каждой цепочки сначала идет 11 проверок с помощью ispseudoprime (они быстрее и положительный ответ менее вероятен), а затем 4 проверки c помощью numdiv.

Вы видите, что здесь 11 и 4 ? Это именно потому, что 11 огромных простых и 4 пары простых.

[VAL]

Кстати, возможно, Ваша программа упростится, если на входе будут не только векторы v[], но и начальное значение, вычисленное с помощью chinese и даже список "терапевтических" исключений (по одному на каждое p от 5 до 37). Просто эти данные у меня уже есть для примерно двух тысяч v[].

[Yadryara]

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

Радость: за 3.5ч запущенная программа на том самом модельном паттерне нашла 13:Код:

1451506113374998608422675946219072604441: 12, 12, 12, 12, 12, 12, 12, 24, 12, 96, 12, 12, 12, 12, 12, len=13

Ну вот, все 4 пары простых она и нашла. Как же она их нашла, если их нет ?? Посмотрите факторизацию чисел, заканчивающихся на $41$, $44$, $51$ и $53$. Они все имеют вид $p_m^2qr$, где $p_m$ — малое($\leqslant37$) простое.

[Dmitriy40]

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

Кстати, возможно, Ваша программа упростится, если на входе будут не только векторы v[], но и начальное значение, вычисленное с помощью chinese и даже список "терапевтических" исключений (по одному на каждое p от 5 до 37). Просто эти данные у меня уже есть для примерно двух тысяч v[].

Ну эти данные у меня получаются прямо из паттерна в генераторе таблиц.
А вот что их можно задействовать ... Программа точно не упростится, но может ускориться. Думал об этом, но решил выгоднее проверять делимость частных на пару первых простых чем индекса, это займёт сравнимое время. Но вот сейчас запустил тест и оказалось что первая проверка у меня сокращает вероятность лишь в 1.3 раза. Выходит можно ускорить ещё в 1.7 раза где-то (проверки индекса сокращают примерно в 2.25 раза). Заманчиво. Правда засада в том что внутренний цикл у меня развёрнут (в этом одна из основных идей ускорения) с исключением недопустимых вариантов (простой аналог ваших проверок индекса) и индекс у меня идёт не подряд и как тогда быстро проверять его делимость ... В общем подумаю.
Пока мне хочется улучшить не скорость, а качество фильтрации, чтобы меньше проходило на выход и тормозило в PARI. Всё же 30с работы моей проги и 90с после интеграции с PARI слишком разнятся.

Yadryara
Походу Вы правы. Это ошибка у меня (в логике работы). Эти 4 числа не надо проверять на простоту, лишь на делимость на число из паттерна (что обеспечивается автоматом), ну и может быть на нечётность частного (не уверен что паттерном это тоже обеспечивается). Т.е. моя программа фильтрует слишком сильно.
Что-то теперь не уверен что это плохо ... Ведь ровно такая же программа без этих 4-х чисел ничего вменяемого не нашла.
Спасибо, буду думать.