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

[VAL]

Huz
mathematician123
Thanks!
I haven't yet understood with restrictions caused by Set 2. I'll think about it.

[Yadryara]

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

Нетрудно доказать, что числа $32p \pm 2$ должны иметь вид $2qr^2$ ($32p$ - среднее число в цепочке).

Спасибо и на этом. Если будет время, покажите, пожалуйста, набросок.

Ну и числа $32p \pm 4$ в составе 15-шки должны иметь вид $4qr$.

Но в наших паттернах не только эти 4, но и все 14 чисел кроме центрального заточены под $q^2rs$.

[mathematician123]

Доработал свою программу. Теперь она тоже умеет доказывать $M(120) \le 107$. Так что этот результат можно считать доказанным.

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

def gcd(a, b):
    if a == 0 or b == 0:
        return a+b
    return gcd(b, a%b)

m = 2**5 * 3**2
bound = 0
Mbound = 0

for x in range(m + 17):
    if (x%32 == 24) or (x%32 == 16) or (x%36 == 30) or (x%48 == 30) or (x%72 == 42) or (x%72 == 66):
        if bound > Mbound:
            Mbound = bound
        bound = 0
    else:
        bound += 1

print("M(84) <= ", Mbound)
            
m = 2**9 * 3**4 * 5**4
bound = 0
Mbound = 0

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

    # set 1 in Hugo notation
    d = [2**6, 2**8, 2**2 * 3**2, 2**2 * 5**2, 3**2 * 5**2, 2**3 * 3**3, 2**3 * 5**3, 3**3 * 5**3, 2**5 * 3**2, 2**5 * 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**3, 3 * 5**3, 3**3 * 5, 2 * 5**3, 5 * 2**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
    return False

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

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

Если кто-нибудь захочет запустить программу: она считает около 2 минут на моём компьютере.

-- 07.07.2022, 16:01 --

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

Спасибо и на этом. Если будет время, покажите, пожалуйста, набросок.

Случай $32p \pm 2 = 2^{11}$ невозможен. Случай $32p \pm 2 = q^2r^3$ невозможен, так как $q^2r^3$ не может содержать двойку в первой степени. В случае $32p \pm 2 = 2q^5$ получается уравнение $16p = q^5 \pm 1$, которое можно решить за счёт того, что правая часть раскладывается на множители.

[EUgeneUS]

К вопросу о точных значениях $M(k)$

1. $k \equiv \pm 2 \pmod{12}$. В этом случае $M(k) \le 3$. (Да, я помню, что общий случай доказан только в случае если, ABC-гипотеза верна). Можно построить паттерн для цепочки из трех чисел, каждое из которых будет иметь вид $n_i = k_i p_i$, где $n_i$ - число в цепочке, $k_i$ - некий наперёд заданный коэффициент, определяемый а) факторизацией $k$ и б) наперед заданными малыми простыми числами, $p_i$ - некое неизвестное простое число. Тогда для всех трех $p_i$ можно составить систему арифметических последовательностей, и наличие цепочки будет "гарантироваться" гипотезой Диксона.

2. $k \equiv \pm 6 \pmod{12}$. В этом случае $M(k) \le 5$. Тогда в цепочку обязательно входит число $n_2 \equiv 2 \pmod{8}$. И вот его уже нельзя будет представить виде $n_2 = k_2 p_2$. Неизвестное простое там будет (как минимум) в квадрате. То есть форма такая: $n_2 = 2 k_2 (p_2)^2$. Вопрос: что (какая теорема или не опровергнутая гипотеза) обеспечивает, что найдется цепочка длиной $5$ для $k \equiv \pm 6 \pmod{12}$?

[Huz]

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

I haven't yet understood with restrictions caused by Set 2. I'll think about it.

Taking $n \equiv 120 = 2^3 \cdot 3 \cdot 5 \pmod{144 = 2^4 \cdot 3^2}$ as an example: this fixes $n = 2^3 \cdot 3 \cdot x^2$ with $x^2 \equiv 5 \pmod{6}$, but 5 is not a quadratic residue mod 6. All of the items in this set are of that style.

[VAL]

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

Вопрос: что (какая теорема или не опровергнутая гипотеза) обеспечивает, что найдется цепочка длиной $5$ для $k \equiv \pm 6 \pmod{12}$?

Гипотеза Шинцеля.
Или более сильное утверждение. Например, гипотеза Бейтмана-Хорна.

Писал от этом в этой ветке, в нашей с Василием статье, а также здесь.
Так что, не только я никак не дочитаю Ваше доказательство...

-- 07 июл 2022, 19:14 --

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

Taking $n \equiv 120 = 2^3 \cdot 3 \cdot 5 \pmod{144 = 2^4 \cdot 3^2}$ as an example: this fixes $n = 2^3 \cdot 3 \cdot x^2$ with $x^2 \equiv 5 \pmod{6}$, but 5 is not a quadratic residue mod 6. All of the items in this set are of that style.

Thanks!
Have You similar upper bounds for other $k$?

[Huz]

I'd be grateful if someone can check this algorithm for errors: this lets me speed up minimization runs, particularly for $M(12n+6)$, but I'm not entirely confident that the logic is correct.

(Оффтоп)

Let $\nu_p(n)$ be the index of the highest power of p dividing n (also called "valuation").
Define boolean $c_k(n, p) := \exists x: x^2 \equiv n \pmod{p}$, ie n is a quadratic residue mod p.

I want a function $c_f(p, x)$ that returns true if $\nu_p(n) = x > 0$ is possible, given $n+dp^k = my^2$, $p \not | dm$ is known. This is the logic I'm using:

$c_f(p, x)$ is true if $d = 0$
else $c_f(p, x)$ is false if $x > k$ and $k$ is odd
else $c_f(p, x)$ is false if $x < k$ and $x$ is odd
else $c_f(p, x)$ is $c_k(d / m, p)$ if $x \ne k$
else $c_f(p, x)$ is true (not sure of the answer when $x = k$, but true is the safe option)

-- 07.07.2022, 16:51 --

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

Have You similar upper bounds for other $k$?

Not yet - I think I looked at $M(120)$ only to prove that $a(120) = 0$ in A72507. I can look for others when I have some spare processing power, if you tell me which ones you are interested in.

[VAL]

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

I can look for others when I have some spare processing power, if you tell me which ones you are interested in.

The numbers divisible by 12 represented in the Table at this page and also 192, 288.

[Huz]

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

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

I can look for others when I have some spare processing power, if you tell me which ones you are interested in.

The numbers divisible by 12 represented in the Table at this page and also 192, 288.

Checking moduli up to 10,000:
$M(108) \le 21$
$M(120) \le 107$
$M(132) \le 21$
$M(144) \le 31$
$M(168) \le 31$
$M(180) \le 29$
$M(192) \le 31$
$M(216) \le 31$
$M(240) \le 123$
$M(288) \le 31$
$M(384) \le 31$
$M(768) \le 31$

[VAL]

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

Checking moduli up to 10,000:

[..]
Thank You!

[mathematician123]

VAL
Можете сказать, как доказать $M(180) \le 23$? У меня получилось доказать только $M(180) \le 29$.

[VAL]

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

Можете сказать, как доказать $M(180) \le 23$? У меня получилось доказать только $M(180) \le 29$.

Техника получения этого результата очень проста: копировал из другой строки и забыл поменять

Но я уже исправился.

Кстати, я что-то засомневался в оценке для 60.
В свое время я тщетно пытался ее уменьшить. Но почему-то в оценке $M(60)\le 23$ при этом не сомневался. А сейчас не очень понимаю почему.

[mathematician123]

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

Кстати, я что-то засомневался в оценке для 60.

Оценка $M(k) \le 23$ легко доказывается для случая, когда $k \equiv 4 \pmod{8}$ и $k$ не делится на 5. Как доказывать эту оценку для $k = 60$, непонятно. В а-файле тоже приведена оценка $M(60) \le 23$, но никаких ссылок на доказательство там нет.

Вообще, было бы неплохо сделать что-то подобное а-файлу, но для теоретических оценок сверху. Чтобы в одном месте были ссылки на все оценки. Есть ли возможность это как-то организовать?

[Huz]

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

В а-файле тоже приведена оценка $M(60) \le 23$, но никаких ссылок на доказательство там нет.

Hmm, I'm not sure either, I'll look into it.

[Yadryara]

mathematician123, благодарю.

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

Случай $32p \pm 2 = q^2r^3$ невозможен, так как $q^2r^3$ не может содержать двойку в первой степени.

И случай $32p \pm 6 = q^2r^3$ невозможен по той же причине.

А все случаи $32p \pm 2,6 = 2q^5$ исключены перебором всех $1969800$ простых $q$.

Итого, если числа вида $q^3r^2$ и $q^5r$ присутствуют в искомой 15-шке, то только на местах $32p \pm 1,3,5,7$

Другими словами, если подходящие $q$ и $r$ существуют, то они все нечётны.