2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 55, 56, 57, 58, 59, 60, 61 ... 215  След.
 
 Re: Пентадекатлон мечты
Сообщение17.05.2022, 23:23 
Заслуженный участник


20/08/14
11763
Россия, Москва
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 сегодня проблемы.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение17.05.2022, 23:36 
Заслуженный участник


27/06/08
4062
Волгоград
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 писал(а):
Возможно какие-то банальности напишу.
Почему банальности?
Вполне содержательно (правда, я подробно не смотрел, только сейчас Ваш пост открылся нормально, с отображением формул).
Беда в том, что масса вариантов отвергается, а какая-то экзотика не хочет ни отвергаться, ни находиться :-(

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение17.05.2022, 23:47 
Аватара пользователя


29/04/13
8108
Богородский
Dmitriy40 в сообщении #1554862 писал(а):
Т.е. для интервала 2e35 по новым паттернам (с шагом 5.95e26) указание 454e6 даёт время 20 минут, а указание более правильного значения 2e35/5.95e26=336.2e6 даёт время в 30 минут?

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

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

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

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

-- 17.05.2022, 23:54 --

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

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.05.2022, 00:01 
Заслуженный участник


20/08/14
11763
Россия, Москва
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 минут на группу. Что за хрень?!
Похоже где-то неправильное округление стоит. Но искать лень, достаточно завысить на доли процентов работу и всё.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.05.2022, 01:29 
Заслуженный участник


27/06/08
4062
Волгоград
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$.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.05.2022, 02:39 
Заслуженный участник


27/06/08
4062
Волгоград
Напомню, что через $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$.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.05.2022, 03:11 
Заслуженный участник


20/08/14
11763
Россия, Москва
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$.
Даже более того, непонятно с какой стати выполняется это "отсюда", если вольфрамальфа даёт бесконечные серии решений. Видимо я не понимаю чего-то совсем очевидного.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.05.2022, 08:17 
Заслуженный участник


27/06/08
4062
Волгоград
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$ не ограничено сверху.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.05.2022, 11:13 
Заслуженный участник


20/08/14
11763
Россия, Москва
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$, где-то я промахнулся с ограничениями.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.05.2022, 13:35 
Заслуженный участник


27/06/08
4062
Волгоград
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 делителей.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.05.2022, 14:13 
Аватара пользователя


11/12/16
13849
уездный город Н
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 --

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

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.05.2022, 16:27 
Заслуженный участник


20/04/10
1876
EUgeneUS в сообщении #1554887 писал(а):
что-то не могу сообразить. :roll:
Верно ли утверждение: $GCD(n, 2n\pm1)=1$ для любых нечетых $n$?

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

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.05.2022, 17:49 
Заслуженный участник


20/08/14
11763
Россия, Москва
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$ нет вообще.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.05.2022, 17:52 
Аватара пользователя


11/12/16
13849
уездный город Н
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. Рассмотрим его подробнее...

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.05.2022, 19:07 
Аватара пользователя


11/12/16
13849
уездный город Н
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. Путём пристального вглядывания :mrgreen: в таблицы в екселе, установлено:

а) Решения сравнения по модулю $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$ - простое можети не запретиться...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3218 ]  На страницу Пред.  1 ... 55, 56, 57, 58, 59, 60, 61 ... 215  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group