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

[VAL]

Между делом нашлось. $M(360)\ge 8$

(Оффтоп)

475606610585772445091412800179457949994548799355265350154168140099702446493501093036933118

К вопросу о том, может длинная цепочка случайно найтись рано.
Запустил всего один поток. Потребовалось порядка 32 миллионов шагов, т.е. примерно в 30 раз меньше, чем ожидалось.

PS: Это сообщение открыло 100-ю страницу темы

PPS: Надо бы уточнить верхнюю оценку.

======== Таблицы от Антона Никонова =========

Здесь речь идёт о задачах минимизации, то есть о нахождении минимально возможного числа, с которого начинается та или иная цепочка из различного количества последовательных чисел, каждое из которых имеет ровно 12 делителей.

Эти задачи уже решены для цепочек, состоящих из не более чем 12 последовательных чисел, каждое из которых имеет ровно 12 делителей.

Вашему вниманию предлагается таблица наименьших таких цепочек длиной 13.

$\tikz[scale=.08]{ \draw (0,210) rectangle (10,220); \draw (10,210) rectangle (89,220); \draw (89,210) rectangle (119,220); \draw (119,210) rectangle (133,220); \draw (133,210) rectangle (141,220); \draw (141,210) rectangle (151,220); \draw (0,200) rectangle (10,210); \draw (10,200) rectangle (89,210); \draw (89,200) rectangle (119,210); \draw (119,200) rectangle (133,210); \draw (133,200) rectangle (141,210); \draw (141,200) rectangle (151,210); \draw (0,190) rectangle (10,200); \draw (10,190) rectangle (89,200); \draw (89,190) rectangle (119,200); \draw (119,190) rectangle (133,200); \draw (133,190) rectangle (141,200); \draw (141,190) rectangle (151,200); \draw (0,180) rectangle (10,190); \draw (10,180) rectangle (89,190); \draw (89,180) rectangle (119,190); \draw (119,180) rectangle (133,190); \draw (133,180) rectangle (141,190); \draw (141,180) rectangle (151,190); \draw (0,170) rectangle (10,180); \draw (10,170) rectangle (89,180); \draw (89,170) rectangle (119,180); \draw (119,170) rectangle (133,180); \draw (133,170) rectangle (141,180); \draw (141,170) rectangle (151,180); \draw (0,160) rectangle (10,170); \draw (10,160) rectangle (89,170); \draw (89,160) rectangle (119,170); \draw (119,160) rectangle (133,170); \draw (133,160) rectangle (141,170); \draw (141,160) rectangle (151,170); \draw (0,150) rectangle (10,160); \draw (10,150) rectangle (89,160); \draw (89,150) rectangle (119,160); \draw (119,150) rectangle (133,160); \draw (133,150) rectangle (141,160); \draw (141,150) rectangle (151,160); \draw (0,140) rectangle (10,150); \draw (10,140) rectangle (89,150); \draw (89,140) rectangle (119,150); \draw (119,140) rectangle (133,150); \draw (133,140) rectangle (141,150); \draw (141,140) rectangle (151,150); \draw (0,130) rectangle (10,140); \draw (10,130) rectangle (89,140); \draw (89,130) rectangle (119,140); \draw (119,130) rectangle (133,140); \draw (133,130) rectangle (141,140); \draw (141,130) rectangle (151,140); \draw (0,120) rectangle (10,130); \draw (10,120) rectangle (89,130); \draw (89,120) rectangle (119,130); \draw (119,120) rectangle (133,130); \draw (133,120) rectangle (141,130); \draw (141,120) rectangle (151,130); \node at (5.3,215) {\text{1.}}; \node at (56,215){\text{586683019466361719763403545}}; \node at (104.4,215){\text{N2-45-256100}}; \node at (126.5,215){\text{8,32}}; \node at (137,215){\text{EF}}; \node at (146,215){\text{Dm}}; \node at (5.3,205) {\text{2.}}; \node at (53,205){\text{108733328714439697994931120345}}; \node at (104.4,205){\text{N2-56-512400}}; \node at (126.5,205){\text{32,4}}; \node at (137,205){\text{EF}}; \node at (146,205){\text{Dm}}; \node at (5.3,195) {\text{3.}}; \node at (53,195){\text{227666845709438395029674265945}}; \node at (104.4,195){\text{N2-50-541200}}; \node at (126,195){\text{16,16}}; \node at (137,195){\text{EF}}; \node at (146,195){\text{Dm}}; \node at (5.3,185) {\text{4.}}; \node at (53,185){\text{613325178838387028899008062041}}; \node at (104.4,185){\text{S2-41-001342}}; \node at (126,185){\text{4,16}}; \node at (137,185){\text{12}}; \node at (146,185){\text{Dm}}; \node at (5.3,175) {\text{5.}}; \node at (52,175){\text{1131687019435887932785738910041}}; \node at (104.4,175){\text{S2-41-302510}}; \node at (126,175){\text{8,48}}; \node at (137,175){\text{EF}}; \node at (146,175){\text{Dm}}; \node at (5.3,165) {\text{6.}}; \node at (52,165){\text{1439314756106602937022269702041}}; \node at (104.4,165){\text{S9-34-002341}}; \node at (126,165){\text{16,8}}; \node at (137,165){\text{12}}; \node at (146,165){\text{Dm}}; \node at (5.3,155) {\text{7.}}; \node at (52,155){\text{1932741770848588276411450776345}}; \node at (104.4,155){\text{N2-15-402310}}; \node at (126,155){\text{32,4}}; \node at (137,155){\text{EF}}; \node at (146,155){\text{Hu}}; \node at (5.3,145) {\text{8.}}; \node at (52,145){\text{3416710478784278632105449158041}}; \node at (104.4,145){\text{S9-26-004213}}; \node at (126.2,145){\text{2,8}}; \node at (137,145){\text{12}}; \node at (146,145){\text{Dm}}; \node at (5.3,135) {\text{9.}}; \node at (52,135){\text{3571541827470111796155912172441}}; \node at (104.4,135){\text{S2-26-203041}}; \node at (126,135){\text{288,16}}; \node at (137,135){\text{12}}; \node at (146,135){\text{Dm}}; \node at (5.2,125) {\text{10.}}; \node at (52,125){\text{3797306190383689322319167788441}}; \node at (104.4,125){\text{S9-32-204531}}; \node at (126,125){\text{128}}; \node at (137,125){\text{2}}; \node at (146,125){\text{Dm}}; }$

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

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

2. Первое число цепочки из 15 последовательных чисел, всегда равное $32p-7$, где $p$ простое.

3. Уникальное имя паттерна.

4. Все плохие($\neq12$) количества делителей среди этих 15 чисел.

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

6. Кто нашёл.


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

$\tikz[scale=.08]{ \draw (0,210) rectangle (10,220); \draw (10,210) rectangle (94,220); \draw (94,210) rectangle (107,220); \draw (0,200) rectangle (10,210); \draw (10,200) rectangle (94,210); \draw (94,200) rectangle (107,210); \draw (0,190) rectangle (10,200); \draw (10,190) rectangle (94,200); \draw (94,190) rectangle (107,200); \draw (0,180) rectangle (10,190); \draw (10,180) rectangle (94,190); \draw (94,180) rectangle (107,190); \draw (0,170) rectangle (10,180); \draw (10,170) rectangle (94,180); \draw (94,170) rectangle (107,180); \draw (0,160) rectangle (10,170); \draw (10,160) rectangle (94,170); \draw (94,160) rectangle (107,170); \draw (0,150) rectangle (10,160); \draw (10,150) rectangle (94,160); \draw (94,150) rectangle (107,160); \draw (0,140) rectangle (10,150); \draw (10,140) rectangle (94,150); \draw (94,140) rectangle (107,150); \draw (0,130) rectangle (10,140); \draw (10,130) rectangle (94,140); \draw (94,130) rectangle (107,140); \draw (0,120) rectangle (10,130); \draw (10,120) rectangle (94,130); \draw (94,120) rectangle (107,130); \node at (5.3,215) {\text{1.}}; \node at (54,215){\text{ 182417228439838813052353038969945}}; \node at (100.3,215){\text{De}}; \node at (123,215){\text{}}; \node at (142.4,215){\text{}}; \node at (150.8,215){\text{}}; \node at (5.3,205) {\text{2.}}; \node at (54,205){\text{1966089440441196672524986345512345}}; \node at (100.3,205){\text{Dm}}; \node at (123,205){\text{}}; \node at (142.4,205){\text{}}; \node at (150.8,205){\text{}}; \node at (5.3,195) {\text{3.}}; \node at (54,195){\text{3051183708749776744662169818575641}}; \node at (100.3,195){\text{Dm}}; \node at (123,195){\text{}}; \node at (142.4,195){\text{}}; \node at (150.8,195){\text{}}; \node at (5.3,185) {\text{4.}}; \node at (54,185){\text{5536971777226727622137176815138841}}; \node at (100.3,185){\text{Dm}}; \node at (123,185){\text{}}; \node at (142.4,185){\text{}}; \node at (150.8,185){\text{}}; \node at (5.3,175) {\text{5.}}; \node at (54,175){\text{5625796463484324070009617271709145}}; \node at (100.3,175){\text{Dm}}; \node at (123,175){\text{}}; \node at (142.4,175){\text{}}; \node at (150.8,175){\text{}}; \node at (5.3,165) {\text{6.}}; \node at (53,165){\text{11865604480910140781102260713619545}}; \node at (100.3,165){\text{Na}}; \node at (123,165){\text{}}; \node at (142.4,165){\text{}}; \node at (150.8,165){\text{}}; \node at (5.3,155) {\text{7.}}; \node at (53,155){\text{12641644871583861275062199467757145}}; \node at (100.3,155){\text{Na}}; \node at (123,155){\text{}}; \node at (142.4,155){\text{}}; \node at (150.8,155){\text{}}; \node at (5.3,145) {\text{8.}}; \node at (53,145){\text{14202875425368849513510319626984345}}; \node at (100.3,145){\text{De}}; \node at (123,145){\text{}}; \node at (142.4,145){\text{}}; \node at (150.8,145){\text{}}; \node at (5.3,135) {\text{9.}}; \node at (53,135){\text{14338620420493961557283066155430041}}; \node at (100.3,135){\text{Na}}; \node at (123,135){\text{}}; \node at (142.4,135){\text{}}; \node at (150.8,135){\text{}}; \node at (5.2,125) {\text{10.}}; \node at (53,125){\text{18154091233136257708912076431017945}}; \node at (100.3,125){\text{Dm}}; \node at (123,125){\text{}}; \node at (142.4,125){\text{}}; \node at (150.8,125){\text{}}; }$

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

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

2. Первое число цепочки из 15 последовательных чисел, всегда равное $32p-7$, где $p$ простое.

3. Кто нашёл.


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

$\tikz[scale=.08]{ \draw (0,210) rectangle (10,220); \draw (10,210) rectangle (98,220); \draw (98,210) rectangle (128,220); \draw (128,210) rectangle (138,220); \draw (0,200) rectangle (10,210); \draw (10,200) rectangle (98,210); \draw (98,200) rectangle (128,210); \draw (128,200) rectangle (138,210); \draw (0,190) rectangle (10,200); \draw (10,190) rectangle (98,200); \draw (98,190) rectangle (128,200); \draw (128,190) rectangle (138,200); \draw (0,180) rectangle (10,190); \draw (10,180) rectangle (98,190); \draw (98,180) rectangle (128,190); \draw (128,180) rectangle (138,190); \draw (0,170) rectangle (10,180); \draw (10,170) rectangle (98,180); \draw (98,170) rectangle (128,180); \draw (128,170) rectangle (138,180); \draw (0,160) rectangle (10,170); \draw (10,160) rectangle (98,170); \draw (98,160) rectangle (128,170); \draw (128,160) rectangle (138,170); \node at (5.2,215) {\text{1.}}; \node at (57.1,215){\text{80215613469168729088982885848674841}}; \node at (113,215){\text{S9-45-304251}}; \node at (133,215){\text{Na}}; \node at (5.2,205) {\text{2.}}; \node at (57.1,205){\text{97648097903866012734106659998399641}}; \node at (113,205){\text{S9-36-587241}}; \node at (133,205){\text{De}}; \node at (5.2,195) {\text{3.}}; \node at (55.1,195){\text{5400788496821420197301806862543165145}}; \node at (113,195){\text{N2-51-74A213}}; \node at (133,195){\text{Na}}; \node at (5.2,185) {\text{4.}}; \node at (54.1,185){\text{66387422053662391209161093722597723545}}; \node at (113,185){\text{N2-46-653421}}; \node at (133,185){\text{Dm}}; \node at (5.2,175) {\text{5.}}; \node at (54.1,175){\text{75847648332862724576017454918623133145}}; \node at (113,175){\text{N9-32-216345}}; \node at (133,175){\text{Ar}}; \node at (5.2,165) {\text{6.}}; \node at (54.1,165){\text{91340991749658028244987380473874205145}}; \node at (113,165){\text{N9-25-241356}}; \node at (133,165){\text{Eu}}; }$

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

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

2. Первое число цепочки из 15 последовательных чисел, всегда равное $32p-7$, где $p$ простое.

3. Уникальное имя паттерна.

4. Кто нашёл.

Ar — Артём Заржецкий
De — Демис
Dm — Дмитрий Петухов
Eu — Евгений Жилицкий
Hu — Hugo van der Sanden
Na — Наталия Макарова.

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

$\tikz[scale=.08]{ \fill[green!90!blue!50] (10,220) rectangle (130,230); \draw[step=10cm] (0,210) grid +(160,20); \node at (5,225) {\text{len}}; \node at (15,225){\text{1}}; \node at (25,225){\text{2}}; \node at (35,225){\text{3}}; \node at (45,225){\text{4}}; \node at (55,225){\text{5}}; \node at (65,225){\text{6}}; \node at (75,225){\text{7}}; \node at (85,225){\text{8}}; \node at (95,225){\text{9}}; \node at (105,225){\text{10}}; \node at (115,225){\text{11}}; \node at (125,225){\text{12}}; \node at (135,225){\text{13}}; \node at (145,225){\text{14}}; \node at (155,225){\text{15}}; \node at (5,215){\text{12}}; \node at (15,215)[red]{\text{5.91}}; \node at (25,215)[red]{\text{3.68}}; \node at (35,215)[red]{\text{2.10}}; \node at (45,215){\text{1.85}}; \node at (55,215){\text{1.58}}; \node at (65,215){\text{1.91}}; \node at (75,215){\text{1.96}}; \node at (85,215){\text{1.90}}; \node at (95,215){\text{1.58}}; \node at (105,215){\text{1.88}}; \node at (115,215){\text{1.95}}; \node at (125,215){\text{1.79}}; \node at (135,215){\text{1.85}}; \node at (145,215)[red]{\text{2.00}}; \node at (155,215){\text{1.96}}; }$

Светло-зелёным обозначены те длины цепочек, минимальность которых Hugo считает доказанной.

По состоянию на 14 июля 2023 года по сравнению с таблицей от 11-го апреля 2022 года

10-ка уменьшена в 238 раз;
11-ка уменьшена в 1055 раз;
12-ка уменьшена в 1564 разa;
__________________________
13-ка уменьшена в 3294 раза;
14-ка уменьшена в 26832 раза;
15-ка уменьшена в 827 раз.

[mathematician123]

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

PPS: Надо бы уточнить верхнюю оценку.

Моя программа даёт оценку $M(360) \le 119$. Но, может быть, у Hugo оценка будет точнее.

Используется синтаксис Python

def gcd(a, b):
    if a == 0 or b == 0:
        return a+b
    return gcd(b, a%b)
            
m = 2**9 * 3**4 * 5**4
bound = 0
Mbound = 0

def condition(x): # Возвращает True, если остаток является запрещённым

    # set 1 in Hugo notation
    d = [2**6, 2**7 * 3, 2**7 * 5, 2**3 * 3**3, 2**3 * 5**3, 3**3 * 5**3, 2**3 * 3 * 5, 3**3 * 2 * 5, 5**3 * 2 * 3, 2**8 * 3**2, 2**8 * 5**2, 2**2 * 3**2 * 5**2]
    for dd in d:
        if (x%dd == 0) and (gcd(x//dd, dd) == 1):
            return True
        
    # set 2 in Hugo notation
    d = [2**7, 2**3 * 3, 2**3 * 5, 3**3 * 2, 3**3 * 5, 5**3 * 2, 5**3 * 3, 2 * 3 * 5]
    for dd in d:
        if (x%dd == 0) and (gcd(x//dd, dd) == 1):
            if ((x//dd)%3 == 2) or ((x//dd)%4 == 3) or ((x//dd)%5 == 2) or ((x//dd)%5 == 3):
                return True

for x in range(m + 65):
    if condition(x):
        if bound > Mbound:
            Mbound = bound
        bound = 0
    else:
        bound += 1

print("M(360) <= ", Mbound)

 

[VAL]

mathematician123 в сообщении #1560361 писал(а):

Моя программа даёт оценку $M(360) \le 119$.

Спасибо!

[Huz]

mathematician123 в сообщении #1560361 писал(а):

Моя программа даёт оценку $M(360) \le 119$. Но, может быть, у Hugo оценка будет точнее.

I also get 119.

[VAL]

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

I also get 119

Thanks!

[Dmitriy40]

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

Разница между 11050х и 750х — видимо плата за множество паттернов.

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

[VAL]

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

Плюс не вполне понимаю как соотносятся вероятности $pqrst$ и $pqrs$ с фиксированным $t$.

Поэкспериментировал в этом направлении.
В паттерне для поиска 16 чисел по 96 делителей делал изменения двух типов:

1. Менял $7^2$ на $7^5$. Т.е. вместо разложения $pqrst$ для оставшегося числа подходящим будет $pqrs$.
Вероятность, что разложение будет подходящим увеличивается при этом примерно в 3.5 раза.
Беда в том, что много таких замен не сделаешь: очень быстро будет расти диапазон проверяемых чисел.

2. Менял $u^2$ на $u^2v$ ($u,v$ - фиксированные простые). Т.е. вновь вместо разложения $pqrst$ для оставшегося числа подходящим будет $pqrs$.
Вероятность, что разложение будет подходящим увеличивается при этом примерно в 1.8 раза.
Зато диапазон проверяемых чисел растет не так быстро, как в первом случае.

[Dmitriy40]

VAL
Уточните несколько моментов:
1. Величина чисел до замен?
2. Какие простые использованы? $2\ldots41$, да? Т.е. кроме двойки остальные лишь в квадратах?
3. $v=43$ или другое? Или без разницы?
4. Менялось одно место или несколько?

-- 19.07.2022, 15:13 --

Я же ночью немного переписал ускорители и генератор таблиц для них для поддержки простых более $2^{15}=32768$ (пока только x64 AVX2 версию).
И проверил на паттерне для 172 делителей с 5-ю проверяемыми местами из 7-ми. К сожалению удалось добиться лишь 1.5х ускорения счёта при повышении коэффициента фильтрации с 2690 до 5020, порог простых $2^{17}$ и 400М задействованной памяти. Но проверял лишь в одном потоке, хотя даже 1.6Г памяти (на 4 потока) приводить к тормозам ещё не должно.
Дальнейшему повышению коэффициента фильтрации (а для порога простых $2^{20}$ он повышается до 11300) мешает быстрое увеличение требуемой памяти, из-за чего приходится уменьшать разворачивание внутреннего цикла, что и приводит к замедлению, например для порога простых $2^{20}$ с памятью 800М при коэффициенте фильтрации 11300 вместо 2690 скорость счёта вдвое ниже исходной (34с/4.4с против 17.3с/16.3с, первое время общее, через дробь в PARI). Возможно если ещё чуть доделать ускоритель (чтобы память не выделялась сразу, а запрашивалась у ОС, что позволит работать с гигабайтами памяти), то скорость и вернётся, но памяти понадобится несколько гигабайтов на поток.
И это для 5-ти проверяемых мест, для большего количества памяти надо линейно больше.

[VAL]

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

1. Величина чисел до замен?

Порядка $10^{42}$

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

2. Какие простые использованы? $2\ldots41$, да? Т.е. кроме двойки остальные лишь в квадратах?

$2^{11}, 3^5, 5^5$, остальные до 41 в квадратах.

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

3. $v=43$ или другое? Или без разницы?

$v\in \{43,47,53,59\}$

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

4. Менялось одно место или несколько?

При замене $7^2$ на $7^5$ - одно. При замене $u^2$ на $u^2v$ - разные.

[Dmitriy40]

Непонятно мне почему такая большая разница в вероятностях, ведь числа то растут очень схоже (в 343 раза или 43-59 раз, по сравнению с $10^{42}$ увеличение несущественно). Возможно дело именно в увеличении степени с 2 до 5 ...
Тогда выходит по скорости выгоднее не степени повышать, а дополнительные простые расставлять. В том числе и для 2,3,5. Числа будут больше, зато вероятность найти цепочку выше.

[VAL]

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

Непонятно мне почему такая большая разница в вероятностях, ведь числа то растут очень схоже (в 343 раза или 43-59 раз, по сравнению с $10^{42}$ увеличение несущественно). Возможно дело именно в увеличении степени с 2 до 5 ...

Выходит. Но почему, я пока не понимаю

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

Тогда выходит по скорости выгоднее не степени повышать, а дополнительные простые расставлять.

Аэтот вывод странный! Ровно наоборот. Выгоднее повышать степени. Пока это не приводит к существенному замедлению факторизации.

[Dmitriy40]

А, да, разумеется, это я знаки попутал.

[VAL]

Применил оба описанных выше приема (замену $7^2$ на $7^5$ и добавление фиксированных множителей, чтобы требовалось поменьше разложений $pqrst$ и запустил поиск 16 гексадекатлона по 96 делителей.
Параллельно провел еще серию экспериментов. И построил базовый паттерн, который должен был уменьшить ожидаемое число проверок еще примерно в 5 раз. Но запустить не успел. Гексадекатлон нашелся!
Так что, $T(48,16) \le 41780573338629779703065418979464122604969472482834053115$, а $M(96) \ge 16$
И цепочка для $k=96$ ожидаемо вышла на чистое третье место.

[EUgeneUS]

VAL
Поздравления!

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

а $M(96) \le 16$

а тут, видимо, знак в другую сторону нужен.

[VAL]

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

тут, видимо, знак в другую сторону нужен.

Спасибо!
Поправил.