Про минимум. Его желательно бы не уменьшать, а наоборот, увеличивать. Чтобы сужалась разница между минимумом и максимумом - это резко уменьшает число шаблонов. Именно поэтому к-кортежи слишком слабое ограничение, в малых интервалах (длиной до
) реальный минимум будет заметно больше, просто потому что плотность к-кортежей окажется сильно меньше размера интервала и вероятность его нахождения упадёт почти в ноль. Я же проверял прямым счётом, на миллиардных интервалах диаметр длинных кортежей в разы превышает теоретический минимум. Вот пример для диаметров 27-кортежа в интервалах длиной 1млрд начиная с
:
1000e9:264..1494
1001e9:246..1692
1002e9:272..1590
1003e9:260..1634
1004e9:270..1536
1005e9:242..1562
1006e9:266..1610
1007e9:276..1530
1008e9:254..1510
1009e9:262..1494
Как видно минимум вдвое больше минимального теоретического диаметра 27-кортежа (он равен 120), а максимум в девять раз меньше оценки по prime gap (
для чисел около триллиона). Длина интервала вдесятеро меньше! И число простых чисел соответственно почти в 10 раз меньше. Представляете как уменьшается число сочетаний по 27 чисел из массивов десятикратно отличающихся длиной? Там же факториал длины.
Собственно задача и состоит именно в сужении интервала [120..15132] до [242..1692] для данного проверяемого интервала 10млрд начиная с 1трлн. И как именно сужать интервал для произвольных параметров (длина кортежа, начало проверяемого интервала чисел, его длина). Особенно максимум.
Про антикортежи и шаблоны. Как уже говорил, сейчас ишутся все простые числа и потом уже из них выбираются кортежи и проверяются на дополнительные условия. Основной тормоз - поиск простых чисел. Хочу попробовать сделать наоборот, для каждого проверяемого интервала (длиной скажем
) ограничить кортежи диапазоном [min..max] реально могущим встретиться в проверяемом интервале, перечислить все возможные комбинации простых чисел в этом диапазоне для кортежей заданной длины, отбросить не удовлетворяющие дополнительным условиям - получится набор шаблонов. После этого основной цикл: выполняем для проверяемого интервала решето Эратосфена на 0.1%, много (но далеко не все) составных чисел выбрасывается, проверить каждый шаблон не вычеркнулось хоть одно число из него, если в результате вычернулись числа из всех шаблонов, то можно не искать в проверяемом интервале все простые числа на 100%, а перейти к следующему интервалу, т.к. уже точно ясно что найденные простые числа не удовлетворят дополнительным условиям. Насколько это будет выгодно зависит от размера интервала и числа шаблонов. Вот только число шаблонов растёт (кажется) по экспоненте от размера max-min, потому и хочется максимально сильно его ограничить, чтобы не получить миллиарды шаблонов. Ограничить именно max-min, как уменьшая max, так и увеличивая min.
Задача не однодневная, за день её и не решить, уже полгода потихоньку про неё думаю и ещё годик-два наверняка есть. Просто думаю весьма изредка, от случая к случаю. Пока даже не знаю точно как формировать шаблоны и сколько же их будет. И боюсь для длинных кортежей количество шаблонов будет нереально большим.