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

[Yadryara]

Dmitriy40, всё-таки стали с одним выброшенным квадратом(с одним нулём) считать? Только расширенные комплекты на 94 группы? Или только по 30 дополнительных групп считаете?

[Dmitriy40]

Да разное я считаю, то одно, то другое, то третье, а то пятое. А то оказывается что первое и третье считал не то чтобы зря, но как-то странно и лучше бы пересчитать ... И не просто пересчитать, а перекомпилить и потом пересчитать. Хотя результат вроде и совпадает ...
Не обращайте внимания, планируйте свою с Демисом работу спокойно.

[Yadryara]

Оказывается нашу тему обсуждают не только здесь. Но уровень обсуждения...

Например, обсуждающие не понимают, что невозможность 12-16 давным-давно доказана. Эдак 4-5 лет назад, а то и раньше. Все ссылки в начале темы даны.

Ну и многие другие вещи не понимают. С целью разъяснения и пишу настоящий обзор.

Итак, тема стартовала 1 февраля, а 6 апреля уже было объявлено о решении главной задачи темы: первый Пентадекатлон(цепочка 12-15) был найден.

И почти одновременно нашлись ещё два Пентадекатлона повыше.

Затем люди разделились и стали решать другие задачи. Цепочками с 12-ю делителями продолжил заниматься только впс. При технической поддержке Dmitriy40.

Выбранный мной способ состоял в замене квадратов простых в эталонном комплекте паттернов на другие.

А каково было предполагаемое количество этих замен? В предположении, что новый Пентадекатлон не найдётся, только для $37^2$ нужно было сделать

$$\pi\left(\sqrt{\frac{66388\cdot10^{33}}{48\cdot(2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31)^2}}\right)=440070$$

замен.

То есть одна только компиляция заняла бы

$$\frac{10\cdot 440070}{24\cdot365}\approx502.36$$

502 года только на одну компиляцию комплектов только для одной замены только одного числа! Про стартовые точки я тогда предпочёл пока не задумываться.

Это на моём компе и при тогдашнем способе компиляции.

Продолжение следует...

[Yadryara]

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

Итак, мне помогли и 8 августа был найден ещё один Пентадекатлон. Аж в 12 раз меньше минимально известного. Сколько комплектов теперь считать?

$$\pi\left(\sqrt{\frac{5401\cdot10^{33}}{48\cdot(2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31)^2}}\right)=126213$$

Здесь в числителе уже величина новой 15-шки(Пентадекатлона). А компиляцию я уже научился делать за 8, а не за 10 часов, так что меняем в числителе два числа:

$$\frac{8\cdot 126213}{24\cdot365}\approx115.26$$

Ну во теперь уже всего лишь 115 лет, только на одну компиляцию комплектов только для одной замены только одного числа. Экие пустяки

Затем мне снова очень помогли и 15 августа был найден ещё один, пятый по счёту, Пентадекатлон. Аж в 55 раз меньше нового минимально известного! И в 679(!!) раз меньше самого первого, который использовался для расчёта. Сколько комплектов теперь считать?

Этот расчёт был проведён чуть раньше, на предыдущей странице — 24 года только на одну компиляцию комплектов только для одной замены только одного числа.

Но! Важный момент: уважаемый Dmitriy40 наконец-то согласился переписать код. В частности был применён метод с выбрасыванием $37^2$. И теперь необходимая компиляция заняла у меня даже меньше 8 часов.

Особо обращаю внимание: не 502 года, а 8 часов!

Счёт именно у меня может занять до 5 лет. Но подчёркиваю: это в худшем случае. То есть если не найдётся непрерывная 14-ка ниже 182213е30.

А она скоро найдётся. Потому что три 14-ки уже нашлись гораздо ниже. Но об этом позже.

[Dmitriy40]

Пожалуй добавлю почему было мало смысла переписывать код раньше.
Не нашёл скорость счёта одиночных комплектов у Yadryara, возьму свою, она составила 156с на интервал 1e38 на каждый паттерн, или проверка всего диапазона до 66388e33 по 46080 паттернам занимает 55 дней (в один поток), на самом деле даже несколько больше. Дополнительное время в 10ч на компиляцию на этом фоне совершенно ничтожно. Потому мысли о переписывании кода стал проверять лишь когда время счёта снизилось до считанных часов и тратить 8-10 часов на компиляцию стало откровенно жалко.

И вот теперь можно прикинуть общее время счёта по одной строке одной таблицы, для определённости возьмём ту же строку с заменой 37 первой таблицы. Если считать все 440 тысяч замен, то кроме 500 лет на компиляцию ещё и счёт займёт 440 тысяч раз по 55 дней (до известной тогда 15-ки, 66388e33) или 66 тысяч лет (на самом деле где-то вдвое меньше, но уже не суть). А до 1.8222e35 нужно 26600 комплектов, их компиляция заняла бы $8\cdot26600/24/365=24.3$ лет, а счёт по 3.6ч на комплект или 11 лет, суммарно 35 лет.
После смены парадигмы компиляция занимает 8 часов вместо 24 лет, а счёт 5 лет. Суммарно получается 5 лет вместо 35.
И текущей парадигмы хватит как минимум до уменьшения границы счёта вновь до считанных часов на счёт, или в десяток тысяч раз! Т.е. это надо найти 15-ку (ну и 14-ку тоже) менее 1e31. А по первой таблице (с одной заменой) её там точно нет. Так что пока не найдётся 15-ка менее 1е31 по другим таблицам первую таблицу выгоднее считать по новому, строками (а когда вдруг найдётся, первую таблицу считать уже станет и вообще не нужно, ни по строкам, ни отдельными комплектами).

[Yadryara]

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

Потому что три 14-ки уже нашлись гораздо ниже.

На настоящий момент уже четыре 14-ки найдены новым способом.

Вашему вниманию вновь предлагается таблица наименьших известных 14-к до первой непрерывной. Таблица изменилась чуть ли не до неузнаваемости:

$\tikz[scale=.08]{ \fill[green!90!blue!50] (94,160) rectangle (107,170); \fill[green!90!blue!70] (0,140) rectangle (156,150); \draw (0,210) rectangle (10,220); \draw (10,210) rectangle (94,220); \draw (94,210) rectangle (107,220); \draw (107,210) rectangle (139,220); \draw (139,210) rectangle (146,220); \draw (146,210) rectangle (156,220); \draw (0,200) rectangle (10,210); \draw (10,200) rectangle (94,210); \draw (94,200) rectangle (107,210); \draw (107,200) rectangle (139,210); \draw (139,200) rectangle (146,210); \draw (146,200) rectangle (156,210); \draw (0,190) rectangle (10,200); \draw (10,190) rectangle (94,200); \draw (94,190) rectangle (107,200); \draw (107,190) rectangle (139,200); \draw (139,190) rectangle (146,200); \draw (146,190) rectangle (156,200); \draw (0,180) rectangle (10,190); \draw (10,180) rectangle (94,190); \draw (94,180) rectangle (107,190); \draw (107,180) rectangle (139,190); \draw (139,180) rectangle (146,190); \draw (146,180) rectangle (156,190); \draw (0,170) rectangle (10,180); \draw (10,170) rectangle (94,180); \draw (94,170) rectangle (107,180); \draw (107,170) rectangle (139,180); \draw (139,170) rectangle (146,180); \draw (146,170) rectangle (156,180); \draw (0,160) rectangle (10,170); \draw (10,160) rectangle (94,170); \draw (94,160) rectangle (107,170); \draw (107,160) rectangle (139,170); \draw (139,160) rectangle (146,170); \draw (146,160) rectangle (156,170); \draw (0,150) rectangle (10,160); \draw (10,150) rectangle (94,160); \draw (94,150) rectangle (107,160); \draw (107,150) rectangle (139,160); \draw (139,150) rectangle (146,160); \draw (146,150) rectangle (156,160); \draw (0,140) rectangle (10,150); \draw (10,140) rectangle (94,150); \draw (94,140) rectangle (107,150); \draw (107,140) rectangle (139,150); \draw (139,140) rectangle (146,150); \draw (146,140) rectangle (156,150); \node at (5.2,215) {\text{1.}}; \node at (57,215){\text{3797306190383689322319167788441}}; \node at (100.3,215){\text{128}}; \node at (123,215){\text{S9-32-204531}}; \node at (142.4,215){\text{2}}; \node at (150.8,215){\text{Dm}}; \node at (5.2,205) {\text{2.}}; \node at (55,205){\text{259037697563588532195140710301145}}; \node at (100.3,205){\text{16}}; \node at (123,205){\text{N9-73-421506}}; \node at (142.4,205){\text{D}}; \node at (150.8,205){\text{Dm}}; \node at (5.2,195) {\text{3.}}; \node at (55,195){\text{937749576115599672133078413902041}}; \node at (100.3,195){\text{16}}; \node at (123,195){\text{S9-26-536401}}; \node at (142.4,195){\text{9}}; \node at (150.8,195){\text{De}}; \node at (5.2,185) {\text{4.}}; \node at (54,185){\text{9687936215599602783812822055365145}}; \node at (100.3,185){\text{16}}; \node at (123,185){\text{N2-45-652403}}; \node at (142.4,185){\text{E}}; \node at (150.8,185){\text{De}}; \node at (5.2,175) {\text{5.}}; \node at (53,175){\text{81208614941517230882469765804509145}}; \node at (100.3,175){\text{24}}; \node at (123,175){\text{N2-56-354126}}; \node at (142.4,175){\text{9}}; \node at (150.8,175){\text{Dm}}; \node at (5.2,165) {\text{6.}}; \node at (52,165){\text{139851236562860254263595357318785945}}; \node at (100.3,165){\text{6}}; \node at (123,165){\text{N2-36-531426}}; \node at (142.4,165){\text{3}}; \node at (150.8,165){\text{Dm}}; \node at (5.2,155) {\text{7.}}; \node at (52,155){\text{173897306650291046911304836208174041}}; \node at (100.3,155){\text{48}}; \node at (123,155){\text{S9-36-345216}}; \node at (142.4,155){\text{3}}; \node at (150.8,155){\text{Dm}}; \node at (5.2,145) {\text{8.}}; \node at (52,145){\text{182212015721072444191301392660439641}}; \node at (100.3,145){\text{24}}; \node at (123,145){\text{S9-31-258471}}; \node at (142.4,145){\text{F}}; \node at (150.8,145){\text{De}}; }$

Слева направо:

1. Место 14-ки по возрастанию.

2. Первое число цепочки.

3. Плохое количество делителей.

4. Уникальное имя паттерна. Все четыре 14-ки, найденные новым способом, занимают первые 4 места и содержат "0" в имени паттерна.

5. Шестнадцатеричный порядковый номер места с плохим числом.

6. Кто нашёл.

[Yadryara]

Некоторые коменты к таблице выше.

По нулю легко видеть новые номера комплектов. Они выстроились по убыванию: на первом месте 37-й, далее 23-й, 19-й и 17-й.

Плохое количество делителей для нового способа — степень двойки. За редчайшим исключением. Выше рассказывал, что нашёл всего лишь 12 цепочек без степени двойки. 12 из 2181.

Когда найдётся новая рекордная непрерывная 14-ка? Все знают, что прогнозы дело неблагодарное.

Вот пример очень аккуратного прогноза:

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

Полагаю, 15 будет в этом году.

Ну я могу чуток рискнуть и сказать, что нужная 14-ка найдётся не позднее 1 октября. Сего года.

[Huz]

The translation of my code into C is starting to look robust now. There are still improvements to make, but I have been able to do $p_x$ "capped" runs - allocating primes only up to some limit - to show that any improved solution for D(12,13) must include some prime power in $\{ p^2, p^5, p^{11} \}$ with $p > 50$.

Timings for the capped runs with my latest code: $p_x=30$ in 40 minutes; $p_x=40$ in 4.3h, $p_x=50$ in 13h. (By contrast for D(12,10) I can check $p_x=1000$ in an hour, while estimated running time for $p_x=\inf$ is about 30 days.)

[Dmitriy40]

Yadryara
Вот Вам ещё одна 14-ка на 2.5 место:
S2-46-503162:517323644441352164508238287911641: 12, 8, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, valids=14, maxlen=13, ALL

[Yadryara]

Да, вижу это 29-й комплект. Кстати, ведь могут быть ещё и гибридные паттерны : один квадрат заменён, а второй выкинут. Например 012347. Повторов только у таких будет больше и их надо как-то отсекать.

[Dmitriy40]

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

Кстати, ведь могут быть ещё и гибридные паттерны : один квадрат заменён, а второй выкинут. Например 012347.

Они все покрываются второй таблицей, с двумя заменами. Можно конечно раздербанить её на несколько по одному из чисел, но там и так всего 15 строк, а этих одиночных замен снова будет 26600 штук или около того. Ну и зачем? Быстрее проверить вторую таблицу всю построчно.

[Yadryara]

А можно я тоже вопросом на вопрос отвечу?

Первая таблица тоже ведь полностью покрывается второй. Зачем же мы её считаем?

Вторая таблица тоже ведь полностью покрывается третьей. Зачем же Вы её считали?

...

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

Я знаю ответы.

[Dmitriy40]

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

Пятая таблица тоже ведь полностью покрывается шестой. Почему же её никто не считает?

Почему никто? Я её считал. Шестую. И пятую. Но найти в них 15-ку и 14-ку можно разве только совсем случайно. А вот 9-ки (непрерывные конечно) находились достаточно быстро.

В принципе ничто не мешает разбить вторую таблицу на много первых и считать их построчно. Вопрос лишь сколько этих вариантов будет. А их будет уж не меньше чем ячеек в первой таблице. Те самые 500 лет только на компиляцию только одной строки, а их 15 ... Впрочем может и повезти и цепочки найдутся быстро.

[Yadryara]

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

Пятая таблица тоже ведь полностью покрывается шестой. Почему же её никто не считает?

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

Почему никто? Я её считал.

Обратите внимание, я же специально написал в настоящем времени: "не считает".

Я знал, что раньше(где-то в феврале-марте) Вы её считали и недавно цитировал.

Между тем, ещё одна 14-ка нашлась. Кое-кто считает уже в 16 потоков.

Итого уже 6 новых 14-к. Раньше(при старом способе) при таких настройках большого ифа как у Демиса (1, 13, 14, 15) можно было ожидать 1 непрерывную 14-ку на 6-7 обычных.

[Dmitriy40]

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

Обратите внимание, я же специально написал в настоящем времени: "не считает".
Я знал, что раньше(где-то в феврале-марте) Вы её считали и недавно цитировал.

Обратите внимание, и шестую и пятую таблицы я считал совсем недавно, неделю назад. То что я об этом не сказал - ну так и не было найдено ничего интересного (14-ки или 15-ки или хоть 13-ки). Хотя, ведь сказал же.