fish224 Oct 3 2023 at 20:03

Расширенная гипотеза Коллатца, или проблема «nx+1» — часть I

3 min

2.9K

Comments 15

longclaps Oct 3 2023 at 21:44

все_величайшие_математики = set()
assert all(математик.сходится_во_мнении("мы все равно придём к единице") 
           for математик in все_величайшие_математики)

Произвольное утверждение относительно всех элементов множества всегда верно для пустого множества. Те из нас, кто не входит во множество "все величайшие математики", могут принять на веру вместо доказательства вышеприведённый код на питоне.

Но мне всё-таки хочется верить, что это множество - непустое. Прошу, огласите весь список!

fish224 Oct 4 2023 at 08:47

Извиняюсь, я действительно неправильно выразился.

Tzimie Oct 3 2023 at 22:46

Возможно вас заинтересует моя статья

https://habr.com/ru/articles/717094/

fish224 Oct 4 2023 at 08:48

Спасибо за интересный материал, она меня заинтересовала.

qid00000000 Oct 4 2023 at 08:29

Эта гипотеза по праву считается самой простой нерешенной проблемой.

Это не так. Формулировка гипотезы - действительно простая, а вот сама гипотеза не является простой (вероятно, она одна из неразрешимых гипотез).

Сама формулировка взята из перевода Veritasium - Vert Dider (научпоп ролик про гиптоезу Коллатца.

В общем, в настоящее время все величайшие математики сходятся во мнении, что вне зависимости от того, какое число мы бы взяли, мы все равно придём к единице.

Очень спорное утверждение. Как приукраса сойдет, но не для статьи на математическую тематику. Да и в любом случае, нужно ссылки на подобные утверждения, чтобы не выглядело как что-то придуманное.

Данная задача показалась мне скучной

Сильное утверждение...

Итак, я поставил себе задачу — найти все такие нечётные множители, для которых существуют подобные циклы.
Для начала, давайте попробуем найти все циклы из 2 чисел для любых значений этого множителя.

Если я правильно понял, речь о множителе n, а не о количестве цифр в циклах. Да и в последней формулировке нужно явно указать, что мы опускаем четные цифры и считаем только нечетные, иначе, утверждение не будет верно уже для n=5, тк там цифр 7:
"3 -> 16 -> 8 -> 4 -> 2 -> 1 -> 6 -> 3"

Для 181 и того больше: "611 -> 110592 -> 55296 -> 27648 -> 13824 -> 6912 -> 3456 -> 1728 -> 864 -> 432 -> 216 -> 108 -> 54 -> 27 -> 4888 -> 2444 -> 1222 -> 611"

Нам удалось выразить х через гораздо меньшие n, a и c, поэтому теперь задача стала значительно легче.

Вот с этого момента, у вас пошло что-то не то. Мало того, что вы пишете что-то замудренное без доказательств, так и код не выдает верный результат.

Программа нашла всего лишь 3 цикла: это {1, 3} (n = 5), {27, 611} (n = 181) и {35, 99} (n = 181). Пока

Накидал простой скрипт для поиска чисел (не настроен углубляться в нечитаемый код):

END_N = 181
MAX_A = 1000
MAX_B = MAX_A


def find_x(n, a, b):
    return (2**a + n) / (2**(a + b) - n **2)


for n in range(3, END_N + 2, 2):
    for a in range(1, MAX_A):
        for b in range(1, MAX_B):
            x = find_x(n, a, b)
            if x % 1 == 0 and x > 0 and x != 1:
                print(n, a, b, x)

В целом, вывод такой же:

$ python col.py
5 4 1 3.0
181 3 12 27.0
181 6 9 35.0
181 9 6 99.0
181 12 3 611.0

Отмечу, что тут обошли стороной циклы, которые состоят из 1 простого числа:

Если x != 1 заменить на x == 1, то вывод такой:

3 2 2 1.0
5 1 4 1.0
7 3 3 1.0
15 4 4 1.0
31 5 5 1.0
63 6 6 1.0
127 7 7 1.0
255 8 8 1.0
511 9 9 1.0

C вероятностью, близкой к 100%, мы можем предполагать, что это все существующие циклы из 2 чисел.

Не понятно, откуда взялась такая вероятность, тем более, без доказательств..

В целом, если устранить некоторые моменты, которые описаны выше, а также добавить доказательств к утверждениям - статью можно будет считать жизнеспособной.

fish224 Oct 4 2023 at 08:39

Благодарю за критику, вы действительно везде или почти везде правы, но почему мой код не выдает верный результат?

qid00000000 Oct 4 2023 at 09:16

Это не убрал (я сначала написал, потом решил сам проверить и потом эту часть не убрал). Так что по сути, эту часть можно считать необоснованной критикой :)

Также, мой код не совсем прям оптимальный (можно принять, что ищем a>b, а второе число получить путем перестановки их значений, что уменьшит количество вычислений наполовину).

Возможно, у вас код более оптимален, но сложен для понимания.

CBET_TbMbI Oct 4 2023 at 10:22

"при маленьких числах её проверили до конца, а при больших числах члены цепочки уменьшаются"
Про большие не понял. Почему при больших какие-то члены должны уменьшатся.

domix32 Oct 4 2023 at 13:09

тут в общем-то формулировка в принципе некорректно составлена, ибо непонятно когда кончаются маленькие числа и начинаются большие. Теренс Тао презентовал доклад, о том что статистически большинство чисел (99+%) всегда будет сходится к циклу в единице - видимо это подразумевалось под "проверили".

Почему при больших какие-то члены должны уменьшатся.

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

CBET_TbMbI Oct 4 2023 at 17:47

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

domix32 Oct 4 2023 at 21:10

Это лишь предположение

термин "гипотеза" ровно это и значит.

есть ещё сценарий, когда в какой-то момент число начинает гарантированно приходить к числам больше исходного и уходит в бесконечность.

SemenovVV Oct 4 2023 at 12:03

меня заминусовали на исследовании варианта преобразования 3*N - 1

https://habr.com/ru/articles/672824/

там появляются циклы

wataru Oct 4 2023 at 12:15

del. ошибся веткой.

wataru Oct 4 2023 at 12:15

Итак, я поставил себе задачу — найти все такие нечётные множители, для которых существуют подобные циклы.

И как, число 3 — является таким множителем, или нет?
Вы, получается, гипотезу коллатца доказали?

Ну у вас в статье только циклы "длины" 2 рассматриваются. И то, вы запустили перебор, нашли какие-то числа и утверждаете, что это все возможные.

Пока вы не приведете математическое доказательство, что для всех больших n таких циклов нет — эта статья ни о чем.

lightln2 Oct 6 2023 at 01:21

А я вот хочу автору сказать спасибо за статью, и позволю не согласиться, что статья ни о чем.
Что я из нее понял:

Автор рассматривает обобщение гипотезы Коллатца на произвольный нечетный множитель и рассмаривает, наверное, самую простую задачу (не считая тривиальной задачи нахождения неподвижных точек) нахождения циклов длины 2. Я быстрым гуглопоиском не нашел, чтобы кто-то эту задачу до него сформулировал. И даже эта задача, по-видимому, не решается аналитически. Ну и наличие решений для и само по себе неожиданно.
Автор применил интересный трюк, показав, что $n=\lfloor \sqrt{2^c} \rfloor$ . Тем самым он ускорил алгоритм по нахождению циклов с началом, меньшим , с $N \cdot log^2N$ у алгоритма "в лоб", до . Это позволило на питоне проверить все числа до $2^{50000}$ , что позволяет высказать гипотезу, что циклов длины 2, скорее всего, больше нет.
Еще мне было интересно ускорить сам алгоритм, избавившись от извлечения корня и умножений с делениями (мне не удалось избавиться только от одного $n \% p$ ). Мой вариант на с++ с первой попавшейся из интернета имплементацией bigint работает примерно в 10 раз быстрее версии автора на питоне.
Как к задаче подступиться аналитически, совершенно непонятно. Кажется, что $p = 2^c-n^2\sim2n\cdot\{ \sqrt{2}\cdot 2^{(c-1)/2} \}$ (фигурные скобки - это дробная часть), и вероятность найти $n + 2^i = 0\ mod\ p$ стремится к нулю, если в двоичном представлении корня из двух нет очень больших последовательностей из нулей, и $p = \Omega(n)$ . Это предположение верно, если корень из двух - это нормальное число в двоичной системе счисления, но это не доказано.