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

[Dmitriy40]

О, после исправления глюков и выкидывания дублей осталось ровно 1044, ура.

[Yadryara]

Так, решил подытожить крайне левую группу паттернов. Там где 25-ка на 2-м месте.

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

Посчитать оказалось не сложно, получилось: $11 +11 + 10 + 12 + 12 + 11 + 13 = 80$
Это только для размещения $25$ в позиции 2.

Первые три слагаемых - $7^{(1, 2, 5)}$ в позиции B
Следующие три слагаемых - $7^{(1, 2, 5)}$ в позиции 5
Последнее слагаемое - $7^2$ в позиции 7

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

Я фиксировал степень 7-к и затем расставлял их по местам слева направо.

Вы фиксировали место и затем расставляли на нём 7-ки по возрастанию степени: 1, 2, 5.

Hugo, видимо, тоже фиксировал место и затем расставляли на нём 7-ки, по-другому перебирая степени: 2, 5, 1.

Как обычно, кто во что горазд

Крайне левая группа стартует в списке Hugo с 809-й строки:

$7^1$ в позиции B, до 819 —  11 штук

$7^2$ в позиции 5, до 831 — 12 штук

$7^5$ в позиции 5, до 842 — 11 штук

$7^1$ в позиции 5, до 854 — 12 штук

$7^2$ в позиции 7, до 867 — 13 штук

$7^2$ в позиции B, до 878 — 11 штук

$7^5$ в позиции B, до 888 — 10 штук

Итого крайне левые паттерны расположены в списке Hugo на позициях 809-888. То есть их всего $888-808 = 80$ штук. Или так:

$11 + 12 + 11 + 12 + 13 + 11 + 10 = 80$

[EUgeneUS]

Huz в сообщении #1568748 писал(а):

Yes, I treat those as distinct. I did consider whether I could adapt my code to take advantage of the common parts, but decided that a) it would need a complete rewrite, b) it would be a lot more complex (and so with more bugs), and c) most or all of the savings would be eaten up by the extra complexity.

I think You are absolutely right about your code. Because it is universal and should work with any $k$ and $n$.
But for specific, record-breaking chains, we can try to go the extra mile and arrange a "manual sunrise".

-- 03.11.2022, 07:41 --

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

Паттерн 9-2C-71:
2.2. На место 2 ставим 11^2: v=[1,242,3,20,1,18,7,32,75,2,1,12,11,-70,-9], lcm=6098400, 6 проверяемых мест.

Выше - ошибка. Вот в чём. Мы должны рассматреть _все_ варианты цепочек с поставленным $11^n$. И для такой расстановки у нас есть два варианта, а не один:
1. 9-2C-71-22 (Вы его указали)
2. 9-1B-71-22 в неё оказывается пять проверяемых мест, и этот паттерн пропустили ;(

То есть с учётом перекрытий тут д.б. паттерн 9-1C-71-22, с пятью проверямыми местами.

В общем, не простая задача - учет перекрытий паттернов ;(

[Yadryara]

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

В общем, не простая задача - учет перекрытий паттернов ;(

Ничего, разберёмся. Я до этого ещё дойду.

А пока что крайне правая группа паттернов. Там где 25-ка на месте E.

Крайне правая группа стартует в списке Hugo с 206-й строки:

$7^2$ в позиции 5, до 216-й — 11 штук

$7^5$ в позиции 5, до 226-й — 10 штук

$7^1$ в позиции 5, до 237-й — 11 штук

$7^2$ в позиции 9, до 250-й — 13 штук

$7^2$ в позиции B, до 262-й — 12 штук

$7^5$ в позиции B, до 273-й — 11 штук

$7^1$ в позиции B, до 285-й — 12 штук

Итого крайне правые паттерны расположены в списке Hugo на позициях 206-285. То есть их всего $285-205 = 80$ штук. Или так:

$11 + 10 + 11 + 13 + 12 + 11 + 12 = 80$

[Yadryara]

Левая 75-я группа стартует в списке Hugo со 130-й строки:

$7^2$ в позиции 9, до 142-й — 13 штук

$7^5$ в позиции 9, до 154-й — 12 штук

$7^1$ в позиции 9, до 167-й — 13 штук

$7^2$ в позиции B, до 180-й — 13 штук

$7^5$ в позиции B, до 192-й — 12 штук

$7^1$ в позиции B, до 205-й — 13 штук

$205-129 = 76$ штук


Левая 75-я группа продолжается в списке Hugo с 386-й строки:

$7^2$ в позиции 9, до 395-й — 10 штук

$7^5$ в позиции 9, до 404-й — 9 штук

$7^1$ в позиции 9, до 414-й — 10 штук

$414-385 = 29$ штук


Левая 75-я группа продолжается в списке Hugo с 596-й строки:

$7^2$ в позиции 9, до 607-й — 12 штук

$7^5$ в позиции 9, до 618-й — 11 штук

$7^1$ в позиции 9, до 630-й — 12 штук

$630-595 = 35$ штук


Итого $76 + 29 + 35 = 140$ паттернов.

И уже пошли повторы...

[EUgeneUS]

Yadryara
Не думаю, что эта информация в тексте (в сообщаниях в теме) будет полезна.

Кстати, я уже разложил паттерны уважаемого Хуго на восемь "кучек", в зависимости от
а) размещений $25$
б) вариантов "перекрытий".

Вечером выложу файл с табличками на гуглодиск.

[Yadryara]

EUgeneUS, вот у Вас хороший пример был:

3    4   5     6    7    8     9    A   B   C      D      E   F
.  12p  .  2p^2q  75p  32p  539p  18p  .  20p  3p^2q
   12p  .  2p^2q  75p  32p  539p  18p  .  20p  3p^2q  2p^2q   
        .  2p^2q  75p  32p  539p  18p  .  20p  3p^2q  2p^2q   .      

Учитывая как работают ускорители, это не три паттерна и не один.

А всё же два. Два верхних содержат 6 совершенно одинаковых проверяемых мест. Ускоритель проверит эти 6 мест, а затем, в случае 6 успехов подряд, прога может пошарить вокруг. Таким образом проверив эти два паттерна как один.

А в нижнем 5 проверяемых мест. Его вроде не так просто объединить с верхними.

[Dmitriy40]

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

Выше - ошибка. Вот в чём. Мы должны рассматреть _все_ варианты цепочек с поставленным $11^n$. И для такой расстановки у нас есть два варианта, а не один:
1. 9-2C-71-22 (Вы его указали)
2. 9-1B-71-22 в неё оказывается пять проверяемых мест, и этот паттерн пропустили ;(

Правы, я ошибся. Всё ж руками и глазками.

Но я забил на всю эту возню с паттернами, ведь программная генерация выдала ровно 1044 паттернов, т.е. можно надеяться все возможные. Расширив их до длины 15 и отсортировав по величине шага и начальному числу (которое стало одинаковым для всех лишь сдвинутых паттернов) стало хорошо видно глазками где что можно сократить/совместить. Скомпилил себе все их (и зря, при сокращении иногда можно уменьшить количество проверяемых мест без особого ущерба, но ускоритель другой) и даже часть проверил (например до 1e22 нет решений 10+ с $7^5$ и $11^5$ одновременно).

Надежда досчитать все варианты в этом году и даже в следующем по текущей технологии ускорителей умерла: там 6-8 паттернов с шагом 554400 и всего тремя проверяемыми местами, со скоростью даже 1e9/c (что для трёх мест нереально) считать 200 дней каждый, а всего паттернов с шагом 554400 более 60шт (до сокращений, после останется штук 40). 10к дней на поток это перебор.
С другой стороны, я ошибся выше в программе подсчитывающей ускорение от идеи Hugo размещать лишнее простое в квадрате, там перебор простого надо вести не до $\sqrt{10^{22}/\operatorname{lcm}(...)}$, а в худшем случае до $\sqrt{10^{22}}$ (в лучшем до $\sqrt{10^{22}/11}$ что не сильно меньше), а это простые до 1e11, их же 4.1e9 штук. PARI их перебирать будет (включая и КТО) ну явно не секунды, это и станет основным тормозом. И это для каждого паттерна из нескольких сотен. В общем грустно. Пока думаю как это ускорить и вообще реализовать. А то высокая скорость перебора по паттерну нивелируется малым шагом паттерна.

UPD. Впрочем нет, не всё так страшно, за час справится, на каждый паттерн. А ускорители (порядка 8000 штук на паттерн) будут работать 5 дней.
Т.е. за пару-тройку месяцев в 4 потока можно попытаться справиться со самыми сложными паттернами ...

[EUgeneUS]

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

Учитывая как работают ускорители, это не три паттерна и не один.

Всё таки один.
Проверяем нижний паттерн следующим образом:
1. Проверяем 5 проверяемых мест ускорителями. Никуда от этого не деться.
2. Проверяем места 5, 6, B, D в скрипте. Никуда от этого не деться.
Заметим, что в этих пунктах мы одновременно проверили все три паттерна.
3. И только если нашлась непрерывная девятка в позициях от 5 до D, начинаем проверять края.

-- 03.11.2022, 16:08 --

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

Надежда досчитать все варианты в этом году и даже в следующем по текущей технологии ускорителей умерла: там 6-8 паттернов с шагом 554400 и всего тремя проверяемыми местами,

У меня таких нашлось всего четыре. Вот они:

      [11, 2, 3, 4, 5, 18, 7, 32, 3, 50, 1]
       [1, 2, 3, 4, 5, 18, 7, 32, 3, 50, 11]
                  [11, 50, 3, 32, 7, 18, 5, 4, 3, 2, 1]
                   [1, 50, 3, 32, 7, 18, 5, 4, 3, 2, 11]

Есть ещё 12 паттернов с тремя проверяемыми числами, но там 7 и-или 11 стоят в квадрате.
Вот они:

  [121, 2, 3, 4, 5, 18, 7, 32, 3, 50, 1]
    [1, 2, 3, 4, 5, 18, 7, 32, 3, 50, 121]
              [121, 50, 3, 32, 7, 18, 5, 4, 3, 2, 1]
                [1, 50, 3, 32, 7, 18, 5, 4, 3, 2, 121]

  [11, 2, 3, 4, 5, 18, 49, 32, 3, 50, 1]
   [1, 2, 3, 4, 5, 18, 49, 32, 3, 50, 11]
               [11, 50, 3, 32, 49, 18, 5, 4, 3, 2, 1]
                [1, 50, 3, 32, 49, 18, 5, 4, 3, 2, 11]

  [121, 2, 3, 4, 5, 18, 49, 32, 3, 50, 1]
    [1, 2, 3, 4, 5, 18, 49, 32, 3, 50, 121]
               [121, 50, 3, 32, 49, 18, 5, 4, 3, 2, 1]
                 [1, 50, 3, 32, 49, 18, 5, 4, 3, 2, 121]

-- 03.11.2022, 16:25 --

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

UPD. Впрочем нет, не всё так страшно, за час справится, на каждый паттерн. А ускорители (порядка 8000 штук на паттерн) будут работать 5 дней.
Т.е. за пару-тройку месяцев в 4 потока можно попытаться справиться со самыми сложными паттернами ...

ИМХО, вот на самых сложных паттернах и надо сейчас сосредоточиться.
Они потому и сложные, так как там вариантов много. А значит улучшение оценки $T(6,11)$ в них найти более вероятно.
(Меня не оставляет надежда, что оценка для $T(6,11)$ может быть улучшена на 1.5-2 порядка )

Кстати, у меня 8 потоков на подоконнике простаивают

[Dmitriy40]

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

У меня таких нашлось всего четыре. Вот они:

ОК, какие из моих лишние (в z[] количество делителей для искомой 11-ки)?

v=[  9,  2, 1,  420, 11,  2, 3, 32, 5, 18,  7,    4, 3, 50,  1]; z=[0,0,0,0,2,2,2,6,2,6,2,3,2,6,1]; n=3; pp=Mod(473337,554400);\\@LCM554400-473337-4
v=[  9,  2, 1, 4620,  1,  2, 3, 32, 5, 18,  7,    4, 3, 50, 11]; z=[0,0,0,0,1,2,2,6,2,6,2,3,2,6,2]; n=3; pp=Mod(170937,554400);\\@LCM554400-170937-4
v=[ 45, 14, 1,   12, 11, 50, 3, 32, 7, 18,  5,    4, 3,  2,  1]; z=[0,0,0,0,2,6,2,6,2,6,2,3,2,2,1]; n=3; pp=Mod(175545,554400);\\@LCM554400-175545-4
v=[ 45, 14, 1,  132,  1, 50, 3, 32, 7, 18,  5,    4, 3,  2, 11]; z=[0,0,0,0,1,6,2,6,2,6,2,3,2,2,2]; n=3; pp=Mod(427545,554400);\\@LCM554400-427545-4
v=[ 11,  2, 3,    4,  5, 18, 7, 32, 3, 50,  1,  132, 1, 14, 45]; z=[2,2,2,3,2,6,2,6,2,6,1,0,0,0,0]; n=3; pp=Mod(126841,554400);\\@LCM554400-126841-8
v=[ 11, 50, 3,    4,  7, 18, 5, 32, 3,  2,  1, 4620, 1,  2,  9]; z=[2,6,2,3,2,6,2,6,2,2,1,0,0,0,0]; n=3; pp=Mod(383449,554400);\\@LCM554400-383449-8
v=[  1, 50, 3,    4,  7, 18, 5, 32, 3,  2, 11,  420, 1,  2,  9]; z=[1,6,2,3,2,6,2,6,2,2,2,0,0,0,0]; n=3; pp=Mod( 81049,554400);\\@LCM554400-81049-8
v=[  1,  2, 3,    4,  5, 18, 7, 32, 3, 50, 11,   12, 1, 14, 45]; z=[1,2,2,3,2,6,2,6,2,6,2,0,0,0,0]; n=3; pp=Mod(378841,554400);\\@LCM554400-378841-8

Я не вижу как их можно сократить или объединить, тут все начальные числа сильно разные, значит и цепочки будут разные.

У Вас нет 4-х паттернов с 50 на местах 32p-6, 32p+6. Почему?

[EUgeneUS]

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

У Вас нет 4-х паттернов с 50 на местах 32p-6, 32p+6. Почему?

Потому что они лежали в кучке, про которую думал, что всё хорошо.
А не всё хорошо... Да, вы правы, "сильно плохих паттернов" - восемь.

-- 03.11.2022, 16:47 --

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

Я не вижу как их можно сократить или объединить,

Объединение паттернов позволяет (если повезёт), считая "плохой" паттерн, за одно проверить от 1 до 4 других.
Относительно 8-ми "плохих" паттернов.

1. Четыре штуки, которые я пропустил выше, ни с чем не объединяются.
2. Из оставшихся четырёх:

2.1. Вот эти два:

  [11, 2, 3, 4, 5, 18, 7, 32, 3, 50, 1]
               [1, 50, 3, 32, 7, 18, 5, 4, 3, 2, 11]

ни с чем не объединяются.

2.2. А вот эти два:

   [1, 2, 3, 4, 5, 18, 7, 32, 3, 50, 11]
              [11, 50, 3, 32, 7, 18, 5, 4, 3, 2, 1]

можно попробовать объединить с четырьмя другими (каждый)

[Dmitriy40]

При проверке до 1e22 паттерна с 4 проверяемыми местами и шагом 56818792800 затрачено 2455с, т.е. для 4-х проверяемых мест скорость вместо 1e9/c составила лишь 7e7/с. Вот почему я тогда для сравнения с Hugo брал 2e7/c (похоже для 3 проверяемых мест она такая и будет) ...
С 5 проверяемыми местами паттерна с тем же шагом затрачено 884с и скорость составила 2e8/c.
С 6 проверяемыми местами паттерна с тем же шагом затрачено 241с и скорость составила 7.3e8/c.
С 7 проверяемыми местами паттерна с тем же шагом затрачено 103с и скорость составила 1.7e9/c.

[EUgeneUS]

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

Видимо что-то ещё не оптимально и в PARI переборе ...

А Вы для каждой кандидатной цепочки сколько чисел в PARI проверяете?
Если паттерны не объединяются (считаем независимо по всем 1044), то достаточно проверять до первого неуспеха.
При этом оставшиеся числа будут иметь разную вероятность успеха. Соответственно, их нужно проверять от меньшей вероятности успеха к большей.
Это даст некоторую экономию времени.

[Yadryara]

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

до 1e22 нет решений 10+ с $7^5$ и $11^5$ одновременно)

И сколько таких паттернов проверено?

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

1. Проверяем 5 проверяемых мест ускорителями. Никуда от этого не деться.

Почему же не деться. Можно проверять 6 проверяемых мест ускорителями.

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

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

Может быть стоит сделать иерархию паттернов по количеству проверяемых мест.

[Dmitriy40]

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

А Вы для каждой кандидатной цепочки сколько чисел в PARI проверяете?

Нет, теперь уже понятно что PARI ни при чём, 1.7e9/с отличная скорость, даже выше расчётной.
Вообще же код проверки такой:

if(!ispseudoprime((h+d1-1)/v[d1]) || !ispseudoprime((h+d2-1)/v[d2]) || !ispseudoprime((h+d3-1)/v[d3]) || !ispseudoprime((h+d4-1)/v[d4]), next);
for(d=5,#dd, if(!ispseudoprime((h+dd[d]-1)/v[dd[d]]), next(2)));
if(z[7]!=6 && numdiv(h+7-1)!=12, next);
if(z[9]!=6 && numdiv(h+9-1)!=12, next);

В dd[] сидят номера проверяемых мест в паттерне, левые 4 из которых продублированы и в dX (для ускорения). Т.е. сначала быстро проверяются левые 4 из всех проверяемых мест, потом немного медленнее все оставшиеся проверяемые места, потом медленно два числа вокруг 32p (если не проверены ранее), потом совсем медленно делители всей цепочки и в лог.
Это же ещё не готовая программа, лишь поиграться для тестов, потому оптимизацией сильно не заморачивался. Но думаю много и не выжать.

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

И сколько таких паттернов проверено?

Все возможные, до сокращения было 58шт, все и проверены, так как это произошло слишком быстро (в среднем порядка секунды на каждый паттерн), то выбросом похожих не успел заняться.

Yadryara, EUgeneUS
По реальной скорости смотрите предыдущее сообщение, я там добавил все варианты (кроме самого медленного, до него ещё не дошёл). И не забывайте что это x64 AVX2.

-- 03.11.2022, 17:57 --

Запустил проверку всех 210 (после сокращения осталось 177) паттернов с $11^5$ (58 из них уже проверены из-за наличия и $7^5$). Там 10 паттернов с 4 проверяемыми местами, остальные с 5 и 6, за сутки думаю проверятся.
Потом на очереди 152 (до сокращения) паттерна с $7^5$ и $11^2$ с шагом 14642258400 плюс 66 (тоже до сокращения) паттерна с $7^5$ и $11^1$ с шагом 1331114400. И это уже надолго.