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

[Dmitriy40]

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

И это при том, что идея трёхкратного ускорения всё ещё остаётся в запасе?

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

На текущий момент идей по кардинальному ускорению больше нет. Процентов 20 наверное ещё можно выжать тонкой настройкой/оптимизацией — поискать поточнее баланс между качеством фильтрации и скоростью, но это по идее повлияет лишь на время в самом PARI (влиянием в моей программе для последних версий можно пренебречь), а оно и так всего 15-20 процентов общего, вот где-то процентов 10-15 и получится отыграть (ещё сколько-то процентов можно выжать из моей проги, но ... тут идей совсем мало и можно уткнуться в процессорозависимость, чего не хотелось бы, оно и так уже немного есть).

Кстати держите себе для статистики ещё несколько 13-ок по вашему паттерну (из разных программ в разных диапазонах, не радуйтесь что "вон аж куда досчитал", это не так):
51709867697085158082433569611813414131545: 12, 48, 12, 12, 12, 12, 48, 12, 12, 12, 12, 12, 12, 12, 12, len=13
58781429538797049472706733214764333345945: 12, 12, 12, 12, 12, 12, 12, 12, 6, 12, 12, 12, 24, 12, 12, len=13
59026111132796786582226237913166139648345: 12, 12, 12, 12, 12, 12, 48, 12, 12, 12, 48, 12, 12, 12, 12, len=13
66372672767559387773311483719050465995545: 12, 12, 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 6, len=13
68350293815411985734437875222486212731545: 12, 12, 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, len=13

[Yadryara]

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

не радуйтесь что "вон аж куда досчитал", это не так):

А как? Надо уже полностью закрывать 41-значные числа, но для этого же надо знать, что проверено, а что нет.

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

66372672767559387773311483719050465995545: 12, 12, 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 6, len=13
68350293815411985734437875222486212731545: 12, 12, 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, len=13

Отлично, вот же какие две красавицы из 5 новых!

12-ки проигнорированы?

[Dmitriy40]

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

12-ки проигнорированы?

Да, их в интервале 4e40-6e40 (только что допроверился) нашлось 28 штук. А вон те две 13-ки за 6.6e40 это от другой программы по вашему же паттерну, с другими условиями по ispseudoprime (хочу проверить всю середину цепочки ради поиска непрерывных 13 и 14), её запустил сразу от 6e40 и далее, она нашла лишь одну 12-ку (и 4шт 11-ки и одну 10-ку). И они по идее могут/будут находить разные и 12 и 13 и 14.
Насчёт проверки всего диапазона до $10^{41}$ не беспокойтесь, проверю, ориентировочно завтра к обеду ночи, уж 15-ку точно не пропустим. Вот меньшие не найтись могут.

UPD. А тем временем по тестовому паттерну нашлась вторая 14-ка (и тоже не непрерывная), всего примерно вдвое дальше первой:
318352321496722643091650863302210959462041: 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 12, 12, 12, 12, valids=14

[Yadryara]

У меня дело идёт гораздо медленнее. Проверил $10-10.7\cdot10^{40}$, нашёл 7 12-к и 1 13-ку:

103021049267708446369500353204305784712345: 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 48, 12, 24, 12, 12,  len=13

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

нашлось 28 штук.

А сколько из них полнокомплектных?

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

проверить всю середину цепочки ради поиска непрерывных

Я в своём интервале не изменял алгоритм, но непрерывная нашлась:

106852944785314096427710863284669294275545: 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 24,  6,  len=12

Итого:

$\text{Хороших чисел}\hspace{3.7cm}12\hspace{1cm} 13\hspace{1cm} 14$

$\text{Найдено}\hspace{4.8cm} 79\hspace{1.2cm} 9\hspace{1.2cm} 1$

$\text{Полных комплектов(11 largeprime)}\hspace{0.52cm} 2? \hspace{1.2cm} 2\hspace{1.2cm} 1 $

[Dmitriy40]

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

459131499342622469058748519334957932441

Вот кстати хороший пример: данная цепочка моей программой не находится так как число $n+14$ имеет делитель $131$, моя программа его обнаруживает и в PARI данную цепочку не выдаёт.
Если это число из паттерна убрать (модуль/шаг и начальное число при этом не меняются), то да, находит, но из-за проверки 10-ти чисел вместо 11-ти скорость работы резко падает (на глаз в несколько раз, точнее мерить не стал).

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

А сколько из них полнокомплектных?

Не проверял.
Сейчас посмотрел — ни одной.
Поискал по всем логам, нашёл вот такие полнокомплектные цепочки:
9360890929744283398804343375484870729945: 12, 12, 24, 12, 48, 12, 12, 12, 24, 12, 12, 12, 12, 12, 24, len=11
18630588394977873276291675658747575317145: 12, 12, 48, 12, 24, 12, 12, 12, 24, 12, 12, 12, 12, 12, 12, len=12
22080923308218395219150573633428656216345: 12, 12, 24, 12, 6, 12, 12, 12, 96, 12, 12, 12, 12, 12, 48, len=11
26790815948011679597006026834798165325145: 12, 12, 12, 12, 12, 12, 12, 12, 48, 12, 12, 12, 12, 12, 12, len=14
30156053008412059145006574582807211579545: 12, 12, 24, 12, 24, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, len=12
60871343093634890059419762812828136912345: 12, 12, 48, 12, 24, 12, 12, 12, 24, 12, 12, 12, 12, 12, 24, len=11
66372672767559387773311483719050465995545: 12, 12, 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 6, len=13
68350293815411985734437875222486212731545: 12, 12, 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, len=13
86019263580597612928841295757994212435545: 12, 12, 48, 12, 96, 12, 12, 12, 24, 12, 12, 12, 12, 12, 24, len=11
11-ок мало потому что надоели и начиная с 3e40 перестал их выводить (до 3e40 их было 233 штуки), а последние две от другой программы.

[Yadryara]

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

318352321496722643091650863302210959462041: 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 12, 12, 12, 12, valids=14

Да, это прекрасная находка. Ближе к цели уже некуда. Можно осторожно предположить, что 15-ка найдётся ещё до достижения 43-значных чисел. Даю оценку 85-90% .

А я тем временем нашёл самую близкую к цели 13-ку.

110088614933289710460990691512640388793945:

12, 12, 24, 12, 12, 12, 12, 12, 6, 12, 12, 12, 12, 12, 12

[Dmitriy40]

Вторая программа до $10^{41}$ 15-ки не обнаружила. Вообще нашла лишь пару 10-ок и одну 12-ку (не полнокомплектную).
Первой до $10^{41}$ ещё считать и считать, надеюсь к ночи досчитает, но зато находит 12-ки (комплектность не смотрю, потом, по итогам проверю).
Что интересно, вторая программа работает в 1.2 раза быстрее первой, хотя исходник и .exe одинаковы и паттерн тоже один, отличия лишь в порядке проверок isprime в PARI. И это при том что встречаемость всех простых практически одинакова (специально проверял, думал первыми проверять более редкие, ан нет, все одинаковы с погрешностью порядка пары процентов).

[Yadryara]

Чтоб нам не проверять одно и то же. Проверил $10-11.04\cdot10^{40}$ и намерен идти дальше до $12\cdot10^{40}$.

[Yadryara]

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

Кстати чуть ошибся, проверяются простые по 41 включительно.

А можно ли Вас попросить обосновать это подробнее? С числовыми примерами?

[Dmitriy40]

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

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

Кстати чуть ошибся, проверяются простые по 41 включительно.

А можно ли Вас попросить обосновать это подробнее? С числовыми примерами?

Я вот тут про это писал (второе предложение, в скобках):

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

Кстати чуть ошибся, проверяются простые по 41 включительно. Просто потому что добавлена проверка делимости индекса первым делом, а она не привязана к 11 числам и влияет на все числа в паттерне (когда тестировал долго шизовался почему некоторые цепочки перестали находиться хотя в 11 проверяемых числах малых простых и нет — оказалось малые простые были как раз в 4-х непроверяемых числах и они новой версией совершенно правомерно исключались).

Причём пример ненайденной цепочки был как раз с 41 в непроверяемом числе (из-за чего долго и не мог понять почему не нашлась). Конкретное число пока привести не могу — те логи не сохранил, соответственно не помню какие именно цепочки перестали находиться.
С другой стороны вот число 42179144918437100779636207822612944345 находится и самой первой версией, и самой последней, хотя в непроверяемом $n+14$ есть делитель $41$.
Возможно я что-то напутал и ошибся тогда насчёт проверки $41$ в непроверяемых числах.

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

Чтоб нам не проверять одно и то же. Проверил $10-11.04\cdot10^{40}$ и намерен идти дальше до $12\cdot10^{40}$.

В принципе мне несложно (да и от перепроверки хуже не будет), но давайте тогда диапазон $12-20\cdot10^{40}$ оставим за мной.

Вообще, учитывая что появляются 14-ки, уже можно бы запускать перебор по всем паттернам, для этого (лично мне) понадобится написать внешнюю программу которая и будет перебирать паттерны каждые пару минут, руками следить я не собираюсь. Ну и нужен список паттернов конечно. Пока у меня имеются четыре паттерна (три нагло свистнул у VAL из опубликованных им данных, надеюсь он не в обиде, и один Ваш), в своих я сомневаюсь. Да, разумеется каждый из них допускает произвольную перестановку непроверяемых чисел, т.е. всего вариантов паттернов $3!+4!+4!+4! =78$ (или $96$ если в самом первом паттерне на пустое место тоже поставить квадрат малого простого). Э, на самом деле чуть меньше, не все перестановки допустимы, но всё равно десятки вариантов.

[Yadryara]

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

Возможно я что-то напутал и ошибся тогда насчёт проверки $41$ в непроверяемых числах.

О чём и речь, если проверять до $37$ включительно, то можно ещё выиграть время.

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

Что-то не решу исправлять ли ошибку в первой приводя ко второй, что посоветуете, камрады? Поддерживать оба варианта как-то муторно (запутаюсь).

Однако ж не только обсчитываете два паттерна, так ещё и о новых заговорили. Да и новые ли они.

Сильно подозреваю, что нужно не метаться между паттернами, а продолжать проверять существующие перспективные на всё больших числах, собирать статистику, хоть это и нудно. Я пока не вижу причин переходить на другие паттерны, которые априори ничуть не более перспективны.

[Dmitriy40]

Первая программа досчитала до $10^{41}$. В интервале $6-10\cdot10^{40}$ нашла 53 штуки 12-ок, все неполнокомплектные, и одну дополнительную к показанным выше 13-ку (тоже неполнокомплектную):
70940905714050530598442431238560357984345: 12,192, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 12, 12, valids=13
На этом её закрываю и дальше счёт будет идти второй программой (отличия только в порядке проверок isprime в PARI), которая выдаёт сильно меньше цепочек, но зато они все максимально правильные в середине. Так как не очень понимаю смысл копить много 12-ок или 13-ок. А две программы по одному паттерну это перебор.

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

Однако ж не только обсчитываете два паттерна, так ещё и о новых заговорили.

Да, поддерживать (в смысле исправлять ошибки и вносить другие изменения) в 2 или 4 варианта программы гораздо сложнее чем иметь 1000 вариантов .exe из одного исходника, получаемых практически автоматически одной программой на PARI при изменении всего одной строчки с вектором паттерна.
Вопрос что быстрее приведёт к результату, глубокий перебор одного паттерна или мелкий перебор множества паттернов — очень и очень непростой. Как показала практика с магическими квадратами (там тоже искались цепочки простых чисел специфичного вида, фактически той же программой, отличия лишь в условиях финальной проверки в PARI) искомые цепочки встречаются сильно неравномерно и при удачном выборе паттерна можно найти на порядки ранее (а при неудачном — столь же позднее).

[Yadryara]

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

нашла 53 штуки 12-ок, все неполнокомплектные,

А мне одна полнокомплектная всё же попалась:

113423464970164322254509415818042581145945

12, 12, 24, 12, 96, 12, 12, 12, 24, 12, 12, 12, 12, 12, 12, len=12


Итого, после проверки $ 0-11.5\cdot10^{40}$

$\text{Хороших чисел}\hspace{3.7cm}12\hspace{1cm} 13\hspace{1cm} 14$

$\text{Найдено}\hspace{4.6cm} 139\hspace{1.1cm} 11\hspace{1.1cm} 1$

$\text{Полных комплектов(11 largeprime)}\hspace{0.7cm} 3 \hspace{1.2cm} 3\hspace{1.2cm} 1 $

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

А две программы по одному паттерну это перебор.

Конечно.

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

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

Согласен. Но вопрос ещё и в том, какие паттерны Уважаемый VAL уже проверял и каких результатов добился.

[Dmitriy40]

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

Но вопрос ещё и в том, какие паттерны Уважаемый VAL уже проверял и каких результатов добился.

Не принижая его заслуги всё же отмечу что мне проще запустить проверку с нуля и повторить его результаты, особенно если не по всем тысячам паттернов. Прикидка на пальцах: вот он скажем уже 7 лет считает десятки тысяч паттернов, это 2500 дней на 22 потока и поделить на пусть 22000 паттернов, по 2.5 дня на паттерн, при ускорении x1000 моей программе хватит пяти минут на каждый паттерн. Так что любые отдельные паттерны перепроверить несложно, вот на все десятки тысяч нужно до месяца счёта (мне, в 4 доступных потока).

Так, немного теории. Поигрался вчера со своим генератором паттернов, посмотрел какие вообще паттерны допустимы по 2,3,5,7, оказалось если исключить те что с квадратом большого простого (по ним остаются вопросы о допустимости), то паттернов ровно 6 (3 зеркальные пары в зависимости от остатка по модулю 6 простого на месте n+7, где формула 32p), 2 пары имеют в одном месте произведение двух простых (с коэффициентом $2^2$ или $7^2$), оставшаяся пара произведения не имеет, а место занято $7$ (и $7^2$ в паттерне нет). Соответственно в первые 2 пары можно дополнительно разместить до 8 малых простых в квадрате, в оставшуюся пару можно расставить до 9 малых простых в квадрате. Учитывая ограничения на размещение 11 и 13 (чтобы они встречались ровно один раз в паттерне, требование вообще говоря произвольно) получается общее количество разных паттернов $2 \times 3 \times 4 \times 6! + 2 \times 4 \times 5 \times 6! + 2 \times 4 \times 5 \times 7! = 247680$ (первая двойка учитывает зеркальность, второе число сколько вариантов расстановки 11, третье число сколько вариантов расстановки 13, факториал сколько осталось возможных мест под остальные простые), причём в $201600$ из них расставлены простые по 41 включительно.

(Приведу под тегом все 6 паттернов в наиболее общем виде:)

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

Ради интереса запустил на ночь счёт по предпоследнему паттерну из перечисленных с произвольно расставленными в него 11 и 13 без других ограничений, т.е. 7 мест остались свободными. Считалось конечно медленно (моя программа могла проверить лишь 8 чисел из 15), 8 и менее совпадений не выводил вообще (слишком много), а больше записывал, до $10^{23}$ нашлось 2480шт 9-ок и 33шт 10-ок и всё, длиннее не обнаружено.
Вообще поигравшись с разными паттернами (и на разных интервалах), и полупустыми, и почти забитыми под завязку, вижу что 9-ки, да и 10-ки находятся очень активно и быстро и много, а вот более длинные обнаруживаются непропорционально реже, даже если они встроены в паттерн и по идее должны бы обнаруживаться чаще, ан нет. На нескольких полупустых паттернах проверил какие лишние (непроверяемые) числа нашлись правильными, оказалось довольно часто в них попадаются малые простые в квадратах, до сотни, до двух сотен. Т.е. идея заполнить пустые места малыми простыми в квадрате правильна.

Ещё ради интереса проверил есть ли разница во встречаемости большого простого с коэффициентом 28, о чём выше рассуждали, довольно простой программкой (тупо беру центральное простое и проверяю простое ли число с коэффициентом 28):

start=12359*10^15; stop=start+10^9; print(start," - start"); print(stop," - stop "); q=0; q1=0; q5=0;
{forprime(p=start,stop,
   q++;
   if(p%6==1,
      x=32*p-4; if(x%28==0 && ispseudoprime(x/28), q1++);
   ,   x=32*p+4; if(x%28==0 && ispseudoprime(x/28), q5++);
   );
)}
printf("N=%d, n1=%d, n5=%d\n", q,q1,q5);

Её вывод:
12359000000000000000 - start
12359000001000000000 - stop
N=22744143, n1=117383, n5=116987

Как видно никакой значимой разницы нет.
Аналогичные результаты и по остальным коэффициентам (на стомиллионном интервале, лень ждать по 5 минут):

18: N=2272941, n1=15024, n5=14998
50: N=2272941, n1=3629, n5=3788
12: N=2272941, n1=44511, n5=44565
45: N=2272941, n1=4826, n5=4970

Кажущаяся большой разница для 50 — артефакт, увеличение интервала в 10 раз (снова до миллиарда) даёт цифры 36659/36609 (замечу, соотношение даже перевернулось).
Дополнительно проверил встречаемость некоторых пар, ничего существенного тоже не обнаружил, везде разница менее 10% и падает с ростом интервала.
По итогу вполне можно принять что все простые распределены достаточно равномерно и предпочитать один паттерн другому нет оснований.

[Yadryara]

Dmitriy40, рад что вы занялись подсчётом количества паттернов.

Три человека считали -- три разных результата. Нормально для сложной задачи.

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

расставлены простые по 41 включительно.

Откуда опять 41-то взялось?

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

2 пары имеют в одном месте произведение двух простых (с коэффициентом $2^2$ или $7^2)$

Иными словами 4qr или 49qr. Или, что то же самое, паттерны-98 и 28 соответственно. То есть паттерн-28 обязательно содержит числа 28p и 49qr.

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

требование вообще говоря произвольно

В каком смысле?