Оказывается с помощью моей программы можно эффективно искать не только кортежи по фиксированному паттерну, но и любые числа (вместо начальных чисел кортежей), которые имеют не все разрешённые остатки по модулю простых. И чем больше остатков запрещено по каждому простому, тем эффективнее поиск (собственно это очевидно). В пределе можно просто искать простые числа, которые имеют всего по одному запрещенному остатку по каждому простому, но это уже извращение, решето эффективнее.
Например, есть пока нерешённая задача поиска такого паттерна [0..19]*19#*d с минимальным значением d чтобы кортеж из простых чисел начинался строго с числа 23, т.е. должны быть простыми все числа 23+d*19#*[0..19] (это задача поиска минимальной PAP/AP-20 с минимальным началом). Наименьшее известное d=134181089232118748020, это офигеть как много, надо или найти меньшее, или доказать что таковых нет. Вообще неизвестно ни одно d для PAP/AP-21 с кортежем 23+d*19#*[0..20]. И для более длинных. Если действовать втупую, то надо перебирать все d подряд, строить паттерн, по нему проверять числа кортежа на простоту. Вот только числа то выходят 28+ значными и их проверка весьма не быстрая.
Но можно заметить что вовсе не любое d разрешено, так например запрещены все d кратные 23. Давайте посмотрим какие остатки от d запрещены по модулю 29, под запрещены понимаю что как минимум одно число кортежа (кроме первого) кратно модулю, для этого переберём все 29 возможных остатков d%29 и проверим делимость каждого числа кортежа на 29:
Код:
? w=[0..19]*9699690; for(m=0,28, print(m,":",apply(x->(23+x)%29==0,w*m)); )
0:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1:[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
2:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
3:[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
4:[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
5:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
6:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
7:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
8:[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
9:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
10:[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
11:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
12:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
13:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
14:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
15:[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
16:[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
17:[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
18:[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
19:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
20:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
21:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
22:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
23:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
24:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
25:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
26:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
27:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
28:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Видим что в строках d%29=[1,2,3,4,5,6,7,8,9,10,15,16,17,18,20,22,23,24,27] одно из чисел кортежа кратно 29, значит такие остатки d%29 не подходят, остаются остатки d%29=[0,11,12,13,14,19,21,25,26,28], всего лишь 10 штук из 29. Перепишем программу их получения компактнее:
Код:
? w=[0..19]*9699690; for(m=0,28, foreach(w,d, if((23+d*m)%29==0, next(2))); print1(m,","); )
0,11,12,13,14,19,21,25,26,28,
И доработаем её до получения остатков по нескольким простым:
Код:
? w=[0..19]*9699690; forprime(p=29,47, print1(p,":");for(m=0,p-1, foreach(w,d, if((23+d*m)%p==0, next(2))); print1(" ",m); ); print; )
29: 0 11 12 13 14 19 21 25 26 28
31: 0 3 7 13 16 19 21 22 23 26 29 30
37: 0 1 3 4 5 6 8 11 12 14 16 17 18 24 27 28 30 35
41: 0 3 11 12 13 14 16 17 19 20 23 25 26 31 32 33 34 35 36 37 39 40
43: 0 1 5 7 13 15 16 18 19 20 21 26 27 29 31 32 33 34 35 37 38 39 40 41
47: 0 2 3 5 6 7 9 10 11 12 13 15 19 20 22 24 25 26 27 29 30 31 33 34 35 39 43 46
Итак, вместо перебора всех d можно перебирать лишь p-19 вариантов остатков по каждому p>28. Чтобы добраться до d=134181089232118748020 надо использовать простые p=[29..73], их произведение равно 182568275710689562381, при этом по всем этим модулям надо проверить лишь 245851150299955200 вариантов (в 742 раза меньше!). Проверка при этом не обязательно должна состоять из проверки простоты больших чисел, достаточно проверять лишь d по модулю небольших простых и те d что останутся подходящими допроверить уже с реальными числами кортежа.
Собственно именно всё это и делает моя программа! Разница только как готовить ей список остатков, что делается внешней утилитой один раз.
При поиске 19-252 мы проверили почти 6e17 вариантов, а тут достаточно проверить 2.46e17 вариантов, всем вместе (особенно с Демисом) можно справиться за пару-тройку месяцев. Причём здесь время счёта гарантированно не превысит оценки, ведь конец счёта известен, это то самое d=134181089232118748020, дальше проверять не нужно, а значит 2.46e17 вариантов точно достаточно (можно даже исключить из них 26.5% вариантов что дают d>134181089232118748020). А судя по динамике роста минимального d для меньших AP-k, есть вероятность что искомое d существенно меньше известного и можно найти ещё быстрее если по 73 перебирать не остатки, а тотально (линейно), как в поиске 19-252 по 71.
Правда в худшем случае мы ничего нового не найдём, лишь подтвердим известный результат, т.е. докажем его минимальность что тоже ценно, но не так как нахождение нового.
К сожалению поиск следующей PAP/AP-21 незначительно уменьшает количество проверяемых вариантов (не p-19, а p-20 по каждому простому, в 1.67 раза для простых p=[29..73]), а вот искомое d может быть и в сотню раз дальше, т.е. искать его в десятки раз дольше, это уже нереально с текущими мощностями.
PS. Конечно эти кортежи хоть и симметричные, но не из последовательных простых чисел, так что к теме не относятся, просто пример как можно использовать готовый инструмент для других целей.