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

[VAL]

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

Ваше доказательство $M(90) \le 5$ можно обобщить. При фиксированных $p, q$ доказательство $M(6pq) \le 5$ сводится к конечному перебору.[..]

Это само собой. Я об этом писал.

Цитата:

В итоге, доказательство $M(6pq) \le 5$ свелось к рассмотрению некоторого количества экспоненциальных диофантовых уравнений. Аналогичная ситуация была и в доказательстве $M(2pq) \le 3$. Там эти уравнения удалось решить с помощью соображений делимости и теории уравнений Пелля. Думаю, что и здесь это получится.

А вот это, как раз, то, о чем я спрашивал.
Причем не только про $k=6pq, p,q>3$, но и про $k=6t+12$.

[Huz]

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

Huz, благодарю. Надеюсь уважаемый Dmitriy40, который вроде бы знает С, это прокомментирует.

Я понимаю как работают программы VAL, как работают программы Dmitriy40, но не Ваши.

I will try to write up a simple example, which may help.

Цитата:

Вы не заметили, что у нас на форуме есть специальный тег [oeis][/oeis]?

I missed that, I'll try to remember it in future.

Цитата:

Уважаемый Huz, а Вы читали вот этот пост?

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

А я тем временем ошибку у Хьюго нашёл. В том самом а-файле:

https://oeis.org/A292580/a292580_2.txt писал(а):

T(3,5) 10093613546512321 Jon E. Schoenfield 2017-09-19

Not sure what to do with that one - I'm sure Düntsch and Eggleton found the correct value, but it's not what they published, and the number published was far enough out that you would really need to redo the calculation to arrive at the correct number. The earliest record I was able to find of someone publishing the correct value was Schoenfield's. However the Düntsch and Eggleton paper is referred to in the A292580 references and comments, so readers have the opportunity to make up their own mind.

For new values I verify them all as they are reported, so if there are errors I can either correct them immediately or warn the author so that they can do so. (But I really wish the sequence had been defined as "first run of at least $k$ consecutive integers ...". By far the slowest part of verification is showing that $\tau(v_0 + k) \ne n$.)

[EUgeneUS]

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

случай $k \equiv 6 \pmod{12}$,

Меня гложут смутные сомнения, это этот случай может развалиться как минимум на три:

$$ k = 6 \prod\limits_{i}^{} p_i; p_i \ge 5$$

$$ k = 2 \cdot 3^m \prod\limits_{i}^{} p_i; p_i \ge 5$$

$$ k = 2 \cdot 3^m$$

которые могут оказаться существенно различными.

[mathematician123]

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

В итоге, доказательство $M(6pq) \le 5$ свелось к рассмотрению некоторого количества экспоненциальных диофантовых уравнений.

Пусть $n_0$ имеет ровно 3 различных простых делителя (2, 3 и 5). Тогда из $2(x-1)(x+1)=n_0$ следует, что $2^a3^b5^c = 2^d3^f5^g+1$. Все решения этого уравнения найдены здесь в разделе example. Поэтому нужно рассматривать только случай $n_0 = r_1r_2^2r_3^{p-1}r_4^{q-1}$.

[Yadryara]

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

The earliest record I was able to find of someone publishing the correct value was Schoenfield's.

Уважаемый Huz ! Вы не прошли по ссылке?

Хорошо, я процитирую ещё фрагмент:

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

Во-первых, в той статье Иво и Роджера 1989 года, на которую я давал ссылку выше, в качестве D(6,5) указано число 10,093,613,546,512,121. Да запятые-то поставили, но вот зачем-то указано в концовке 121 вместо правильного 321.

И что Шёнфилд первым заметил эту опечатку спустя 28 лет? Как бы не так. Основатель OEIS Neil James Alexander Sloane в 2009-м запостил последовательность A141621 автора Matthijs Coster (Aug 23 2008):

https://oeis.org/history?seq=A141621&start=50

[EUgeneUS]

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

случай $k \equiv 6 \pmod{12}$,

Посмотрел, что можно обобщить на этот случай в теореме 5 в этой работе Владимира Лецко и Василия Дзюбенко.

Прошу проверить, насколько соответствуют общему случаю ($k \equiv 6 \pmod{12}$) следующие утверждения:

1. Числа вида $n_6 \equiv 6 \pmod{8}$ в цепочку входить не могут. Поэтому любые цепочки лежат между $n_7$ и $n_5$ (включительно).
2.

Цитата:

(Если) число в позиции $2$ делится на $3$. Тогда оно обязательно делится на $9$, а число в позиции $7$ имеет вид $3x^2$. Но сравнение $3 x^2 +3 \equiv 0 \pmod{9}$ неразрешимо. Поэтому число в позиции $7$ не может входить в искомую цепочку.

3. Если число в позиции $2$ делится на $3$. Тогда оно обязательно делится на $9$, а число в позиции $5$ делится $3$ и имеет вид $3 x^2$. Тогда $n_5 = 3 x^2 \equiv 3 \pmod{4}$, а значит $n_2 \equiv 0 \pmod{4}$, что невозможно, так как $n_2 \equiv 2 \pmod{4}$.

Таким образом, eсли число в позиции $2$ делится на $3$, то в цепочку входит не более трех чисел UPD: не более пяти, конечно.

4.

Цитата:

Теперь допустим, что число в позиции $3$ кратно $9$... Двойка в любой чётной степени – это $1$ по модулю $3$. Поэтому $2^e \cdot x^2 \equiv x^2 \pmod{3}$. Но тогда сравнение $2^e \cdot x^2 +3 \equiv 0 \pmod{9}$ сводится к сравнению $x^2 \equiv 2 \pmod{3}$, не имеющему решений.

Таким образом, число $n_3$ кратно $3$, но не $9$, а число $n_0$ кратно $9$.

5.

Цитата:

Из того, что $2 x^2$ и $3 x^2$ не могут быть сравнимы ни с $1$, ни с $4$ по модулю $5$ простым перебором получаем, что числа в позициях $0$ и $5$ делятся на $5$

Если выше всё верно, то $M(k) \le 5 $ для $k \equiv 6 \pmod{12}$ следует из неразрешимости двух систем Пелль-подобных уравнений. (их чуть позже выпишу. То есть системы-то я выпишу, но сейчас у меня нет доказательства их неразрешимости). UPD: тут тоже исправил $\le 3$ на $\le 5$

[Huz]

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

Уважаемый Huz ! Вы не прошли по ссылке?

Oh I do apologise, I misread what you wrote. I've corrected my records to "Matthijs Coster 2008-08-23", it'll be in the next update.

-- 08.06.2022, 16:02 --

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

3. Если число в позиции $2$ делится на $3$. Тогда оно обязательно делится на $9$, а число в позиции $5$ делится $3$ и имеет вид $3 x^2$. Тогда $n_5 = 3 x^2 \equiv 3 \pmod{4}$, а значит $n_2 \equiv 0 \pmod{4}$, что невозможно, так как $n_2 \equiv 2 \pmod{4}$.

Таким образом, eсли число в позиции $2$ делится на $3$, то в цепочку входит не более трех чисел.

I think you've shown that $n_7$ and $n_5$ cannot be in the chain, so is it not still possible to have a chain of 5 numbers $n_0 .. n_4$?

[EUgeneUS]

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

I think you've shown that $n_7$ and $n_5$ cannot be in the chain, so is it not still possible to have a chain of 5 numbers $n_0 .. n_4$?

of course. I think about one, but write another

We want prove $M(k) \le 5 $ if $k \equiv 6 \pmod{12}$ now.

-- 08.06.2022, 19:20 --

UPD: It's next challenge from Vladimir

-- 08.06.2022, 20:08 --

Если утверждения тут (с 1 по 5) верные, то
а) $n_2 = 2 x^2$
б) $n_3 = 3 y^2$
в) либо $n_0 = 5 z^2$, либо $n_5 = 5 z^2$

где, $x, y, z \in \mathbb{N}$ не делятся на $2, 3, 5$.
Тогда, должна быть разрешима одна из систем диофантовых Пелль-подобный уравнений:

либо:

$$\left\{ \begin{array}{rcl} 5 z^2 +2 = 2 x^2 \\ 5 z^2 +3 = 3 y^2 \\ \end{array} \right.$$

либо:

$$\left\{ \begin{array}{rcl} 5 z^2 = 2 x^2 + 3\\ 5 z^2 = 3 y^2 +2 \\ \end{array} \right.$$

Если обе системы неразрешимы, то
а) никакое число в цепочке не может содержать $5$ в первой степени, в качестве делителя.
б) а значит в цепочку может входить не более одного числа, которое делится на $5$, при этом оно должно делиться на $5^2$.
в) а значит цепочка (если откинуть $n_5$ и оставить $n_0$), будет не длиннее шести чисел (все таки тут не более шести, а не пяти).

(Оффтоп)

случаи в очередной раз плодятся, как тараканы...

[EUgeneUS]

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

где, $x, y, z \in \mathbb{N}$ не делятся на $2, 3, 5$.

Поправка:
а) $x, y, \in \mathbb{N}$ не делятся на $2, 3, 5$
б) $z \in \mathbb{N}$ не делятся на $5$
в) во второй системе $z$ не делится на $2, 3$, а в первой системе, напротив $z$ делится на $2$ и на $3$.

[mathematician123]

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

либо:

$$\left\{ \begin{array}{rcl} 5 z^2 +2 = 2 x^2 \\ 5 z^2 +3 = 3 y^2 \\ \end{array} \right.$$

Отсюда видно, что $z = 6m$. Подставим это в систему и получим $90m^2+1 = x^2$ и $60m^2+1 = y^2$. А эта система имеет конечное количество решений, причём похоже, что их все можно найти: сообщении #448114.

-- 08.06.2022, 21:04 --

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

либо:

$$\left\{ \begin{array}{rcl} 5 z^2 = 2 x^2 + 3\\ 5 z^2 = 3 y^2 +2 \\ \end{array} \right.$$

Это уравнение тоже имеет конечное количество решений:

maxal в сообщении #448114 писал(а):

для заданных $a, b$ - см. Теорему 6 в моей статье http://arxiv.org/abs/1002.1679

[EUgeneUS]

Ага. Получается, что семерок такого вида не более чем конечное количество.
Их бы найти все, чтобы закрыть эту возможность...

Тогда остаются шестёрки. В шестёрках получается, что $n_0 \equiv 0 \pmod{25}$, и уравнение для $n_2+1 = n_3$, откуда известное уравнение: $3y^2 - 2 x^2 =1$

[Huz]

Yadryara, here is a partial worked example run for the 'oul' program in a simple case: ./oul -n 12 3. Specifying "-n" means "no database", so we start with an assumed upper limit of $\infty$, and attempt to find $T(6,3)$.

We initialise the allocated multiple and outstanding $\tau$ values: $q_i = 1, t_i = 12 \forall i: 0 \le i \le 2$.

First job is to find fixed primes $p \le k$, in this case 2 and 3.

Recursion level 0: possible arrangements for powers of 2 over the three elements are precalculated. We initially try the first of those, and set $q_0 = 2^2, t_0 = 4; q_2 = 2, t_2 = 6$.

Recursion level 1: possible arrangements for powers of 3 are similarly precalculated. We cannot use any of $3^2, 3^5, 3^{11}$ in $v_0$, so we next try assigning $3^3$. But that leaves $t_0 = 1$, so we check the case $v_0 = 108$ (which fails), and immediately continue to the case $3^1$, so we now set $q_0 = 2^2 \cdot 3, t_0 = 2$.

Fixed primes are now allocated, so we proceed to the main recurse().

Recursion level 2: we first decide which $v_i$ to allocate to, by calling best_v(). This chooses $v_1$, since $t_1 = 12$ is the highest remaining multiple of the highest odd factor dividing $n$. We now loop over the powers (2, 5, 11) that can satisfy the highest odd factor dividing $t_1$, starting with 2, and then start looping over primes $p$ starting with $p=5$, the first prime after the fixed primes used above. So we set $q_1 = 5, t_1 = 4$ and recurse.

Recursion level 3: best_v() chooses $v_2$ as the next to allocate to, since $t_2 = 6$. We now loop over the powers (2, 5) that can satisfy the highest odd factor dividing $t_2$, starting with 2, and then start looping over primes $p$ starting with $p=5$. We see that $p=5$ has already been used (and since $p > k$, it cannot be used a second time), so advance to $p=7$. So we set $q_2 = 98, t_2 = 2$ and recurse.

Recursion level 4: best_v() returns nothing, since all $t_i$ are now powers of 2, so we will call walk_v() and return.

walk_v() collects the $q_i$ and $t_i$, uses CRT to calculate $m: \forall i: m + i \equiv 0 \pmod{q_i}$, finds $a_q$ as the least common multiple of the $q_i$, calculates $Q_i = \frac{a_q}{q_i}$ and $o_i = \frac{m+i}{q_i}$.

We have no limit at this point, so we start an infinite loop $x \in {0, 1, 2, ...}$ such that $v_i = q_i(x \cdot Q_i + o_i)$. On each iteration of the loop, we first check that $\forall i: \gcd(x \cdot Q_i + o_i, q_i) = 1$, then $\forall i: \tau(x \cdot Q_i + o_i) = t_i$. In this case we get a match with $x=59$, yielding $(870924 = 2^2 \cdot 3 \cdot 72577, 5^2 \cdot 11 \cdot 3167, 2 \cdot 7^2 \cdot 8887)$. So we log 870924 as a candidate and return.

Recursion level 3: we now have a limit, so we calculate what the greatest prime we need to check is: in this case that's $\lfloor \sqrt{\frac{870926}{10}} \rfloor = 275$. Now we try the next prime $p=11$, and call walk_v() again to find 678324, further reducing our limit

And so we continue until all the recursions complete. By now our best candidate is 1274, and we have checked every factorization that could possibly give a smaller solution, so we declare $T(6,3) = 1274$.

I hope this makes the approach clear.

[EUgeneUS]

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

В шестёрках получается, что $n_0 \equiv 0 \pmod{25}$, и уравнение для $n_2+1 = n_3$, откуда известное уравнение: $3y^2 - 2 x^2 =1$

Итого $n_0 \equiv 0 \pmod{900}$, откуда $n_2 \equiv 2 \pmod{900}$ и $n_3 \equiv 3 \pmod{900}$.
Что удивительно, если накладывать только уравнение $n_3 - n_2 = 3y^2 - 2 x^2 =1$, то так бывает и довольно часто.
Опять варианты с максимальной чётной цепочкой?

[mathematician123]

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

Итого $n_0 \equiv 0 \pmod{900}$,

Так как $n_0 = 2x^2-2$, то $16 \mid n_0$ и тогда $n_0 \equiv 0 \pmod{3600}$.

[EUgeneUS]

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

тогда $n_0 \equiv 0 \pmod{3600}$

Это слабо помогает. Подходящих $n_2, n_3$ тоже хватает.