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

[Dmitriy40]

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

I. С простой двойкой ($n_2$) могут быть только или $2\cdot 3^4 \cdot p^6$ или $2\cdot 3^6 \cdot p^4$.

Почему? Мне казалось можно в Ваших вариантах 7-10 поменять $3\leftrightarrow q$ и получить например $q^6 p^4-2^5 3^4 r=1$. Не любые $q$ будут допустимы, но например $q=7, q=17$ подходят.

VAL
У меня тоже с dxdy сегодня проблемы.

[VAL]

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

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

I. С простой двойкой ($n_2$) могут быть только или $2\cdot 3^4 \cdot p^6$ или $2\cdot 3^6 \cdot p^4$.

Почему?

Потому что гипотезы, что $n_0$ или $n_1$ кратны 3, опровергаются.
Я же выше писал, что $n_2$ должно быть вида $162+1296t$. По сути Евгений стартует с того же самого рассуждения.

Цитата:

VAL
У меня тоже с dxdy сегодня проблемы.

Значит, я не одинок во Вселенной

-- 17 май 2022, 23:46 --

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

Возможно какие-то банальности напишу.

Почему банальности?
Вполне содержательно (правда, я подробно не смотрел, только сейчас Ваш пост открылся нормально, с отображением формул).
Беда в том, что масса вариантов отвергается, а какая-то экзотика не хочет ни отвергаться, ни находиться

[Yadryara]

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

Т.е. для интервала 2e35 по новым паттернам (с шагом 5.95e26) указание 454e6 даёт время 20 минут, а указание более правильного значения 2e35/5.95e26=336.2e6 даёт время в 30 минут?

Говорю же, я указал 336133915 и тогда 30 минут.

Да, сейчас указал 337000000 и наконец-то убыстрение: всего лишь 17 минут на группу. Что за хрень?!

Оставлю пока так.

И у меня были проблемы. Небось дидосили наш форум. Обратите внимание, около 4-х часов на форуме не было ни одного поста.

-- 17.05.2022, 23:54 --

А сейчас всего 16 минут на группу. Ура.

[Dmitriy40]

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

Потому что гипотезы, что $n_0$ или $n_1$ кратны 3, опровергаются.
Я же выше писал, что $n_2$ должно быть вида $162+1296t$. По сути Евгений стартует с того же самого рассуждения.

Да видел я Ваше $n_2=3^4k$, только не успел спросить почему.
Я согласен что $n_0$ не может содержать тройку (тогда и $n_3$ её должно содержать и уже в первой степени, что вообще говоря кажется не запрещено, но два квадрата в одной цепочке это очень плохо). Но кто мешает сдвинуть паттерн вправо на 1 чтобы степень двойки стала в $n_1$, а двойка в $n_3$?
Вот почему недопустим к примеру такой паттерн: $5^6\cdot19^4\cdot w, 2^6\cdot3^4\cdot q, 17^6\cdot23^4\cdot r, 2\cdot7^6\cdot p^4$ ?

-- 18.05.2022, 00:07 --

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

Да, сейчас указал 337000000 и наконец-то убыстрение: всего лишь 17 минут на группу. Что за хрень?!

Похоже где-то неправильное округление стоит. Но искать лень, достаточно завысить на доли процентов работу и всё.

[VAL]

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

Но кто мешает сдвинуть паттерн вправо на 1 чтобы степень двойки стала в $n_1$, а двойка в $n_3$?
Вот почему недопустим к примеру такой паттерн: $5^6\cdot19^4\cdot w, 2^6\cdot3^4\cdot q, 17^6\cdot23^4\cdot r, 2\cdot7^6\cdot p^4$ ?

Давайте по новой не начинать путаницу в обозначениях. Мы это уже проходили
Единица в $n_1$ - это не порядковый номер, а остаток от деления на 8. Соответственно $n_1$ нечетно, а Ваш паттерн - $n_7, n_0, n_1, n_2$.
Почему он невозможен напишу чуть позже.
Если цепочка длины 4 и существует (в чем я сомневаюсь), то она выглядит так: $n_0, n_1, n_2, n_3$.

[VAL]

Напомню, что через $n_i$ мы обозначаем число из нашей цепочки, сравнимое c $i$ по модулю 8.

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

Вот почему недопустим к примеру такой паттерн: $5^6\cdot19^4\cdot w, 2^6\cdot3^4\cdot q, 17^6\cdot23^4\cdot r, 2\cdot7^6\cdot p^4$

У Вас $n_2$ - удвоенная четная степень. То есть, $n_2=2x^2$. Тогда $n_0=2x^2-2= 2^6\cdot3^4\cdot q$. Тогда $(x-1)(x+1)=2^5\cdot 3^4 \cdot q$. Отсюда $q \le 2^3 \cdot 3^4+1$. То, что это не годится проверяется коротким перебором.

PS: Ровно те же соображения, что и при доказательстве $M(90) \le 5$.

[Dmitriy40]

VAL
По обозначениям согласен, упустил что у Вас $i$ в $n_i$ это не индекс в цепочке, а остаток по модулю 8.

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

У Вас $n_2$ - удвоенная четная степень. То есть, $n_2=2x^2$. Тогда $n_0=2x^2-2= 2^6\cdot3^4\cdot q$. Тогда $(x-1)(x+1)=2^5\cdot 3^4 \cdot q$. Отсюда $q \le 2^3 \cdot 3^4+1$. То, что это не годится проверяется коротким перебором.

PS: Ровно те же соображения, что и при доказательстве $M(90) \le 5$.

Да, я ещё тогда это не понял. И сейчас не понимаю. В $n_2$ всегда удвоенная чётная степень, хоть с тройкой, хоть без, и что?
Вот возьмём допустимые по вашему тройку с двойкой и запишем ровно по вашему ходу мысли: "$n_2=2\cdot3^4\cdot p^6=2x^2$, тогда $n_0=2x^2-2=2^6\cdot5^4\cdot q$, тогда $(x-1)(x+1)=2^5\cdot5^4\cdot q$, отсюда $q \le 2^3 \cdot 5^4+1$, коротким перебором тоже ничего не годится" — получили ровно тот же результат. И так можно проделать с любым простым вместо $5$, даже в общем виде с $a$ вместо него. И в чём тогда разница-то? Где тут используется тройка то? Что в одном случае она недопустима, а в другом допустима? До меня не доходит.

-- 18.05.2022, 04:00 --

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

Тогда $(x-1)(x+1)=2^5\cdot 3^4 \cdot q$. Отсюда $q \le 2^3 \cdot 3^4+1$.

Даже более того, непонятно с какой стати выполняется это "отсюда", если вольфрамальфа даёт бесконечные серии решений. Видимо я не понимаю чего-то совсем очевидного.

[VAL]

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

VAL в сообщении #1554873
писал(а):
Тогда $(x-1)(x+1)=2^5\cdot 3^4 \cdot q$. Отсюда $q \le 2^3 \cdot 3^4+1$. Даже более того, непонятно с какой стати выполняется это "отсюда", если вольфрамальфа даёт бесконечные серии решений.
Видимо я не понимаю чего-то совсем очевидного.

Именно!
Сколько среди Ваших (с Вольфрамом) решений с простым $q$?
Ровно одно - 647. Которое не превосходит $2^3 \cdot 3^4+1=649$.
НОД чисел $x-1$ и $x+1$ равен 2. Поэтому сомножители в $\frac{x-1}2\cdot \frac{x+1}2=2^3\cdot 3^4 \cdot q$ взаимно просты. Являясь ПРОСТЫМ, $q$ входит ровно в один из сомножителей. Даже если все остальные входят в другой, $q$ все равно не больше их произведения, увеличенного на 1. Ведь числа $\frac{x-1}2$ и $\frac{x+1}2$ соседние.

-- 18 май 2022, 08:27 --

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

В $n_2$ всегда удвоенная чётная степень, хоть с тройкой, хоть без, и что?
Вот возьмём допустимые по вашему тройку с двойкой и запишем ровно по вашему ходу мысли: "$n_2=2\cdot3^4\cdot p^6=2x^2$, тогда $n_0=2x^2-2=2^6\cdot5^4\cdot q$, тогда $(x-1)(x+1)=2^5\cdot5^4\cdot q$, отсюда $q \le 2^3 \cdot 5^4+1$, коротким перебором тоже ничего не годится" — получили ровно тот же результат. И так можно проделать с любым простым вместо $5$, даже в общем виде с $a$ вместо него. И в чём тогда разница-то?

В том, что $2^3 \cdot a^4+1$ не ограничено сверху.

[Dmitriy40]

VAL
Спасибо, теперь дошло. И сам про что-то подобное думал, но никак не доводил размышления до конца.

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

В том, что $2^3 \cdot a^4+1$ не ограничено сверху.

Зато ограничено для любого конечного $a$, т.е. для малых простых глубина перебора всегда сильно ограничена и можно брать и проверять буквально всё. Получается будет или $p<\sqrt[4]{q}$ или $p<\sqrt[6]{q}$ с точностью до коэффициентов, т.е. и перебрать то надо совсем не триллионы. Ну если брать $q$ лишь в первой степени, в высоких проверить ещё проще.

Кстати, а раз есть и $n_1,n_3$, то ведь минимальное значение $p$ будет ими ограничено, т.е. можно попытаться вывести противоречие, по крайней мере для малых $a$ ...

Запустил перебор по $a$, до $a<1000$ решений нет никаких, а до $a<7000$ нет решений кроме возможно варианта $a^6,p^4$ (он проверяется долго, зато до проверки простоты $q$ в нём даже не доходит, оно всегда не целое). Конечно если нигде не ошибся.

-- 18.05.2022, 11:30 --

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

зато до проверки простоты $q$ в нём даже не доходит, оно всегда не целое

А, нет, не всегда, в уравнении $2^3 a^6 q + 1 = 3^6 p^4$ нашлись варианты: $a=7, p=295357, q=5894383301540868709$, $a=7, p=765953, q=266598552608850245419$, $a=7, p=1116431, q=1203308125907226961699$. Но все $q$ не простые.
UPD. А, все эти $q$ намного больше предела $2^3 a^6 + 1$, где-то я промахнулся с ограничениями.

[VAL]

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

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

В том, что $2^3 \cdot a^4+1$ не ограничено сверху.

Зато ограничено для любого конечного $a$, т.е. для малых простых глубина перебора всегда сильно ограничена и можно брать и проверять буквально всё. Получается будет или $p<\sqrt[4]{q}$ или $p<\sqrt[6]{q}$ с точностью до коэффициентов, т.е. и перебрать то надо совсем не триллионы.

Эти соображения позволяют проверить утверждение $M(6pq)\le 5$ для конкретных $p$ и $q$.

Но я не вижу, как они могут помочь, например, для проверки утверждения $M(70) \le 3$.

Еще раз обращаю внимание на пример с $n_2=162+1296t$.
Среди таких чисел бесконечно много имеющих по 70 делителей.
Например, $911250=2\cdot 3^6 \cdot 5^4$. При этом $n_0=911248=2^4\cdot 13^2 \cdot 337$.
Не вижу причин ("не вижу" и "не существует" не синонимы), по которым для некого $t$ не может оказаться $n_2=2\cdot 3^6 \cdot p^4$, а $n_0=2^4\cdot q^6 \cdot r$.
И где тут ограничение сверху и конечный перебор?

Насколько я понимаю, примерно то же сформулировано у Евгения в его посте про 70 делителей.

[EUgeneUS]

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

, нет, не всегда, в уравнении $2^3 a^6 q + 1 = 3^6 p^4$ нашлись варианты:

Вроде бы, я доказал невозможность этого паттерна. И его "сестринского": $2^3 a^6 q + 1 = 3^4 p^6$
Вечером напишу док-во.

-- 18.05.2022, 14:43 --

что-то не могу сообразить.
Верно ли утверждение: $GCD(n, 2n\pm1)=1$ для любых нечетых $n$?

[lel0lel]

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

что-то не могу сообразить.
Верно ли утверждение: $GCD(n, 2n\pm1)=1$ для любых нечетых $n$?

Алгоритм Евклида в помощь.

[Dmitriy40]

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

Еще раз обращаю внимание на пример с $n_2=162+1296t$.
Среди таких чисел бесконечно много имеющих по 70 делителей.
Например, $911250=2\cdot 3^6 \cdot 5^4$. При этом $n_0=911248=2^4\cdot 13^2 \cdot 337$.
Не вижу причин ("не вижу" и "не существует" не синонимы), по которым для некого $t$ не может оказаться $n_2=2\cdot 3^6 \cdot p^4$, а $n_0=2^4\cdot q^6 \cdot r$.
И где тут ограничение сверху и конечный перебор?

Для какого-нибудь $t$ ничто не мешает оказаться, вот только после выбора $a$ максимальная величина $t$ будет ограничена так как ограничено $q$ в $2^4\cdot a^6 \cdot q$: $n_2=162+1296t=2\cdot3^4\cdot(1+8t)=2\cdot3^4\cdot p^2=2x^2$, тогда $n_0=n_2-2=2x^2-2=2(x-1)(x+1)=2^4\cdot 13^2 \cdot 337$, тогда $(x-1)(x+1)=2^3 \cdot a^2 \cdot q, a=13, q=337$, при этом $q=337<2^3 \cdot 13^2+1$, как и должно быть. Т.е. ограничение на $q$ и соответственно $x,p$ выполняется.
Потому выбрав некое $a$ мы тут же получаем ограничение на $q<2^3 a^4+1$ или $q<2^3 a^6+1$ или $q<2^5 q^4+1$ или $q<2^5 q^6+1$ (некоторые из которых EUgeneUS возможно уже запретил, надо свериться с его списком).
Это же ровно что Вы мне и объяснили, про ограничение на $q$ если взять $a=3$. С чего ограничение вдруг пропадает если взять другое простое $a$ мне невдомёк, ведь нигде в рассуждении $3$ кроме как в $a=3$ не фигурирует и ничто не мешает взять любое другое простое $a$.

Я уже проверил $a<16000$ для вариантов кроме $a^6,p^4$ (он проверен до $p<48\cdot10^6$ для всех $a$), ни решений, ни даже целых $q$ нет вообще.

[EUgeneUS]

lel0lel в сообщении #1554892 писал(а):

Алгоритм Евклида в помощь.

Да, конечно, спасибо.

-- 18.05.2022, 17:54 --

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

(некоторые из которых EUgeneUS возможно уже запретил, надо свериться с его списком).

Из всего многообразия остался только один "живой паттерн", и то там на числа у двойки в высокой степени появились сильные ограничения. Сейчас напишу.

-- 18.05.2022, 18:07 --

Обозначения:
$a, b$ - различные простые числа больше двух. Одно из них равно трём.
$p, q$ - различные простые числа больше трех. Также попарно различны с $a, b$
$t$ - целая степень (может быть $1$) любого простого числа больше трех.

I. Запрет "экзотических паттернов" вида $a^4 b^ 6 - 1 = 2^\alpha t$

1. $(a^2 b^ 3 - 1)( a^2 b^ 3 - 1)= 2^\alpha t$
2. В скобках одно число кратно двойке, а второе - $2^{\alpha -1}$, запишем это:
$(2^{\alpha -1} n)(2^{\alpha -1}n \pm 2) = 2^\alpha t$, $n$ - целое нечетное.
3. Сократим двойки:
$(n)(2^{\alpha -2}n \pm 1) = t$

у чисел в скобках НОД равен единице, а значит с необходимостью $n=1$

4. Тогда $(a^2 b^ 3 \pm 1) = 2^{\alpha -1}$. Эти два варианта (на каждую степень двойки, которая появляется в таких паттернах) проверяются и паттерны исключаются.

Тут исключили паттерны: с (1) по (6), нумерация по этому посту.

-- 18.05.2022, 18:26 --

II. Запрет паттернов вида $a^4 b^6 - 1 = 2^3 q^6 p$ (1)

1. Проворачиваем тот же фокус с сокращением степени двойки:

$(n) (2n \pm 1) = q^6 p$

2. У чисел в скобках опять НОД равен $1$, тогда:

а) либо $n = q^6$, $p = 2n \pm 1$, тогда $p = 2 q^6 \pm 1$
б) либо $n = p$, $q^6 = 2n \pm 1$, тогда $p = (q^6 \pm 1)/2$

3. Подставим выражения для $p$ в (1), получим четыре варианта:

1,2: $a^4 b^6 = 2^3 q^6 (2 q^6 \pm 1) +1$
3,4: $a^4 b^6 = 2^2 q^6 (q^6 \pm 1) +1$

4. Все четыре варианта запрещаются сравнением по модулю 27.
Это желательно проверить. Я просто делал таблицу в екселе и смотрел, какие остатки бывают.

-- 18.05.2022, 18:38 --

это запретило паттерны (9) и (10), паттерн (8) был запрещен ранее.

Итого, остался паттерн (7): $3^4 b^6 - 1 = 2^5 q^4 p$

III. Рассмотрим его подробнее...

[EUgeneUS]

1. Проворачиваем тот же фокус с сокращением степени двойки:
$n (8n \pm 1) = q^4 p$

2. Опять имеем четыре варианта. Выпишем их более подробно:

а) $3^4 b^6 = 2^5 q^4 (8q^4 +1) +1$, при этом $p = 8 q^4 + 1$
б) $3^4 b^6 = 2^5 q^4 (8q^4 -1) +1$, при этом $p = 8 q^4 - 1$
в) $3^4 b^6 = 2^2 q^4 (q^4 +1) +1$, при этом $p = (q^4 + 1)/8$
г) $3^4 b^6 = 2^2 q^4 (q^4 -1) +1$, при этом $p = (q^4 - 1)/8$

3. Теперь по модулю 27 запрещаются не все варианты, а только два: "а" и "г", другие два остаются "живыми".
Это тоже хорошо бы проверить.

4. Выпишем "живые" варианты, чтобы можно было на них ссылаться:
б) $3^4 b^6 = 2^5 q^4 (8q^4 -1) +1$, при этом $p = 8 q^4 - 1$
в) $3^4 b^6 = 2^2 q^4 (q^4 +1) +1$, при этом $p = (q^4 + 1)/8$

5. Путём пристального вглядывания в таблицы в екселе, установлено:

а) Решения сравнения по модулю $27$ в целых числах доставляются при $q = 18 n \pm 5$. Где $n$ - целое (не обязательно нечетное).
б) При этом решения иногда запрещаются для одного или другого "живого варианта" по модулю 243. Но никогда одновременно для обоих "живых вариантов".
в) Решения вида $q = 54 n \pm 5$ подходят для обоих "живых вариантов" всегда.

-- 18.05.2022, 19:18 --

IV. Что дальше (на что меня не хватило)

1. Возможно удастся доказать, что $p$ и $q$ не могут быть простыми одновременно. Тогда последний паттерн запретится, и 4-к не существует.
2. Возможно имеет смысл подставить вместо $q$ его выражение через $n$. Тогда $3^4$ сократится, и получится:
$b^6 = (\text{какое-то сложное выражение от n})$
возможно это даст дополнительные ограничения на $q$ и повысит эффективность поиска.
3. Возможно, имеет смысл поискать с имеющимися ограничениями на $q$ и $p$, если найдутся решения, где они простые одновременно, то и решение, где $b$ - простое можети не запретиться...