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

[Yadryara]

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

Latest estimate for my code suggests it may be able to prove $T(6,10)$ minimal in under 90 days (down from nearly 500 days);

И до конца 21-го века останутся сущие пустяки: минимизация $T(6,11)$ — $T(6,15)$

[EUgeneUS]

mathematician123

К случаю $k=12t$, где $t>5$ - простое. И сокращению переборов в этом случае.

Правильно ли я понимаю, что можно считать доказанным, что в этом случае $n_0$ представимо в виде $n_0 = 2^{t-1} \cdot 3 pq^2$, либо в виде $n_0 = 2^{t-1} \cdot 3^2 pq$?
То есть доказано, что
а) $n_0$ обязательно делится на $3$
б) всякие "экзотические" факторизации $n_0$ исключены, и у $n_0$ имеется ровно четыре простых делителя, включая $2$ и $3$?

Тогда продолжим с этого места:

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

и получим $32(w)(w+1)(w^2+w+1) = n_0$

$(w)(w+1)(w^2+w+1) = 2^{t-6} \cdot 3 pq^2$
либо:
$(w)(w+1)(w^2+w+1) = 2^{t-6} \cdot 3^2 pq$

Отметим следующие факты:
а) $w^2+w+1$ - всегда нечётное. То есть на степень двойки может делиться либо $w$, либо $w+1$
б) $w^2+w+1$ - может, но не обязано делиться на $3$, но не может делиться $9$.
в) Уравнение $w^2+w+1 = 3 q^2$ не имеет решений, кроме $q=1$

Сократим на $2^{t-6}$, тогда слева возможны варианты:

$$(a)(w+1)(w^2+w+1)$$

$$(w)(a)(w^2+w+1)$$

где числа в скобках все нечётные и попарно не имеют общих делителей.
$a$ - наименьшее число.

слева возможны варианты:
$ 3 pq^2$ или $3^2 pq$

Тогда возможны (часть будет исключена) варианты:
1. $a=1$
1.1. $w=2^{t-6}$, $w+1=q^2$, $w^2+w+1=3p$
1.2. $w+1=2^{t-6}$, $w=q^2$, $w^2+w+1=3p$
1.3. $w=2^{t-6}$, $w+1=p$, $w^2+w+1=3q^2$, что невозможно
1.4. $w+1=2^{t-6}$, $w=p$, $w^2+w+1=3q^2$, что невозможно

2. $a=3$
2.1. $w=3 \cdot 2^{t-6}$, $w+1=q^2$, $w^2+w+1=p$
2.2. $w+1=3 \cdot 2^{t-6}$, $w=q^2$, $w^2+w+1=p$

3. $a=9$
2.2. $w=3^2 \cdot 2^{t-6}$, $w+1=q$, $w^2+w+1=p$
2.3. $w+1=3^2 \cdot 2^{t-6}$, $w=q$, $w^2+w+1=p$

4. $a=7$
4.1. $w=7 \cdot 2^{t-6}$, $w+1=3^2$, $w^2+w+1=p$, что невозможно
4.2. $w+1=7 \cdot 2^{t-6}$, $w=3^2$, $w^2+w+1=p$, что невозможно

Наверняка, что ещё можно исключить. Но наибольшие проблемы будут с $a=9$. Но уже сейчас осталось 6 проверок для каждого $p$ (а если считать разные $a$ - то три проверки).

[mathematician123]

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

Правильно ли я понимаю

Да

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

в) Уравнение $w^2+w+1 = 3 q^2$ не имеет решений, кроме $q=1$

Откуда это следует? В натуральных у этого уравнения бесконечно много решений. Например, $w = 22$ и $q = 13$.

[Huz]

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

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

Latest estimate for my code suggests it may be able to prove $T(6,10)$ minimal in under 90 days (down from nearly 500 days);

И до конца 21-го века останутся сущие пустяки: минимизация $T(6,11)$ — $T(6,15)$

You may joke, but I do not rule out the possibility of reaching $T(6,15)$ - I think up to $T(6,12)$ is probably within reach for a single computer already. The rest will depend in part on how much further we can reduce the upper bounds, so I appreciate that you are still finding further improvements.

[EUgeneUS]

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

Откуда это следует? В натуральных у этого уравнения бесконечно много решений. Например, $w = 22$ и $q = 13$.

Нашел у себя ошибку
$w^2+w+1$ может делиться на $3$, только если $w = 3m+1$
тогда: $3m^2 + 3m +1 = q^2$
Решаем квадратное уравнение относительно $m$
$D = 9 + 4 \cdot 3 (q^2-1) = d^2$
Тогда $4 \cdot 3 (q^2-1) = d^2 - 9$, это может быть, только если $3 \mid d$.
Обозначим $d = 3l$, тогда $4 (q^2-1) = 3(l^2 - 1)$ (вот тут была ошибка).
Тогда $(2q)^2 - 3 l^2 = 1$. Это уравнение Пелля, у которого есть решение $(1,1)$, а значит есть бесконечная серия решений.

[mathematician123]

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

1.1. $w=2^{t-6}$, $w+1=q^2$, $w^2+w+1=3p$

Из первого уравнения получаем $w \equiv 2 \pmod{3}$. Тогда из второго уравнения получаем $q = 3$.

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

1.2. $w+1=2^{t-6}$, $w=q^2$, $w^2+w+1=3p$

Здесь получаем $q^2+1 = 2^{t-6}$, что невозможно по модулю 4.

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

2.1. $w=3 \cdot 2^{t-6}$, $w+1=q^2$, $w^2+w+1=p$

Здесь $(q+1)(q-1) = 3 \cdot 2^{t-6}$. Одно из чисел $q + 1$ или $q-1$ даёт остаток 2 от деления на 4. Откуда следует $q \pm 1 \le 6$.

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

2.2. $w+1=3 \cdot 2^{t-6}$, $w=q^2$, $w^2+w+1=p$

Здесь $q^2+1 = 3 \cdot 2^{t-6}$, что невозможно по модулю 3.

-- 12.07.2022, 20:39 --

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

1.3. $w=2^{t-6}$, $w+1=p$, $w^2+w+1=3q^2$

Здесь по модулю 3 получаем, что $p = 3$.

-- 12.07.2022, 20:42 --

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

1.4. $w+1=2^{t-6}$, $w=p$, $w^2+w+1=3q^2$

Здесь $w \equiv 3 \pmod{4}$. Откуда следует, что третье уравнение неразрешимо по модулю 4.

[EUgeneUS]

Но исключать можно и другими способами. Например:
1.1. и 1.3. исключаются по модулю $3$ (подстановкой $w=2^{t-6}$ в $w^2+w+1$)
А 1.2. исключается так:
$2^{t-6}-1 = q^2$

Тогда $2 (2^{(t-7)/2})^2 - q^2 =1$. Получили уравнение Пелля $2x^2 - q^2=1$. Но в его решениях $x$ - нечётный, а должен быть степенью двойки. Случай $t=7$ рассматривается отдельно.

UPD. Пока писал, Вы эти (и другие) случаи исключили

-- 12.07.2022, 21:14 --

2.1.

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

Откуда следует $q \pm 1 \le 6$.

$q \in \left\lbrace5,7\right\rbrace$

Тогда
а) $3 \cdot 2^{t-6} = 5^2 - 1= 24$, $t=9$
б) $3 \cdot 2^{t-6} = 7^2 - 1= 48$, $t=10$
В обоих случая $t$ - составное.

[VAL]

$M(252)\ge 8$

(Оффтоп)

391902698087243425314852428890110551415750115828713566685689280666923041108575888504728806796695118952059109375

Найдено через 8 проверок на простоту.
Верхнюю границу пока поставил 23.
Полагаю, наши "пограничники" меня поправят. И не только для $k=252$.

$M(384)\ge 11$.

(Оффтоп)

2506886107744388753893303970491251251321529484710988882583006456982943740

[EUgeneUS]

по случаю $k = 12t$, $a=9$:

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

3. $a=9$
3.1. $w=3^2 \cdot 2^{t-6}$, $w+1=q$, $w^2+w+1=p$
3.2. $w+1=3^2 \cdot 2^{t-6}$, $w=q$, $w^2+w+1=p$

(поправил нумерацию в цитате)

Проверил нечетные $t$ до $t=27$ (до куда разрядности Эксела хватило )
В обоих случаях $q = 3^2 \cdot 2^{t-6} \pm 1$ довольно регулярно попадает в простые числа.
А вот $w^2+w+1=p$ бывает простым существенно реже.
В (3.1) совпадений не было, чтобы оба были простыми. А в (3.2) есть три совпадения:
1. $t=7$, $w=q=17$, $p = 307$. Кстати, этот случай нашел уважаемый Dmitriy40 выше. Но там потребовалось 576 проверок, а сейчас всего две.
2. $t=9$, $w=q=71$, $p=5113$
3. $t=27$, $w=q=18874367$, $p=356241748525057$

Похоже одно (редко - два) решения могут находиться и для каких-то простых $t$. Хорошо бы проверить на системамх с длинной арифметикой...
Конечно, крайне мало вероятно, что 1-2 решения для каких-то отдельных $t$ дадут цепочку длиной более $15$, но исключить это пока не получается.

[VAL]

$T(48,14)\le 312318006809070608880247466427347491827017724$.
И, соответственно, $M(96)\ge 14$.

Кто-нибудь пятнашку по 96 или мне запустить поиск?

[mathematician123]

EUgeneUS
У нас во всех случаях $w \approx 2^t$ и $n_0 \approx 16^t$.

Предположим, что существует цепочка из 16 чисел по $12t$ делителей. Тогда каждое число в этой цепочке в разложении на простые содержит некоторое простое в степени $\ge t-1$. Причём у различных чисел цепочки эти простые будут различные. Поэтому одно из чисел цепочки будет $\ge p_{16} ^{t-1} = 53^{t-1}$

-- 13.07.2022, 10:43 --

Похоже, что $M(108) \le 15$. Случай $n_0 = q_1q_2q_3^2q_4^2q_5^2$ невозможен из-за делимости на 32. Поэтому $n_0$ должно иметь не более четырёх различных простых делителей. А тогда можно применить ту же технику, что и в доказательстве $M(84) \le 15$.

[Yadryara]

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

Не беря во внимание дополнительные фильтры и ухищрения (иногда они дают колоссальный эффект,

Правильно ли я понимаю, что самый колоссальный эффект как раз для 12-15? Ибо имеется не менее 11 одиночных искомых простых в паттернах.

В паттернах для 48-20 не менее 3 искомых одиночных простых? Можно ли посмотреть на эти данные по другому количеству делителей и другим длинам цепочек? Неплохо бы свести их в табличку.

[EUgeneUS]

mathematician123
Прекрасно! Нужно только верхнюю оценку для $n_0$ более аккуратно выписать. Чтобы понять, какие $t$ могут вылезти.
Сейчас неравенство $16 \cdot 16^{t-1} > 53^{t-1}$ имеет решение $t=3$. Но $M(36) \le 5$ уже доказано.

[VAL]

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

Правильно ли я понимаю, что самый колоссальный эффект как раз для 12-15? Ибо имеется не менее 11 одиночных искомых простых в паттернах.

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

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

В паттернах для 48-20 не менее 3 искомых одиночных простых? Можно ли посмотреть на эти данные по другому количеству делителей и другим длинам цепочек? Неплохо бы свести их в табличку.

Не совсем понял, что именно свести в таблицу.

При поиске двадцатки я экспериментировал с разными паттернами. И эмпирически пришел к той системе (с тремя простыми), для которой и была найдена двадцатка. (Возможно, если бы основной поиск велся с помощью других паттернов, двадцатка бы нашлась еще раньше )
Но 3 проверки на простоту оптимально для поиска без ускорителей.
Поэтому создавая паттерны для цепочки длины 21, я сделал варианты и на 3, и на 4.
Дмитрий пришел к выводу, что и с его ускорителями 3 проверки лучше 4-х. Но я не исключаю, что это не "окончательный диагноз".

-- 13 июл 2022, 11:33 --

Повторю вопросы, которые в бурном потоке сообщений остались без ответа.

Пятнашку по 96 делителей кто-нибудь ищет?
Здесь отсутствие ответа, по-видимому, означает, что никто.

И еще раз пытаюсь понять, что у нас не сегодняшний момент с оценками сверху для $k$, сравнимых с 12 по модулю 24. Пытался выудить ее из диалога Дениса и Евгения, но заблудился

Верно ли, что $M(k)\le 15$ для 108, 132, 156? Или там еще не было проверки частных случаев?
Какова текущая оценка для 252? Полагаю, 23 явно завышена. 21?

[EUgeneUS]

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

Пятнашку по 96 делителей кто-нибудь ищет?
Здесь отсутствие ответа, по-видимому, означает, что никто.

Видимо. Я не ищу.

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

И еще раз пытаюсь понять, что у нас не сегодняшний момент с оценками сверху для $k$, сравнимых с 12 по модулю 24. Пытался выудить ее из диалога Дениса и Евгения, но заблудился

После предыдущего сообщения Дениса можно считать доказаным, что $M(12t) \le 15$, где $t$ - простое.
То есть из этих $k$:

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

Верно ли, что $M(k)\le 15$ для 108, 132, 156? Или там еще не было проверки частных случаев?

$M(k)\le 15$ доказано для 132 и 156, но не для 108.

-- 13.07.2022, 12:19 --

UPD, впрочем была выполнена проверка для $t = 11, 13, 17, 19, 23$ ещё до "окончательного решения вопроса" от Дениса.

-- 13.07.2022, 12:24 --

UPD2, Денис сделал выше дополнение по $k=108$. То есть тоже можно считать доказаным $M(108) \le 15$.

-- 13.07.2022, 12:28 --

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

Похоже, что $M(108) \le 15$. Случай $n_0 = q_1q_2q_3^2q_4^2q_5^2$ невозможен из-за делимости на 32. Поэтому $n_0$ должно иметь не более четырёх различных простых делителей. А тогда можно применить ту же технику, что и в доказательстве $M(84) \le 15$.

Если делителей ровно четыре, то двойка может быть либо в пятой, либо в восьмой степени. Пятая степень не подходит. Как выше разбирали должно быть 32, умноженное на четное число. То есть не ниже 6-й степени.