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

[Dmitriy40]

EUgeneUS
Ну так различайте. Я не очень понимаю как это соотносится с вопросом расставлять ли простые.

Время счёта для больших интервалов (в десятки/сотни миллиардов раз больше получившегося шага/модуля паттерна) зависит практически как $T \sim n/p^r$, где $p$ расставляемое простое, $n$ сколько паттернов получилось при его расстановке, $r$ в какой максимальной степени оно расставлялось. Соответственно для первой степени выгодно когда $n<p$ (и лучше бы в разы, а не в десяток процентов), для второй и выше выгодно всегда (даже $p^2$ вариантов размещения просто не бывает, не говоря уж про $r>2$).

Для программы удобнее разделять паттерны по величине шага/модуля (и по количеству проверяемых мест если оно сильно отличается). Потому что выгодно запускать ускоритель минимум на десятые доли секунды, иначе накладные расходы съедают скорость, значит нужно выбирать круг так чтобы паттерны с максимальным шагом/модулем (и максимальным количеством проверяемых мест так как они лучше фильтруют и меньше оставляют работы PARI) выполнялись долю секунды, но тогда паттерны с минимальным шагом/модулем (и/или минимальным количеством проверяемых мест) будут выполняться минуты-часы. Если запускать круг на много часов (как Yadryara), то не принципиально, я же предпочитаю чтобы статистика писалась в лог примерно раз в час-два (сколько не жалко потерять при любых сбоях), а прогресс на экран и вообще каждую секунду. Хотя вопрос конечно тоже вполне решаемый, но удобства не прибавляет.

[EUgeneUS]

Dmitriy40

Прикинул по своему файлику. Получается, что $11^1$ расставляется от 2 до 4 мест, не более. То есть расставлять вроде как выгодно.

Однако, прикинем количество паттернов.
Количество возможных цепочек длиной 11, при расставленных пятерках и не расставленных 7 и 11: $2 \cdot (1 + 3 + 5) = 16$
Количество вариантов расстановок $7$ - от 3 до 8 (с учетом, что степени могут быть разынми). Пусть в среднем 6.
Количество вариантов расстановок $11$ - оценим в 13.
Тогда оценка количества паттернов - около $1250$.
Составлять их вручную - застрелиться

[Dmitriy40]

Ну так 46080 тоже не вручную составляли, и даже 64 группы для них (во всяком случае я). Сформулировали чёткие критерии и написал PARI программу полного перебора всех вариантов с критериями включения/исключения и проверил глазками статистику от результата (что везде нужное количество проверяемых мест, что групп ровно 64, что паттернов ровно 46080, что не повторяются (не глазками конечно, сортировкой и утилиткой поиска дублей), что не осталось неизвестных $p^2$, что шаг/модуль у всех одинаковый и именно расчётный, может и ещё что-то, уже не помню).
Тут можно хоть даже и её взять, но как ей объяснить что не всегда надо исключать неподходящие варианты (например для "11-с-краю" или "13-с-краю") пока не очень представляю, думать надо и пробовать. А у меня остаётся надежда что за меня подумаете Вы с Yadryara и выдадите или готовый список паттернов или точные условия как их получать. Мне всё равно останется куча работы (например привести все паттерны к длине 15 потому что иначе компилятор ускорителей почему-то не видит возможности утроить шаг проверки и лень разбираться почему), но она уже не столь творческая и вероятность ошибиться на порядки ниже.

[Yadryara]

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

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

Ну так я уже выложил 13 паттернов. И именно в них, в уже готовых, никто ошибок пока не заметил.

А как вчерашний запуск? Нашлось ли что-то выше 3е18?

[EUgeneUS]

Dmitriy40
Можно сделать вот такое:
1. Я вручную сделаю порядка 100 групп паттернов. С расставленными простыми до 7 включительно.
2. В них каждая позиция будет помечена:
"0" - $11$ не попадает. Это "проверяемая" позиция и без $11$
"1" - можно поставить $11^1$, $11^2$ или $11^5$. Если ставится $11^5$, то позиция становится проверяемой.
"2" - можно только $11^2$. Если ставится $11^2$, то позиция становится проверяемой.

Если в таком виде подойдет для дальнейшей автоматической генерации паттернов, то на выходных постараюсь сделать.

По идентификации паттернов. Предложение такое (на примере):

"A-3-52" - означает: $25$ стоит в позиции A, цепочка длиной 11 начинается с позиции 3, в пятой позиции стоит $7^2$
После расстановки $11$ идентификатор паттерна будет иметь вид:
"A-3-52-B1", что означает, что в позиции B стоит $11^1$.
Номера позиций - в Hex.
Тогда идентификатор любого паттерна будет строкой длиной ровно 9 символов.

-- 01.11.2022, 16:58 --

Кстати, в A119479 указано:

Цитата:

FORMULA
.... If n is not divisible by 3, a(2n) <= 7.

Вообще говоря, $a(2n) \leqslant 7$, "If $n$ is not divisible by $6$".
Это же ещё в основополагающей статье Дюнша и Эгглетона доказано...

Или надо поправить (у меня нет аккаунта к OEIS), или чего-то не понимаю...

[Yadryara]

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

Тогда идентификатор любого паттерна будет строкой длиной ровно 9 символов.

Но ведь в паттерне могут быть две семёрки. Разве не надо обозначать места и степени обеих?

[EUgeneUS]

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

Разве не надо обозначать места и степени обеих?

1. Если в паттерне есть семерка в степени более первой, то указываем её. Другая семерка появляется автоматически. И она обязана быть в первой степени.
2. Если в паттерне две семерки в первой степени, то указываем любую из них. То есть, если в идентификаторе указана семерка в первой степени, а в паттерне попадает ещё одна семерка, то вторая обязана быть в первой степени. Лучше всего в этом случае указывать ту семерку, которая (в других паттернах) может быть в степени отличной от первой.

[Yadryara]

Понял. Логично.

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

2. Если в паттерне две семерки в первой степени, то указываем любую из них.

Лучше именно левую указывать, с меньшим номером.

[EUgeneUS]

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

Лучше именно левую указывать, с меньшим номером.

не-не. Лучше указывать ту, степени которой перебираются.

[Dmitriy40]

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

Можно сделать вот такое:
1. Я вручную сделаю порядка 100 групп паттернов. С расставленными простыми до 7 включительно.
2. В них каждая позиция будет помечена:
"0" - $11$ не попадает. Это "проверяемая" позиция и без $11$
"1" - можно поставить $11^1$, $11^2$ или $11^5$. Если ставится $11^5$, то позиция становится проверяемой.
"2" - можно только $11^2$. Если ставится $11^2$, то позиция становится проверяемой.

Если в таком виде подойдет для дальнейшей автоматической генерации паттернов, то на выходных постараюсь сделать.

Ну так это всё легко алгоритмизируется и соответственно реализуется на PARI. Взять 6 паттернов с пятёрками и пытаться вставить туда $7^1,7^2,7^5$, если получилось, то пытаться и $11^1,11^2,11^5$. Делать это руками ... странно. Намного проще аккуратно сформулировать почему что-то куда-то нельзя поставить (для семёрки, для 11-ки условия простые). И ограничиться или центральной семёркой чисел (чтобы покрыть все возможные 11-ки), или лучше варианты "9-в-центре" плюс два "11-с-краю". Если что-то можно не слишком сложно переложить на комп, то так и надо делать.

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

Тогда идентификатор любого паттерна будет строкой длиной ровно 9 символов.

Это удобно, но совершенно не обязательно, длина обозначения паттерна нигде не критична.
Остальное не смотрел.

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

Ну так я уже выложил 13 паттернов. И именно в них, в уже готовых, никто ошибок пока не заметил.

Не сказали об ошибках не означает что их нет, может просто не проверяли. Хотелось бы ясного подтверждения что да, всё правильно и совпадает.
И 13 паттернов конечно прекрасно, но я так понял они лишь для одного варианта из семи с пятёрками и семёрками.

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

А как вчерашний запуск? Нашлось ли что-то выше 3е18?

Да оставил его считаться в одном потоке, что-то малоинтересное нашлось конечно (короче 8-ми в лог не выводил), до 3e19:
3439950928171579417: 12, 4, 32, 12, 12, 12, 12, 12, 12, 12, 12, 12, 8, 32, 6, valids=10, maxlen=9
4027400632776173017: 16, 32, 8, 12, 8, 12, 12, 12, 12, 12, 12, 12, 12,128, 24, valids=9, maxlen=8
5825942113694016217: 8, 8, 8, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 64, 24, valids=9, maxlen=9
5860039499314003417: 16, 32, 12, 12, 12, 12, 12, 12, 12, 12, 8, 12, 4, 64, 12, valids=10, maxlen=8
6798033470805845017: 2, 4, 12, 12, 12, 12, 12, 12, 12, 12, 16, 12, 32, 64, 6, valids=9, maxlen=8
7638870434878113817: 8, 16, 8, 12, 12, 12, 12, 12, 12, 12, 12, 12, 6, 16, 6, valids=9, maxlen=9
8863315803831936217: 32, 8, 48, 12, 4, 12, 12, 12, 12, 12, 12, 12, 12, 16, 36, valids=9, maxlen=8
10110329465900376217: 2, 48, 32, 12, 12, 12, 12, 12, 12, 12, 12, 12, 8,128, 12, valids=10, maxlen=9
10340594329951517017: 16, 16, 8, 12, 8, 12, 12, 12, 12, 12, 12, 12, 12, 16, 24, valids=9, maxlen=8
11992043826765725017: 4, 16, 12, 12, 12, 12, 12, 12, 12, 12, 32, 12, 8, 64, 24, valids=9, maxlen=8
12424727009994715417: 8, 8, 64, 12, 4, 12, 12, 12, 12, 12, 12, 12, 12, 32, 12, valids=10, maxlen=8
14153266331613105817: 8,256, 32, 12, 16, 12, 12, 12, 12, 12, 12, 12, 12, 16, 48, valids=9, maxlen=8
14999214006174432217: 2, 16,128, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 16, 48, valids=9, maxlen=9
16793827386062376217: 4, 16, 16, 12, 12, 12, 12, 12, 12, 12, 12, 12, 2, 16, 6, valids=9, maxlen=9
17898487139729093017: 4, 8, 32, 12, 4, 12, 12, 12, 12, 12, 12, 12, 12, 16, 24, valids=9, maxlen=8
18100622923455288217: 8, 4, 4, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 16, 6, valids=9, maxlen=9
18509024618870232217: 32, 32, 8, 12, 2, 12, 12, 12, 12, 12, 12, 12, 12, 16, 12, valids=10, maxlen=8
18836128191087595417: 8, 8, 32, 12, 12, 12, 12, 12, 12, 12, 12, 12, 4, 64, 24, valids=9, maxlen=9
22212340326452049817: 16, 16, 12, 12, 12, 12, 12, 12, 12, 12, 16, 12, 4, 32, 24, valids=9, maxlen=8
22683957009731285017: 4, 16, 8, 12, 12, 12, 12, 12, 12, 12, 12, 12, 8, 32, 6, valids=9, maxlen=9
23326375383552979417: 8, 8,256, 12, 4, 12, 12, 12, 12, 12, 12, 12, 12,512, 48, valids=9, maxlen=8
23656583988572923417: 8, 16, 4, 12, 12, 12, 12, 12, 12, 12, 12, 12, 4, 64, 96, valids=9, maxlen=9
29850280787656776217: 2, 8, 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 64, 24, valids=9, maxlen=9

[Yadryara]

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

И 13 паттернов конечно прекрасно, но я так понял они лишь для одного варианта из семи с пятёрками и семёрками.

Совершенно верно. Но это и хорошо. Ибо уже строится упорядоченная иерархия паттернов.

В данном случае взято самое левое положение 25-ки, самое левое положение 7-ки, и самая низкая степень обеих семёрок. И расставлены все возможные 11-ки тоже слева направо и по возрастанию степени.

[EUgeneUS]

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

1. Я вручную сделаю порядка 100 групп паттернов. С расставленными простыми до 7 включительно.
2. В них каждая позиция будет помечена:
"0" - $11$ не попадает. Это "проверяемая" позиция и без $11$
"1" - можно поставить $11^1$, $11^2$ или $11^5$. Если ставится $11^5$, то позиция становится проверяемой.
"2" - можно только $11^2$. Если ставится $11^2$, то позиция становится проверяемой.

Тэкс. Тут уточнение, будет так:

2. В них каждая позиция будет помечена:
"0" - $11$ не попадает. Это "проверяемая" позиция и без $11$
"1" - можно только $11^1$. Если ставится $11^1$, то позиция становится проверяемой.
"2" - можно только $11^2$. Если ставится $11^2$, то позиция становится проверяемой
"5" - можно поставить $11^1$, $11^2$ или $11^5$. Если ставится $11^5$, то позиция становится проверяемой.

-- 01.11.2022, 18:22 --

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

Взять 6 паттернов с пятёрками и пытаться вставить туда $7^1,7^2,7^5$, если получилось, то пытаться и $11^1,11^2,11^5$. Делать это руками ... странно

Конечно, всё это легко алгоритмизируется, а я занимаюсь закатом солнца вручную
Но там семёрки довольно странно "плавают".
Конечно, могу выдать 16 паттернов с расставленными простыми до $5$ включительно (это почти сделано, а доделать - быстро).
Но в каком виде Вам предоставить информацию, чтобы Вы аккуратно перебрали $7$ и $11$?

С другой стороны, сейчас сделал 14 групп паттернов с расставленными семерками. А их всего не более 100, то есть тоже подъёмно.

[Yadryara]

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

Да оставил его считаться в одном потоке, что-то малоинтересное нашлось конечно (короче 8-ми в лог не выводил), до 3e19:

Да, здорово. 10 непрерывных 9-к.

Черепашка и Ахиллес уже который день считают, но ни одной 9-ки не нашли. Никакой.

А всё потому, что тот перебор трудно назвать умным. Учитывается, что в искомой 11-ке обязательно есть число $32p$. Но ничего не говорится о об использовании того факта, что в искомой 11-ке не менее железобетонно есть число $18p$. Про обязательность 25-ки тоже ни слова. Сколько тысяч лет уйдёт на проверку интервала таким способом...

[Dmitriy40]

(Оффтоп)

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

Черепашка и Ахиллес уже который день считают, но ни одной 9-ки не нашли. Никакой.
А всё потому, что тот перебор трудно назвать умным.

Не только. Я не знаю как они перебирают, но подозреваю что forprime для 32p. Но для чисел 1e19 простое в среднем каждое 45-е число, значит в пространстве чисел перебор идёт с шагом в среднем 45*32=1440, против более чем 2млн шага у меня в программе (352800*6). Это уже в полторы тысячи раз быстрее. Плюс ускоритель работает раз в 600 быстрее PARI. В сумме выходит под миллион раз разница в скорости.
Проверим, по сообщениям там скорость составляет примерно 5e11/18ч=7.5e6/c, у меня с ускорителем 3.3e14/с (в 44млн раз быстрее) и 5e11/с без ускорителя на чистом PARI. Заметьте разницу даже на чистом PARI, 18ч против 1с на интервал 5e11, почти 5 порядков, я не знаю как надо написать код чтобы он работал настолько медленно, наверное там слишком много/рано используются numdiv и nextprime вместо ispseudoprime. Вот поэтому у меня столько и нашлось. Но это всего один паттерн из многих. Ближайшую известную мне девятку 3.44e18 там найдут уже через 17млн часов, совсем чуточку осталось досчитать.

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

Сколько тысяч лет уйдёт на проверку интервала таким способом...

А Вам не всё равно? Ну посчитайте сами, это же легко: (9.887e21-2.97e18)/7.55e6/3600/24/365.25/1000=41500 тысяч (41.5млн) лет. Разве ж это много. Тем более там два перебора идут навстречу, так что время надо ещё пополам поделить, вообще крохи останутся, уже вот-вот найдётся.
Понимаете, это не лечится. Любой вменяемый человек попытается оценить потребное время для решения задачи если она не решилась сходу (за час/день/неделю), вспомните сколько с Вами копий ломали с оценкой вероятностей для 15-ки, но мы же не знали верхней границы докуда надо проверить, а тут она известна и для оценки требуемого времени ничего сложнее арифметики 6-го класса школы знать не нужно. Но если цель не найти или доказать, а искать, т.е. процесс, то почему бы нет, можно хоть на обычных счётах искать минимальную 11-ку.
Да и вдруг повезёт, вот ткнёт пальцем и попадёт прямо в минимальную 11-ку, ну и что что вероятность меньше $10^{-12}$ (для часа проверки), кого это волнует то, ведь совсем же несложно ткнуть пару триллионов раз. Я тоже подумывал запустить какой-нибудь поиск по случайным точкам, но меня такая вероятность успеха не устраивает. А кто-то просто не хочет её знать (это ведь уже далеко не 6-й класс школы) и считает как умеет.
Так что не мешайте человеку заниматься любимым делом, медленно но верно.

[Yadryara]

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

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

Сколько тысяч лет уйдёт на проверку интервала таким способом...

А Вам не всё равно?

Разумеется, всё равно. Я же специально поставил многоточие, а не вопросительный знак.

Целью моего поста было подсказать. Хотя бы то, что нужно учесть обязательно. Ведь не хочется верить, что не в коня корм.

Ну а что насчёт тех 13-ти паттернов? Может их адаптировать?


1. 2-4B-1 $\to$ v = [11,50,3,28,1,18,5,32,3,2,7];
2. 2-4B-5 $\to$ v = [1,50,3,28,11,18,5,32,3,2,7];
...
13. 2-4B-55555 $\to$ v = [1,50,3,28,161051,18,5,32,3,2,7];

Или Вам всё понятно, но есть какие-то причины пока отложить?