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

[Yadryara]

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

Хм, у меня решений больше (или меньше? не пойму), правда сразу для двух серий (до первой 6-ки и ещё три шестёрки до 1e22):

Ну вот, теперь можем сравнить для двух серий до 1e22.

Всего 83 непрерывных 5-ки и 4 непрерывных 6-ки.

Все 6-ки сравнил — те самые.

Итого, в центре(30-34-е места) нет ни одной 5-ки в 1-й степени.

[Yadryara]

На местах 30-34 степень 5-ки выше 2-й уже невозможна по той простой причине, что количество делителей будет больше 12.

Значит 25 в центре гарантированно присутствует во всех цепочках 11+. Таким образом, после исследования различных запретов, обнаружил, что осталось всего лишь 3 варианта с 25 в центре. Два классических, с $50p$ на местах 30 и 34(знакомых нам ещё по по поиску 15-ки) и ещё вот этот с $75p$ на 33-м месте:

S-pattern

25  26  27  28  29  30  31  32  33  34  35  36  37

     2       4       2      32       2       4    
         3           9           3           3    
             5                  25              

Пока не вижу причин, запрещающих такое расположение именно для цепочки длиной 11.

[EUgeneUS]

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

Значит 25 в центре гарантированно присутствует во всех цепочках 11+

25 гарантированно есть в центре для цепочек 12+. Для которых обязательно наличие "центральной" цепочки длиной девять.
Для каждого варианта расположения троек таких мест для 25 - два.

Для цепочки длинной 11, появляется ещё один вариант размещения 25-ки: "с краю". В позиции $n_{\pm 6}$, знак - в зависмости от расположения троек.

Все эти варианты расположения 25 отображены на рисунке в этом посте

-- 31.10.2022, 10:26 --

Текущая деятельность направлена на уменьшение паттернов, которые могут дать цепочки 11+.
Но полностью исключить "линейный" перебор не получится.
Хотя бы потому, что точно есть как минимум два паттерна размещения простых до $7$ включительно, которые дают длинные цепочки - именно там мы искали и нашли пентадекатлон ;)

Поэтому остаётся актуальным вопрос:
1. Если мы возьмём паттерн размещения простых до $7$ включительно, в котором искали пентадекатлон.
2. Простые больше $7$ расставлять не будем.
3. Вопрос: насколько реально в таком паттерне найти "все центральные девятки", а найденные проверить на принадлежность к более длинным цепочкам (11+)? Проверять - хотя бы до известной 11-ки.

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

[VAL]

$M(216)\ge 12$

(Оффтоп)

n = 55779355645113341211122358712392520214879167929235672115352492101485784565743796474425099267237787943040424560891
n+5 = (2)^8 ((67))^2 (2811845934409)(15172487889275524707767527110729667454136263)(1137720547271822389091236452003431560283337531470207)  
n+6 = 17^(2) * 29^(2) * 41^(2) * 63 248679 019328 774339 913749 * 22 007928 926239 518792 060772 159871 (32 digits) * 98080 191861 801887 536535 103679 478163 132778 689947 (47 digits)  
n+10 = 3^(2) * 7^(2) * 59^(2) * 19 524851 * 1 436599 624729 842289 915820 618942 695669 147254 207557 (49 digits) * 1295 410471 357442 313189 777876 336169 052543 442958 743883 (52 digits)

[Yadryara]

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

Для цепочки длинной 11, появляется ещё один вариант размещения 25-ки: "с краю". В позиции $n_{\pm 6}$, знак - в зависмости от расположения троек.

Да ладно. Думаю, что это невозможно. То есть пятёрка в 1-й степени всё-таки стоит в центре ?

Приведите пож-ста схему размещения без рисунка. Рисунок мне разглядывать затруднительно. Мелкий шрифт и не получается увеличить.

-- 31.10.2022, 11:46 --

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

Хотя бы потому, что точно есть как минимум два паттерна размещения простых до $7$ включительно, которые дают длинные цепочки - именно там мы искали и нашли пентадекатлон ;)

4 классических паттерна размещения простых до $7$ включительно.

-- 31.10.2022, 12:09 --

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

Для цепочки длинной 11, появляется ещё один вариант размещения 25-ки: "с краю". В позиции $n_{\pm 6}$, знак - в зависмости от расположения троек.

Да, не видно запрета.

Не первый раз замечаю, что почему-то удваиваете "н": "для цепочки длинной 11".

[EUgeneUS]

Yadryara
Вот, в Вашей нотации:
N-pattern

25  26  27  28  29  30  31  32  33  34  35  36  37  38  39
     2       4       2      32       2       4       2
  9          3           3           9           3
             5                   5                  25

Да, число в позиции $n_{28}$ не может иметь 12 делителей.
Однако, цепочка в позициях $n_{29}...n_{39}$ не запрещена.

Впрочем, Вы уже и сами это обнаружили.

[Dmitriy40]

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

а найденные проверить на принадлежность к более длинным цепочкам (11+)?

Проверка на более длинную цепочку чем искалось делается при выводе найденного в лог и потому фактически бесплатно, замедление ниже порога случайных флуктуаций.

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

Вопрос: насколько реально в таком паттерне найти "все центральные девятки",

Не понял размещается $7^1$ или $7^2$ или любая из них. В квадрате легче, её и прикину. Сколько получится паттернов считать лень, потому оценка лишь по порядку величины. Шаг проверки будет $\operatorname{lcm}(2^5,3^2,5^2,7^2)=352800$, до 1e22 надо сделать $10^{22}/352800=2.83\cdot10^{16}$ попыток (на каждый паттерн), из 9-ти чисел проверить ускорителем можно 5, примем скорость проверки 3e14/c (это не попыток, а реальных чисел, для примера скомпилировал приведённый выше S-паттерн Yadryara с размещенным 49 на 32p-1), требуемое время порядка 1e22/3e14=3.3e7 секунд или год на поток на паттерн, при этом 60% времени занимает допроверка в PARI (фильтрация в ускорителе всего лишь 28400000000/4784079/95492 (передано в ускоритель / вернулось из ускорителя / все проверяемые места правильные) для 1e16 интервала). Если размещать $7^1$, то ещё в 7 раз дольше.
Это консервативная оценка, можно поступить по методу Yadryara & Hugo и разместить в любое из 3-х мест квадрат ещё одного не слишком большого простого $x$ (большие можно сразу в PARI проверить, без компиляции ускорителей) и уменьшить время в $x^2$ раз (для каждого конкретного $x$).

[EUgeneUS]

Dmitriy40
Спасибо!

некоторые уточнения.

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

из 9-ти чисел проверить ускорителем можно 5

Для "классического" размещения $25$ у меня получилось, что в центральной девятке проверяются ускорителями только 4 числа
Для "экзотических" размещений $25$ проверяются ускорителями 5 из 9, 3 из 11, 4 из 11. (Эти размещения $25$ оказываются возможны, так как ищем не 15-ку, а всего лишь 11-ку)

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

Не понял размещается $7^1$ или $7^2$ или любая из них.

Для "классического" размещения $25$ у меня получилось, что $7^2$ можно разместить тремя способами и $7^1$ - двумя способами.

То есть только для "классического" размещения пятёрок потребуется время в $2 \cdot 1 \cdot (3 + 2 \cdot 7) = 34$ больше, чем для одного паттерна. То есть 34 года на один поток.
Первый множитель - количество вариантов расстановки троек.
Второй множителье - количество вариантов расстановки пятерок (рассматриваем только "классический варниант")
Первое слагаемое в скобках - варианты расстановок $7^2$.
Второе слагаемое в скобках - варианты расстановок $7^1$, а они считаются в семь раз медленнее.

И это без учета времени на "экзотические расстановки пятерок", что увеличит в разы, если не на порядок.
И без учета, что ускорителями считаются 4 из 9, а не 5 из 9.

Итого - сотни или 1-2 тысячи лет на один поток.
Для BOINC-проекта с несколькими тысячами потоков - подъёмно. Для текущих располагаемых мощностей - нет

[Dmitriy40]

Сравнил со скоростью перебора на чистом PARI ровно того же паттерна: 5e11/c (в реальных числах), в 3.3e14/5e11=660 раз медленнее. Ну то есть ускоритель работает практически как и обычно, почти 1e9 попыток в секунду, для 5-ти проверяемых мест очень даже неплохо.

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

Для "классического" размещения $25$ у меня получилось, что в центральной девятке проверяются ускорителями только 4 числа

Не понимаю, я же конкретно сказал какой именно паттерн проверяю: v=[1,2,3,20,1,18,49,32,75,2,1,12,1,70,9], при этом ускорителем проверяются места с 20 по 12, т.е. центральные 9, из которых он может проверить 5 (20,18,32,75,12). Числа 70 и 9 поставлены от фонаря, они нигде не используются но нужны для корректной компиляции ускорителя.
До 1e18 за почти час найдены две восьмёрки, длиннее не найдено:
558986553851592217: 32, 32, 16, 12, 16, 12, 12, 12, 12, 12, 12, 12, 12,256, 12, valids=10, maxlen=8
642257978362205017: 8, 16, 8, 12, 4, 12, 12, 12, 12, 12, 12, 12, 12, 64, 24, valids=9, maxlen=8
О, пока писал нашлись две девятки чуть дальше:
1046695868406465817: 16, 24, 32, 12, 12, 12, 12, 12, 12, 12, 12, 12, 4, 32,144, valids=9, maxlen=9
1096933088805369817: 16, 8, 32, 12, 12, 12, 12, 12, 12, 12, 12, 12, 32,192, 24, valids=9, maxlen=9

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

Для BOINC-проекта с несколькими тысячами потоков - подъёмно.

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

[EUgeneUS]

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

Не понимаю, я же конкретно сказал какой именно паттерн проверяю: v=[1,2,3,20,1,18,49,32,75,2,1,12,1,70,9],

Это скорее "экзотическое размещение" $25$. Там действительно пять проверяемых мест. И одно место для размещения семерки ($7$ или $7^2$).

[Yadryara]

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

До 1e18 за почти час найдены две восьмёрки,

А есть ли смысл проверять с нуля. Ведь Хьюго заявил, что почти до 3e18 уже всё проверено.

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

v=[1,2,3,20,1,18,49,32,75,2,1,12,1,70,9]

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

Числа 70 и 9 поставлены от фонаря, они нигде не используются но нужны для корректной компиляции ускорителя.

Ну так тогда тем более нужно 11 ставить в той иной допустимой степени. Ведь в 11-ке обязательно есть 11-ка!

А вообще лучше всё-таки полный список паттернов подготовить, хотя бы с расстановкой всех простых до 11.

Занимаюсь этим потихоньку.

[Dmitriy40]

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

И одно место для размещения семерки ($7$ или $7^2$).

Почему одно? А $32p+2$ вместо $32p-1$? Вроде для длин 10,11,12 вполне допустимо.

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

А есть ли смысл проверять с нуля. Ведь Хьюго заявил, что почти до 3e18 уже всё проверено.

Во первых перепроверить не помешает, во вторых это всего 2.5ч при общем времени до 1e22 порядка 8400ч=год, что совершенно ничтожно, в третьих я в общем то и не собирался считать этот паттерн, сделал его лишь для оценки скорости для EUgeneUS (ну и себе понять насколько выгодны ускорители в такой комбинации).

[EUgeneUS]

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

А вообще лучше всё-таки полный список паттернов подготовить, хотя бы с расстановкой всех простых до 11.
Занимаюсь этим потихоньку.

Тоже этим занимаюсь. Но с расстановкой простых до 7 включительно. Для центральной девятки уже готово. Для 11-к с краю - в процессе.

-- 31.10.2022, 17:41 --

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

Почему одно? А $32p+2$ вместо $32p-1$? Вроде для длин 10,11,12 вполне допустимо.

Семерка в позиции $32p+2$ для данного паттерна исключается хитрым образом:
1. Если там $7^1$, то приходим к "квадратичному перебору".
2. Если там $7^2$, то в позиции $32p - 5 = 21 q^2$, то есть опять приходим к "квадратичному перебору".
3. С другой стороны, такое размещение $25$ приводит к $32p + 6 = 10 p^2$, то есть опять приходим к "квадратичному перебору".

Итого, наличие $7^1$ или $7^2$ в $32p+2$ (в цепочках 11+) может быть исключено тремя "квадратичными" переборами. Или меньше, если что-то по модулям не пройдёт.

-- 31.10.2022, 17:55 --

Huz

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

Ведь Хьюго заявил, что почти до 3e18 уже всё проверено.

About $T(6,11)$.
What do you think, if we check all possible placements of strings of length 11 up to $10^{19}$, how likely is it to find such a string?
What about up to $10^{20}$?

[Dmitriy40]

До 3e18 нашлось дополнительно:
1904546144979221017: 16, 8, 16, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 64, 6, valids=9, maxlen=9
2862173948232864217: 8, 8, 4, 12, 16, 12, 12, 12, 12, 12, 12, 12, 12,128, 6, valids=9, maxlen=8

Оценил потребное время если на место 32p+2 расставлять простые в квадрате, получать новый паттерн и если расчётное время его счёта до 1e22 на чистом PARI превышает 2с, то компилить ускоритель (за секунду) и считать с ним, получилось достаточно 180ч счёта с ускорителями плюс 5ч счёта без них, т.е. вместо года где-то за неделю в один поток можно проверить до 1e22 конкретно этот паттерн.
Если всего паттернов окажется менее десятка, то можно за пару недель (в мои 4 потока) доказать отсутствие меньшей 11-ки только с квадратами простых. А с кубами и пятыми степенями вроде ещё проще (частично это уже проверил выше).
Программа оценки времени:

up=1e22; L=lcm([32,18,20,75,12,49]); t1=0; t2=0; f=0; print("L=",L);
{forprime(q=13,floor(sqrt(up/L)),
   h=up/L/q^2;
   if(h>2*1.4e6, t1+=h/1e9+1; f=q, t2+=h/1.4e6);\\Если на PARI считать дольше 2с, то делаем ускоритель за 1с и считаем им, иначе на PARI
)}
printf("Times up to %0.3fe20: %0.1fh (<=%d) plus %0.1fh.\n",up/1e20,t1/3600,f,t2/3600);

Вывод:
L=352800
Times up to 100.000e20: 179.5h (<=100613) plus 4.5h.

-- 31.10.2022, 17:59 --

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

About $T(6,11)$.
What do you think, if we check all possible placements of strings of length 11 up to $10^{19}$, how likely is it to find such a string?
What about up to $10^{20}$?

Он уже отвечал (правда не здесь) что по его мнению текущая 11-ка скорее всего и есть минимальная.
И других оценок сделать нельзя.

-- 31.10.2022, 18:04 --

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

Итого, наличие $7^1$ или $7^2$ в $32p+2$ (в цепочках 11+) может быть исключено тремя "квадратичными" переборами. Или меньше, если что-то по модулям не пройдёт.

ОК, только просьба, говорите поточнее что место не исключается, а проверяется другими способами (квадратичными переборами). Иначе неясно ошибка/недосмотр это или что.

[EUgeneUS]

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

получилось достаточно 180ч счёта с ускорителями плюс 5ч счёта без них, т.е. вместо года где-то за неделю в один поток можно проверить до 1e22 конкретно этот паттерн.

Правильно ли понимаю, что если в позиции $32p-1$ стоит не $7^2$, а $7^1$, то время увеличится в семь раз?

Плюс ещё симметричные паттерны...
И это только для одного класса паттернов: "центральная девятка с экзотическим размещением $25$".

Конечно, проверить до 1е22 - заманчиво. Но, ИМХО, за это время лучше бы брутефорсом пройтись до $10^{19}..10^{20}$ по всем паттернам (включая паттерны для 11-ки с краю). Вдруг 11-ка там найдется. Тогда и минимальность доказать можно будет

-- 31.10.2022, 18:22 --

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

Он уже отвечал (правда не здесь) что по его мнению текущая 11-ка скорее всего и есть минимальная.

Пусть $N(n, k)$ - это число, с которого начинается минимальная цепочка длиной ровно $n$ чисел с ровно $k$ делителями.

Я посмотрел, как ведут себя функции $\log (N(n, k))$ для некоторых $k \equiv 0 \pmod{12}$, по данным из файла от уважаемого Хуго.
И очень похоже, что они ведут себя линейно (по $n$).
Проблема в том, что именно для $k=12$ относительно линейного тренда имеется довольно большой расколбас.
Если же линейный тренд таки принять, то получается, что 11-ку можно ожидать, как раз где-то в районе $10^{19}...10^{20}$

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

И других оценок сделать нельзя.

Тут речь, скорее об "экспертных оценках".