VALВозможно и отвечали ранее, но или я не понял, или ответ был про чуть другое. Сейчас вот это увидел
(последние теоретически могли бы присутствовать, но их допущение резко снижает эмпирическую вероятность успеха, поскольку в интересующем нас диапазоне произведения двух простых встречаются гораздо чаще, чем простые).
Таким образом, в проверяемых наборах заведомо не будет чисел, делящихся на квадраты простых чисел, больших 37. Разумеется, в интересующих нас цепочках таковые могут встречаться. Но в целях ускорения поиска выгоднее искать цепочки без них.
и стало понятно почему и простые взяли наименьшие, и от проверки квадратов отказались.
Спасибо за разъяснения.
Что же, с работой Ваших программ понятно, вопрос лишь как выбираете начальные числа, типа этого
, как строится всё их множество тоже понятно (по китайской теореме об остатках). Но это уже детали, на скорость перебора цепочек (но не величину числа
) это слабо влияет. А заниматься мелкими оптимизациями кода на PARI неохота.
Мне интереснее не просто запустить ваш код, а пытаться его ускорить, или в самом PARI, или вынесением части проверок наружу (в прогу на асме, да ещё и AVX прикрутить). Причём ускорить не в разы, а на пару-тройку порядков.
Поэтому и хотел сменить формулы на содержащие квадраты простых. Например выложенная Вами выше программа использует следующую комбинацию коэффициентов:
\\ 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 4pq 5pq^2 18p 847p 32p 3pq^2 50p - 12p 169pq 98p 45p
в которой в числа
подставлены квадраты простых 19,31,23,37 соответственно слева направо:
\\ 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
\\ - 722p 2883p 4pq 2645p 18p 847p 32p 4107p 50p - 12p 169pq 98p 45p
Понятно что все
и
тут и далее разные.
В результате остались лишь первые степени неизвестных простых
, которые Вы и ищете перебором с постоянным шагом по одному из них. А все
и пропущенные позиции найдутся сами, через numdiv.
(Зачем вообще подставлять квадраты)
Тут есть непонятная тонкость: зачем вообще подставили квадраты маленьких простых. Понятно чтобы увеличить модуль/шаг, но ведь тогда пропускаете огромную тучу вариантов где на этих местах стоят простые чуть больше 37. А количество проверок цепочек ровно то же, одна на модуль/шаг. Зато числа больше и PARI их проверить чуть труднее. Это полезно делать ради распараллеливания, но у вас и так достаточно разных вариантов чтобы загрузить хоть тысячи потоков. Зато если не подставлять квадраты первых простых, то и числа будут меньше, и подходящих под них вариантов будет больше, при фактически том же объёме проверок. Да, чуть чаще будут "ложные срабатывания" (уход на проверку numdiv вместо более быстрых ispseudoprime), но ведь и до подстановки есть 7 чисел лишь с
, одно перебираем, на 6 вместо 10 проверяем, частота уходов заметно не повысится и тормоза от numdiv влиять не будут (доли и единицы процентов замедления как обычно нагло игнорирую).
В качестве обоснования приведу сравнение: ваша десятка начинается с числа
, я же аналогичным линейным поиском на PARI без подстановки этих вот квадратов малых простых нашёл
той же длины 10, в 4млрд раз меньше. Да, мериться размером чисел, тем более для длины 10, смысла мало, просто иллюстрация что и без подстановки поиск достаточно эффективен.
Но я хотел поискать по формулам типа такой:
\\ 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
\\ 9pq 10p^2 11pq^2 12p 13pq^2 14p^2 15p^2 32p - 18p - 20p 21p^2 22p^2 -
Тут можно предварительно найти все возможные комбинации 5-ти простых
, чтобы выполнялись одновременно все равенства
по некоторому достаточно большому модулю
. Тогда можно перебирать лишь несколько (или вообще один если повезёт) вариантов
по этому модулю (т.е. с таким шагом). А так как условие на совпадение квадратов сильнее условия совпадения произведений, то и модуль тут должен быть на много порядков больше - а значит проверять на простоту и количество делителей на те же порядки меньше. Но проблема оказалась в нахождении и такого модуля, похоже он кардинально огромный, и подходящих вариантов
. Про символ Лежандра только пытаюсь осознать.
Кроме того, извлечение квадратного корня намного быстрее проверки на простоту, во всяком случае на обычном языке типа С или асма (но не PARI), что тоже можно использовать, даже на PARI (предварить проверку на простоту проверкой извлекаемости корня, плюс числа в ispseudoprime будут сильно меньше что тоже поможет PARI их проверить). А если организовать проверку на извлекаемость корня внешней прогой, что в общем несложно, то можно получить и хорошую скорость проверки (порядка сотен миллионов цепочек в секунду).
Такова была общая идея, вот её и обсасываю в разных вариантах. Пока безуспешно.