03.10.2023 17:03
fish224 15 1700 Источник

Расширенная гипотеза Коллатца, или проблема "nx+1"


Вероятно, все уже слышали про гипотезу "3х+1", или гипотезу Коллатца.


Правила очень простые. Берём любое число. Если оно нечётное, умножаем его на 3 и добавляем 1. Если оно чётное, делим на 2. Повторяем то же самое действие с результатом. Обязательно ли в конце мы получим 1?


Например, берём число 7. Оно нечётное, поэтому умножаем его на 3 и добавляем 1. Получается 22. 22 чётное, поэтому его делим на 2 и получаем 11. Получается такая "цепочка":


7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4


4 повторилось 2-й раз, следовательно, мы пришли к циклу 1 -> 4 -> 2, который будет продолжаться бесконечно. Поскольку после каждого нечётного числа мы обязательно перейдём к чётному, поэтому далее мы будем опускать чётные числа в нашей цепочке, сократив её примерно в 3 раза. (7 -> 11 -> 17 -> 13 -> 5 -> 1).


Скорее всего, гипотеза справедливая, так как при маленьких числах её проверили до конца, а при больших числах члены цепочки уменьшаются. Однако всё надо необходимо доказывать строго.


Данная задача показалась мне скучной, поэтому я решил видоизменить гипотезу Коллатца. Почему, если наше число нечётное, мы должны умножать его именно на 3? Ведь мы бы могли умножать число на любое нечётное.


Например, у нас есть нечётное число. Умножим его на 5, добавим 1, а затем будем его делить на 2, пока оно чётное. Сделаем тоже самое с результатом, и так далее. Придём ли мы в конце к единице?


На этот раз, ответ отрицательный. Например, если мы начнём с числа 13, то получим цикл из 3 чисел {33, 83, 13}, следовательно, мы никогда не придём к числу 1.


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


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


Пусть x — это число в цикле, n — это множитель, на который мы умножаем (в стандартной гипотезе Коллатца он равен 3), а a и b — это количество двоек, которые содержатся в промежуточных числах. Тогда мы получаем следующее уравнение:


\frac{xn + 1}{2^a} *n + 1 = 2^b * x


(Мы берём число x, умножаем на n, добавляем 1, делим на несколько двоек, снова умножаем на n, добавляем 1 и получаем х, умноженный на ещё несколько двоек).


Попробуем теперь преобразовать это уравнение в произведение или дробь.


xn^2 + n + 2^a = x2^c, c = a+b



2^a + n = x(2^c - n^2)



x = \frac{2^a + n}{2^c - n^2}


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


Стоит обратить внимание, что c > 2a, ведь в любой цикл, который мы ищём, входят 2 числа, которые оба подходят в уравнение с одинаковыми с и n, однако, с разными значениями a — у одного c > 2a, у другого c < 2a. Поскольку нас не интересует находить один и тот же цикл два раза, мы будем искать только меньшее из двух чисел в цикле.


Из этого следует, что для каждого 2^c может подходить не более одного n: 2^a < n (иначе (xn + 1) / 2^a будет меньше, чем x, а ведь наше число х — меньшее в цикле), следовательно, 2^a + n < 2n, следовательно, 2^c — n^2 также меньше чем 2n. Мы все знаем, что разница между соседними квадратами составляет 2n + 1, следовательно, (n+1)^2 больше, чем 2^c.


Последнее замечание: с — нечётное число, потому что иначе 2^с было бы полным квадратом, и, следовательно, 2^c — n^2 было бы равно 2n + 1, что уже больше 2n, и, следовательно, больше, чем числитель.


Учитывая все эти данные, а также, то, что n нечётное число, мы можем написать программу, которая будет перебирать всевозможные переменные:


import math

for c in range(1, 10000, 2):
    n = math.isqrt(2**c)
    if (n%2==0): continue
    p = 2**c - n**2
    i = 2
    while (i < n):
       if ((n+i) % p == 0): print((n+i)/p, n)
       i = i * 2

Программа нашла всего лишь 3 цикла: это {1, 3} (n = 5), {27, 611} (n = 181) и {35, 99} (n = 181). Пока что неизвестно, что такого особенного в этих двух простых числах, однако, вероятно, дело в том, что их квадраты находятся очень близко к степеням двойки: 181^2 = 2^15 — 7, а 5^2 = 2^5 — 7.


Поскольку близлежащие квадраты лежат только у небольших степеней двойки, я предполагаю, что это все циклы из 2 чисел. Я проверил все c вплоть до 100 001, следовательно, наш множитель n должен быть большим, чем 2^50000. Это очень огромное число.



Я собираюсь также написать и опубликовать вторую часть про циклы, длиною больше, чем 2.


Пока что гипотеза xn + 1, или расширенная гипотеза Коллатца звучит так: 5 и 181 — это единственные возможные множители, при которых существуют циклы, отличные от {1}.

Комментарии (15)


  1. longclaps
    03.10.2023 18:44
    #26025146
    +1

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

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

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


    1. fish224 Автор
      03.10.2023 18:44
      #26025860
      +1

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


  1. Tzimie
    03.10.2023 18:44
    #26025256
    +1

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

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


    1. fish224 Автор
      03.10.2023 18:44
      #26025866
      +1

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


  1. qid00000000
    03.10.2023 18:44
    #26025808
    +1

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

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

    Сама формулировка взята из перевода 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 чисел.

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

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


    1. fish224 Автор
      03.10.2023 18:44
      #26025836
      +1

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


      1. qid00000000
        03.10.2023 18:44
        #26026058

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

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

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


  1. CBET_TbMbI
    03.10.2023 18:44
    #26026318

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


    1. domix32
      03.10.2023 18:44
      #26027086

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

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

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


      1. CBET_TbMbI
        03.10.2023 18:44
        #26028142

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


        1. domix32
          03.10.2023 18:44
          #26028744

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

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

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


  1. SemenovVV
    03.10.2023 18:44
    #26026796

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

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

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


    1. wataru
      03.10.2023 18:44
      #26026848

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


  1. wataru
    03.10.2023 18:44
    #26026850

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

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


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


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


    1. lightln2
      03.10.2023 18:44
      #26033498

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

      1. Автор рассматривает обобщение гипотезы Коллатца на произвольный нечетный множитель и рассмаривает, наверное, самую простую задачу (не считая тривиальной задачи нахождения неподвижных точек) нахождения циклов длины 2. Я быстрым гуглопоиском не нашел, чтобы кто-то эту задачу до него сформулировал. И даже эта задача, по-видимому, не решается аналитически. Ну и наличие решений для n=5 и 181 само по себе неожиданно.

      2. Автор применил интересный трюк, показав, что n=\lfloor \sqrt{2^c} \rfloor. Тем самым он ускорил алгоритм по нахождению циклов с началом, меньшим N, с N \cdot log^2N у алгоритма "в лоб", до log^3N. Это позволило на питоне проверить все числа до 2^{50000}, что позволяет высказать гипотезу, что циклов длины 2, скорее всего, больше нет.

      3. Еще мне было интересно ускорить сам алгоритм, избавившись от извлечения корня и умножений с делениями (мне не удалось избавиться только от одного n \% p). Мой вариант на с++ с первой попавшейся из интернета имплементацией bigint работает примерно в 10 раз быстрее версии автора на питоне.

      4. Как к задаче подступиться аналитически, совершенно непонятно. Кажется, что p = 2^c-n^2\sim2n\cdot\{ \sqrt{2}\cdot 2^{(c-1)/2} \} (фигурные скобки - это дробная часть), и вероятность найти n + 2^i = 0\ mod\ p стремится к нулю, если в двоичном представлении корня из двух нет очень больших последовательностей из нулей, и p = \Omega(n). Это предположение верно, если корень из двух - это нормальное число в двоичной системе счисления, но это не доказано.

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