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

[Yadryara]

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

А Вы сверили что все проверки она делала без ключей -p и -W? Это важно.

Я-то сверил. Но это в первую очередь Hugo надо спросить. Все ли квадратные паттерны для 13-15-к правильно проверялись...

[Dmitriy40]

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

Запустил уменьшение порога до 5e11, в начале оценка 6ч, но реально думаю до суток будет.

Недооценил скорость своей проги, до 5e11 порог для всех паттернов уменьшила за 12ч, вдвое дольше первоначальной оценки.
Продолжает считать дальше.

[Dmitriy40]

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

Отдельно довёл до ума проверку по методу превышения начального числа в паттернах, запустил для уменьшения порога с 1e11 для паттернов с LCM=15850052618400, скорость примерно 400с/1e9, оценка требуемого времени 12ч, но подозреваю ниже 1e9 начнёт подтормаживаться так как будет достаточно много простых давать начальное число меньше 6e26 (пока около 1e11 их суммарно для всех этих паттернов в среднем порядка одного на 1e6, именно в этом и смысл такой фильтрации).

Действительно, за 12ч снизилось до 1e9, при этом вместо 1/1e6 простых в PARI вываливаются уже порядка 7e3/1e6, а при 0.5e9 и уже 15e3/1e6, при 0.3e9 уже 80e3 на миллион, 180e3 при 0.2e9, полмиллиона при 0.15e9, и их допроверка уже начинает занимать заметное время. Но всё равно оно несравнимо меньше проверки по qr. Во всяком случае для p заметно больше $\sqrt{6\cdot10^{26}/LCM}$.
За следующий час снизилось с 1e9 до 1e7.
От 1e11 до 1e8 ни одной цепочки так и не найдено ни для одного паттерна с LCM=15850052618400. Ниже 1e8 до 1e7 найдены 22 цепочки не длиннее 7.

[Dmitriy40]

Как и ожидалось за 12ч*2 (в двух потоках) снизил порог для всех паттернов с LCM=15850052618400 с 3e11 до 1e11, опять же ожидаемо ничего не найдено. Ниже 1e11 снижал вчера. Интервал 345e9-300e9 пока остаётся недопроверенным.

Вторая программа (которая на самом деле первая, работает по qr) за ночь досчитала лишь до 345e9, но для всех вообще паттернов. Суммарно потрачено 32ч, из которых 25ч на уменьшение с 1000e9 до 345e9. Ничего длиннее 7 по прежнему не найдено.

[Dmitriy40]

Всё же полезно иногда прежде чем писать программы подумать головой ...

При попытке добавить проверку реальных цепочек наткнулся на сильнейшее ограничение возможных решений при подстановке $p^2$ в любой паттерн: $p<\sqrt{LCM}$. Т.е. для всех паттернов с $LCM=7214407200$ нет ни малейшего смысла пытаться подставлять в него $p>\sqrt{7214407200}=84938$ ни на какую позицию. А для $LCM=7207200$ нет смысла подставлять $p>\sqrt{7207200}=2685$. Хоть в 13-ку, хоть в 14-ку, хоть в 15-ку (каждое из них проверяется отдельно, но достаточное условие выполнено везде).
И вообще не надо париться с поиском подходящих qr или муторным снижением порога -p от триллионов.

Соответственно, для максимального $LCM=7236072072036007200$ нет смысла подставлять $p>\sqrt{7236072072036007200}=2.7\cdot10^9$, а значит минимально возможный qr будет $\frac{1.2\cdot10^{23}}{2\cdot(2.7\cdot10^9)^2}=8260$ (раз уж до 1.2e23 решений не нашлось). А для любого $LCM$ минимальный $qr=1.2\cdot10^{23}/2/LCM$.

И это только верхнее ограничение на $p$, а ведь и ниже него далеко не любое $p$ можно подставлять, причём проверка подходит $p$ или нет оказывается очень простой, всего лишь взятие остатка.

-- 24.01.2023, 19:45 --

Например для всех паттернов без квадратов D12n15 с LCM=7207200 можно подставить лишь ровно одно $p=41$ и всё, т.е. нет даже двух допустимых $p$ чтобы их подставлять!

-- 24.01.2023, 20:24 --

Для D12n15 без квадратов для LCM=17304487200, 205844839200, 494233458919200, 3013774290727200, 7236072072036007200 нет ни одного допустимого простого для подстановки в паттерны в квадрате!

[EUgeneUS]

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

При попытке добавить проверку реальных цепочек наткнулся на сильнейшее ограничение возможных решений при подстановке $p^2$ в любой паттерн: $p<\sqrt{LCM}$.

Вот это поворот!
Это же прям сильно упрощает проверки.
А как это обосновывается?

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

Например для всех паттернов без квадратов D12n15 с LCM=7207200 можно подставить лишь ровно одно $p=41$ и всё, т.е. нет даже двух допустимых $p$ чтобы их подставлять!

Насколько помню, там нужно подставлять более одного $p^2$. То есть в этих паттернах решений нет?

[Dmitriy40]

EUgeneUS в сообщении #1578621 писал(а):

А как это обосновывается?

В двух словах: в алгоритме Гарнера начальное число паттерна (до подстановки простого в квадрате) по модулю $p^2$ должно иметь диапазон всего 13-15 значений (для паттернов соответствующей длины), и для $p^2>LCM$ оно просто равно начальному числу паттерна, а они все не подходят под этот диапазон.
А меньшие $p$ должны удовлетворять тому же соотношению, но там таки надо проверять что начальные числа паттернов по модулю $p^2$ не дают 13-15-ти нужных остатков.
Если не в двух словах, а подробно, то позже.

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

EUgeneUS в сообщении #1578621 писал(а):

Насколько помню, там нужно подставлять более одного $p^2$. То есть в этих паттернах решений нет?

Может и есть, но не по паттернам без квадратов и с подстановкой простых только в квадрате (можно же и $p^5$ подставлять, для пустых мест и малых $p$ решения могут найтись).

-- 24.01.2023, 20:44 --

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

(можно же и $p^5$ подставлять, для пустых мест и малых $p$ решения могут найтись).

Могли бы, но для 15-ки не нашлись, ни одного допустимого простого ни для одного LCM - по той же причине.
Выходит да, для некоторых LCM решений в принципе нет.

-- 24.01.2023, 21:03 --

Что-то странное, в 15-ку с LCM=7214407200 ни в один паттерн типа нельзя расставить более двух простых в квадратах, все $p<241$, а там где можно два, там 19 и 47. Но ведь пятнашки найдены ... Что-то вероятно я не так делаю ...

[Dmitriy40]

Да, это я погорячился! Не то нулю приравнял.
Не выходит такого строго ограничения.

[Dmitriy40]

Считающие программы продолжают своё непростое дело, первая прога снизила порог до -p2e11 за 65ч работы, вторая снизила его же до $\sqrt{6\cdot10^{26}/LCM}$ (т.е. до величины, ниже которой может быть больше одной итерации линейного перебора, хотя может и не быть) для всех паттернов с $LCM=15850052618400$ и $LCM=9602375983200$ (примерно по 25ч каждый).
А третья прога перебора паттернов нашла наконец целых 3 десятки (раньше были только девятки), одну в b510 и две в b470.
Во все их сомнительных штук не добавлял.

Реализовал тут кстати тест простоты Ферма, для чисел $p<2^{64}$, это ускорило первые две проги где-то на 25%, теперь понимаю почему isprime/ispseudoprime в PARI так резко тормозят при увеличении чисел выше $2^{64}$.

[EUgeneUS]

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

Да, это я погорячился!

Понятно.

Вот это:

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

сильнейшее ограничение возможных решений при подстановке $p^2$ в любой паттерн: $p<\sqrt{LCM}$

сразу выглядело странным, так как противоречит гипотезе Диксона.

Там ход такой:
1. Для каждого числа в цепочки мы можем всё расставить, кроме одного простого числа, оставлямого неизвестным.
2. Каждого из этих неизвестных простых чисел можно выразить через арифметическую последовательность.
3. Итого имеем набор из $n$ (число чисел в цепочке) арифметических последовательностей.
4. Гипотеза Диксона обещает, что если модули не запрещают, то обязательно найдется бесконечная серия, когда значения всех этих арифметичесских последовательностей будут простыми числами. То есть обещает не просто наличие цепочки, а их бесконечное количество.

Поэтому ограничения на расставляемые числа ($p^$, $qr$, $p^5$ ....) могут основываться только на двух факторах:
1. Модульная арифметика.
2. Ограничение сверху на числа в цепочке.

[Yadryara]

Что интересного ещё есть для 12-ти делителей? Я так понимаю, что какого-то существенного ускорения(в разы) уже достичь не удастся? Чем лично я могу помочь? Или остался только скучный счёт?

[Huz]

After a bit of a break, I've started working to remove the restrictions on -W in pcoul. As part of that, I'd like to simplify it to act in a more natural order, in particular to try the different primes in ascending order.

That implies two things: first, that with the new code you would not be able to recover a run started with the old code (if the last log line shows "W"); second, that you could no longer change your mind about the -W limit without restarting.

If anyone is currently using it in a way that would be substantially inconvenienced by such a change, please let me know either here or by email.

[Dmitriy40]

Состояние по D12n13:
Все паттерны с LCM=15850052618400 проверены, в среднем по минут 40 на каждый, найдено 41шт цепочек длиной 10, длиннее нет.
Для всех паттернов порог -p опущен проверкой по qr до 110e9, с большими простыми ничего длиннее 7 не найдено.
Для нескольких LCM порог -p опущен проверкой по начальным числам до момента когда ниже 6e26 может оказаться более одной итерации линейного перебора, с большими простыми ничего длиннее 7 не найдено.

[Dmitriy40]

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

Для всех паттернов порог -p опущен проверкой по qr до 110e9, с большими простыми ничего длиннее 7 не найдено.

За суммарно 135ч порог опущен до 100e9, ничего длиннее 7 не найдено. По этой программе работа остановлена.

[Dmitriy40]

D12n13:
За 117ч проверены все паттерны с LCM=9602375983200, найдены почти 50 десяток, длиннее нет.

Порог в -p опущен до 7e9 для всех паттернов, а для большинства LCM и ещё сильно ниже. Нашлась одна десятка, причём сразу в нескольких LCM. Ни девяток, ни длиннее 10 нет.