07.07.2022 11:52
Lloyder 108 2600 Источник

Доказательство гипотеза Колатца, Проблемы 3n+1,
Проблемы Какутани

Введение и результаты

Привет, Хабр! В данной статье мы рассматриваем гипотезу Колатца, которая заключается в следующем. Если мы возьмём произвольное число, то нам нужно посмотреть на то, чётное ли оно. Если чётное, то делим на два, если не чётное, то умножаем на 3 и прибавляем 1. Потом с получившимся числом делаем тоже самое. Например возьмём 5. 5 нечётное, значит умножаем на 3 и прибавляем 1. Получаем 16. 16 чётное, значит делим на 2, получаем 8. И так далее. 16->8->4->2->1. А дальше следующее 1->4->2->1->4… . Получаем цикл. Гипотеза Колатца заключается в том, что любое число после некоторого конечного числа операций, превратится в 1, то-есть войдёт в этот цикл. На данный момент методом компьютерного перебора было изучено 2 в степени 64 чисел. Все они приходили к циклу 1->4->2->1. В данной статье я докажу что все числа приходят к циклу 1->4->2->1, подтвердив гипотезу Колатца. Так же в данной статье будет рассмотрен вариант опровержения гипотезы. По сути гипотеза неверна в двух случаях, если есть другой цикл, кроме, 1->4->2->1. Или же существует число, которое бесконечно растёт.

Доказательство

Докажем, что каждое число, кроме 1, в последовательности содержит число меньше данного. В таком случае взяв произвольное число, и применив к нему доказательство мы получим число меньше данного. Применив к полученному числу доказательство, мы получим опять число меньше данного и т.д. В итоге мы придём к 1, что и требовалось доказать.

Рассмотрим натуральный ряд:

N={1,2,3,4,5,6,7,8,9,10,11,12,13,...}

Начнём последовательно применять правило для каждого числа:

N={1,2,3,4,5,6,7,8,9,10,11,12,13,...}

{4,1,10,2,16,3,22,4,28,5...}

После первого шага видно что для чётных чисел гипотеза верна, ведь они стали числами меньше исходного. Значит дальше следует рассматривать то что получилось от нечётных чисел. Применим правило для них. Так как получились все чётные (Ведь мы к нечётному прибавили 1, то дальше все будем делить на два):

{10,16,22,28,34,40,46,52}

{ 5 , 8, 11,14,17,20,23, 26}

Дальше опять, чередующийся в плане чётности ряд. На данный момент, мы один раз воспользовались правилом 3n+1 и один раз правилом n/2 для исходных нечётных чисел. Продолжим использовать правило:

{5,8,11,14,17,20,23,26,29,32,...}

{16,4,34,7,52,10,70,13,88,16,...}

Заметим, что числа: 7, 10, 13, 16. Изначально были: 9, 13, 17, 21. То-есть все они стали меньше изначального. Докажем, что для всего этого ряда верно утверждение о существовании числа меньше данного.

Действительно: Числа имеют вид: K_{n}=K_{1}+4n, K_{1}=9. То-есть сначала умножаем на 3 и прибавляем 1. Получим: 3*K_{n}+1потом делим на 2, (3*K_{n}+1)/2. Так как опять получилось чётное, опять делим на 2. Ведь мы берём каждое второе число, увеличив шаг в два раза. Получаем (3*K_{n}+1)/4. Проверим когда получившееся число меньше данного:

(3*K_{n}+1)/4<K_{n},\Leftrightarrow 3K_{n}+1=4K_{n}, \Leftrightarrow K_{n}>1

То-есть, в случае если исходное число больше 1, мы получим число меньше данного. Лемма доказана. Заметим что для данной последовательности, мы один раз использовали 3n+1 и два раза n/2. Обозначим количество раз использования 3n+1, за X. Количество раз использования n/2 за Y. То-есть тут X=1, а Y=2. Заметим так-же, что тенденция пока следующая. Часть чисел из {5,8,11,14,17,20,23,26,29,32} после деления станет числом меньше данного, а часть чисел пойдёт дальше для следующего изучения.

Дальше доказательство гипотезы сводится к следующему. Если доказать что на каждом шаге (При передачи ряда чисел), часть из них станет числом меньше данного, а часть передастся дальше, то получим следующее: Любые первые n натуральных чисел на каком-то шаге станут числом меньше данного. Что и требовалось доказать.

Доказательство: Рассмотрим общий вид числа после шагов, он следующий (3^xn+m)/2^y. Соответственно число станет меньше изначального если (3^xn+m)/2^y<n (1), где m это число вида (3 * (3* ... (3*( 3*(3*1 +1))+1*2)+1*4)+1*8) ... +1 * 2^t). Почему? Ну начинаем сначала. Было некое n, потом стало 3n+1, потом обязательно делим на 2. То-есть (3n+1)/2. Здесь m=1. Потом мы либо делим на 2, либо опять 3n+1. Допустим 3n+1, тогда потом опять делим на 2. Будет 3*(3n+1)/2=(9n+3)/2, потом +1. Для m будет 5, то-есть 3*1+2. Прибавляем 2 а не 1, ибо у числа к которому прибавляем есть знаменатель 2 и нам нужно привести к общему знаменателю, потом делим на 2, будет (9n+5)/4. Если опять 3n+1, то будет (27n+15)/4, и прибавляем 1. Приводим к общему знаменателю, то-есть к m прибавляем 4. И так далее. Основа для m это 1. Потом умножаем на 3 и или прибавляем 1 приведённую к общему знаменателю.

Лемма: m всегда меньше 3^x. Действительно m содержит степень тройки, однако начинает умножение на шаг раньше, с 1, а прибавление степени двойки меньше, чем умножение на 3, сравнивая темпы роста производных.

Лемма, докажем что 3^x<2^y. Доказательство от противного: если , 3^x>2^yто неравенство 1 не выполняется.

Докажем что для любого числа над которым было X использований 3n+1 операций, достаточно что-бы было 2*Y шагов использования операций n/2. И тогда число обязательно станет меньше исходного. Где Y=[(log_2 3)*X+1]. Где [] это функция округления вниз.

Доказательство: Заметил что раз после операции 3n+1, нечётное число станет чётным, то следующая операция обязательно будет n/2. Таким образом, Y>=X. То-есть, нужно доказать что после дополнительных операций n/2, число станет меньше данного. (Количество которых t в пределах t \geq Y-X)

Рассмотрим неравенство 1 для если m = 0. В таком случае количество операций Y и X не зависят от самого числа, а зависят только от X или Y (Одно выражается через второе). Выразим Y через X и получим Y=[(log_2 3)*X+1]. Однако m убирать нельзя. Ведь если убрать m и все числа на каком-то шаге станут меньше исходного, что с m в знаменателе оно может и не стать меньше исходного либо стать исходным, образовав новый цикл. В случае если m не 0, количество операций будут зависеть от самого n. Перепишем неравенство 1.

n(2^y- 3^x)>m (2)

n>m/(2^y-3^x)

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

Лемма: Для чисел описанных в ситуации выше (Которые предположительно будут расти бесконечно далеко либо образовывать новый цикл) они так же либо перейдут дальше, либо после дополнительных Y делений на 2, гарантировано станут числами меньше исходных.

Действительно, после Y дополнительных делений на два получим: (3^xn+m)/(2^y2^y)<n. Или в виде неравенства 2:

n(2^y*2^y-3^x)>m, \Leftrightarrow n(2^y(2^y-3^x/2^y)>m,

Так как 3^x<2^y, то t=2^y-3^x/2^y>1, \Leftrightarrow n(2^yt)>m, n >m/(2^yt)

Значит n больше числа, которое меньше единицы. То-есть, получаем что на этом шаге получилось число меньше исходного независимо от исходного числа. Мы доказали второе утверждение леммы. А если число нечётное, то мы используем 3n+1, повышая X, то-есть по определению передаем дальше. Лемма доказана.

Осталось доказать основную теорему: То-есть, что на каждый следующий уровень передаётся ряд чисел с шагом, который позволит нам часть передать дальше а часть сделать числами меньше исходного. И доказать что те числа которые мы передаём дальше, имеют такую же структуру. Докажем по индукции. База индукции тривиальна, поэтому перейдем к шагу.

f(n)\Longrightarrow f(n+1)

Есть набор чисел {K_{1},K_{2},K_{3},K_{4},K_{5},K_{6},K_{7}, ... } они обладают рядом свойств:

  1. Все числа четные.

  2. Их разница имеет вид: 2*3^n,n- натуральное число

  3. Часть множества после ряда Y и X операций станет множеством чисел меньше исходного. 

  4. Часть передается дальше с свойствами 1 и 2.

Если все числа чётные то мы должны разделить их на 2, и получим числа с разнице в 3n. То-есть чередующееся чётные и не чётные. Значит для половины мы умножаем на 3 и прибавляем 1, а половину делим на 2. По нашему условия не важно какой Y нам передается из прошлого ряда, но он точно не меньше X.

Ту часть исходных чисел, для которых мы использовали 3n+1, переходит дальше. С разницей в 2*3^n*3. Потому что выбрав половину чисел мы умножили разницу на 2, а потом операцией 3n+1, умножили разницу на 3.

Остаются числа {K_{2}/2,K_{4}/2,K_{6}/2,K_{8}/2,K_{10}/2,K_{12}/2, ...}

Так как мы опять же, убрали половину чисел и разделили на 2, разница остаётся 2*3^n, Если все числа четные, тогда опять делим на 2, если все нечётные умножаем на 3 и как доказано выше передаёт на следующий уровень.

Получим:{K_{2}/4,K_{4}/4,K_{6}/4,K_{8}/4,K_{10}/4,K_{12}/4, ...}, здесь шаг уже 3^nзначит получим очередь из чётных и нечётных чисел. Заметим что Y увеличился на 2 от исходного множества, ведь мы два раза делили на 2. Если после этого Y стал равен Y=2*[(log_2 3)*X+1] то как уже доказано число гарантировано станет меньше исходного для всех чисел. Если нет, то продолжаем алгоритм с шага про числа чередующейся чётности, пока Y не дойдёт до нужной величины. Шаг Индукции доказан. Гипотеза доказана.

Вот и всё. Пару слов о значении данной работы. Данная работа относится к теории чисел. Теория чисел, наука которая изучает числовой ряд и его закономерности, являются одной из фундаментальных дисциплин в математике. История показывает, как часто фундаментальная математика находит своё применение в более прикладных сферах знания или даже в создании новых гаджетов.

Спасибо что уделили внимание, надеюсь что не ошибся. 

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


  1. xi-tauw
    07.07.2022 13:01
    #24505162

    Рассмотрим общий вид числа после шагов, он следующий (3^xn+m)/2^y <...> , где m это число вида (3 * (3* ... (3*( 3*(3*1 +1))+1*2)+1*4)+1*8) ... +1 *2y).

    Вас не затруднит обосновать это?

    А то эта формула выглядит прям очень странной. То есть, вот я фиксирую число x и вот так вот случилось, что следующие шаги будут разные - одно деление пополам, одно утроение с увеличением. Но я не знаю что именно получится для произвольного числа. В одном порядке это будет 3(x/2)+1, а в другом (3x+1)/2.


    1. Lloyder Автор
      07.07.2022 13:15
      #24505232

      Согласен, добавлю.


      1. Lloyder Автор
        07.07.2022 13:35
        #24505306

        Добавил


        1. xi-tauw
          07.07.2022 13:48
          #24505362
          +1

          Лучше не стало. Будьте, пожалуйста, математически строги.

          Например, если я возьму y = (3^x) * n + m, то довольно очевидно, что получившееся число в вашей формуле будет не то, что меньше n, оно будет меньше 1. Но такое число преобразованиями 3n+1 и n/2 получить нельзя. Таким образом, не каждое число из вашей формулы является корректным числом в последовательности, а значит дальнейшие рассуждения не имеют смысла.


          1. Lloyder Автор
            07.07.2022 13:59
            #24505394
            -1

            С чего вы взяли что мы получим число меньше 1?


            1. xi-tauw
              07.07.2022 14:02
              #24505414
              +1

              При указанном y, формула приобретает вид y/(2^y).


              1. Lloyder Автор
                07.07.2022 14:07
                #24505448

                Можно цитату откуда этот вывод?


                1. xi-tauw
                  07.07.2022 14:17
                  #24505502
                  +1

                  Рассмотрим общий вид числа после шагов, он следующий (3^xn+m)/2^y

                  Поскольку я не вижу больше никаких ограничений, то я предлагаю взять y = (3^x)n+m (это числитель из вашей формулы). Вот и получаем y/(2^y),


                  1. Lloyder Автор
                    07.07.2022 14:27
                    #24505538

                    Как связаны y и x дальше объясняется. Когда y становится равен 2*[(log_{2} 3)*x+1] то число гарантированно станет меньше исходного. y не дойдёт до значений (3^x)n+m


                    1. xi-tauw
                      07.07.2022 15:14
                      #24505730
                      +1

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


                      1. Lloyder Автор
                        07.07.2022 15:16
                        #24505742
                        -1

                        Безусловно ваше право


          1. Lloyder Автор
            07.07.2022 14:03
            #24505420

            Условие на n, что оно больше числа которое меньше 1. Это не говорит что n=1, n может быть и 2 и 3 и какое угодно большое.


            1. domix32
              08.07.2022 00:51
              #24507490
              +1

              Как минимум формулы и леммы необходимо пронумеровать, чтобы понимать про что конкретно идёт речь. А то даже ваша лемма (какая-то непосчитанная) спорит с неким неравенством 1, но не уточняет где оно.


  1. 1dash
    07.07.2022 13:05
    #24505174

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

    В таком случае, так же может быть не рассмотренный случай, когда достаточно большое число растёт сколько то раз, а потом при уменьшении становится равно себе же - те есть цикл (Вопрос: насколько большое? количество атомов в Вселенной? больше числа Грэма?)


    1. Lloyder Автор
      07.07.2022 13:35
      #24505304

      Насколько большое судить не берусь. Ведь рассматривается общий случай для всех чисел. А случай с новым циклом рассматривается далее. Ведь каждое число кроме 1 становится числом меньше данного, то-есть цикла быть не может.


    1. Lloyder Автор
      07.07.2022 13:53
      #24505378

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


  1. korolevdd
    07.07.2022 13:40
    #24505324
    +1

    Смотрел интересный ролик на эту тему, там много кто пытался доказать, но не вышло. https://www.youtube.com/watch?v=QgzBDZwanWA


    1. Lloyder Автор
      07.07.2022 13:45
      #24505348
      +1

      Да, отличный видос. Оттуда подрезал фото на превью)


  1. unC0Rr
    07.07.2022 13:48
    #24505358
    +1

    Если нет, то продолжаем алгоритм с шага про числа чередующейся чётности, пока Y не дойдёт до нужной величины.
    Чем этот пассаж отличается от «применим алгоритм Колатца, пока не получится 1, чтд»?


    1. Lloyder Автор
      07.07.2022 14:00
      #24505406

      Не понял утверждения. Что за алгоритм Колатца?


      1. unC0Rr
        07.07.2022 14:08
        #24505454
        +1

        Алгоритм из гипотезы Колатца: чётное число делим на два, нечётное умножаем на 3 и прибавляем 1, повторяем.


        1. Lloyder Автор
          07.07.2022 14:12
          #24505486

          Да, думаю так лучше бы было сформулировать.


          1. unC0Rr
            07.07.2022 15:50
            #24505896

            Так а будет ответ на вопрос? Рассуждение "Если нет, то продолжаем алгоритм с шага про числа чередующейся чётности, пока Y не дойдёт до нужной величины" нужно доказывать в той же мере, что и исходную задачу. Действительно ли Y дойдёт до нужной величины за конечное число шагов?


            1. Lloyder Автор
              07.07.2022 15:59
              #24505934

              Y натуральное число, 2*Y тоже натуральное. При деление на 2, к Y прибавляем 1. Конечно дойдёт.


  1. antonkrechetov
    07.07.2022 14:04
    #24505424

    Есть набор чисел {K_{1},K_{2},K_{3},K_{4},K_{5},K_{6},K_{7},… } они обладают рядом свойств:

    Все числа четные.

    …

    Часть множества после ряда Y и X операций станет множеством чисел меньше исходного.

    Часть передается дальше с свойствами 1 и 2.
    Если все числа чётные, абсолютно все числа из этого «множества» после первой же операции станут меньше исходного. То есть, это утверждение тривиально — «дальше» ничего не «передается».

    Также замечу, что довольно трудно читать такое доказательство. Много понятий, которым вы не даете формального определения («Y нам передается из прошлого ряда» — что?), плюс очень вольное обращение с терминологией (то, что вы выше называете множеством, — не множество).

    UPD: насчёт «не множества» я поспешил, извиняюсь.


    1. Lloyder Автор
      07.07.2022 14:06
      #24505438

      Согласен. Это моя первая публикация, я открыт к критике. Ну а по вашим аргументам. Y передаётся из прошлого ряда, имеется ввиду что количество операций n/2 передаётся из прошлого ряда. А "Если все числа чётные, абсолютно все числа из этого «множества» после первой же операции станут меньше исходного." Тут же чётные, но это не изначальные числа. Над ними уже были операции.


      1. antonkrechetov
        07.07.2022 14:34
        #24505562

        Y передаётся из прошлого ряда, имеется ввиду что количество операций n/2 передаётся из прошлого ряда.
        Я не знаю:
        — Что такое «ряд».
        — Что такое «прошлый».
        — Как количество операций может «передаваться» и зачем.
        Также непонятен шаг индукции: какое утверждение вы доказываете, и как именно конструируете множество для следующего шага из множества на текущем. Из-за этого непонятна и база индукции, кстати.
        Все-таки K1, K2… — это у вас множество или последовательность?


        1. Lloyder Автор
          07.07.2022 14:41
          #24505602

          Да, думаю последовательность лучше слово. Так прошлый ряд, это последовательность из которого посредством операций Колатца получилось последовательность для нового шага индукции. Утверждение индукции: Если для данной последовательности выполнен ряд условий (4 условия описаны), то посредством операций Колатца над её элементами мы получим либо числа меньше изначальных, либо числа у который количество операций 3n+1 на одну больше. То-есть они образовывают последовательность для следующего шага индукции.


  1. v__17
    07.07.2022 14:56
    #24505650
    +3

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

    Доказательство: Рассмотрим общий вид числа после шагов, он следующий (3^xn+m)/2^y. Соответственно число станет меньше изначального если(3^xn+m)/2^y<n (1), где m это число вида (3 * (3* ... (3*( 3*(31 +1))+12)+14)+18) ... +1 2y). Почему? Ну начинаем сначала. Было некое n, потом стало 3n+1, потом обязательно делим на 2. То-есть (3n+1)/2. Здесь m=1. Потом мы либо делим на 2, либо опять 3n+1. Допустим 3n+1, тогда потом опять делим на 2.

    Будет 3(3n+1)/2=(9n+3)/2, потому +1.

    Для m будет 5, то-есть 3*1+2. Прибавляем 2 а не 1, ибо у числа к которому прибавляем есть знаменатель 2 и нам нужно привести к общему знаменателю, потом делим на 2, будет (9n+5)/4. Если опять 3n+1, то будет (27n+15)/4, и прибавляем 1. Приводим к общему знаменателю, то-есть к m прибавляем 4. И так далее. Основа для m это 1. Потом умножаем на 3 и или прибавляем 1 приведённую к общему знаменателю.

    Почему 3(3n+1)/2, если (3(3n + 1) + 1)/2 = (9n + 4)/2, что такое "потому +1" и почему для m будет 5?

    UPD: Запутался в выкладках автора, имелось в виду 3(3n+1)/2 + 1 = (9n + 5)/2, что в принципе верно, но никак не отменяет факта, что читать и понимать ужасно трудно.


    1. Lloyder Автор
      07.07.2022 15:00
      #24505660

      Да, тут опечатка "Потом +1". Будет 3(3n+1)/2, а не (3(3n + 1) + 1)/2. Сначала умножаем на 3, 3(3n+1)/2, потом прибавляем 1. Но 1 нужно привести к общему знаменателю 2. 1 = 2/2. Поэтому прибавляем 2. Об этом далее писалось.


      1. v__17
        07.07.2022 15:09
        #24505706

        Рассмотрим общий вид числа после шагов, он следующий (3^xn+m)/2^y.

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

         где m это число вида (3 * (3* ... (3*( 3*(3*1 +1))+1*2)+1*4)+1*8) ... +1 *2y)

        К тому же непонятно какой вид все-таки имеет число m, слагаемые в скобках это последовательные четные числа (абстрактный 2y) или все-таки степени двойки (1, 2, 4, 8)?


        1. Lloyder Автор
          07.07.2022 15:10
          #24505708

          Да, тут опечатка. Степень двойки конечно.


          1. v__17
            07.07.2022 15:35
            #24505826

            где m это число вида (3 * (3* ... (3*( 3*(3*1 +1))+1*2)+1*4)+1*8) ... +1 * 2^y)

            Для m будет 5, то-есть 3*1+2. Прибавляем 2 а не 1, ибо у числа к которому прибавляем есть знаменатель 2 и нам нужно привести к общему знаменателю, потом делим на 2, будет (9n+5)/4.

            Мы получили число (9n+5)/4 на очередном этапе применения алгоритма, m отсюда равно 5. Но число 5 не является членом последовательности, которой вы указали для m выше. Поправьте, если я неправ, но вы говорите, что m является одним из членов следующей последовательности:

            f(0) = 1

            f(n) = 3f(n-1) + 2^(n-1)

            f(1) = 4, f(2) = 14, f(n+1) > f(n) для всех натуральных n

            Нужна более точная формулировка и строгое доказательство факта выше.


            1. Lloyder Автор
              07.07.2022 15:42
              #24505858

              Тут не получится определить через прошлые члены. Поскольку это не линейная последовательность. Тут есть ветвлении. Делим на 2, это одно ветвление, умножаем на 3 и прибавляем 1, это другое ветвление


              1. v__17
                07.07.2022 15:44
                #24505866

                где m это число вида (3 * (3* ... (3*( 3*(3*1 +1))+1*2)+1*4)+1*8) ... +1 * 2^y)

                Вы же определили, деления я в этой формуле не наблюдаю


                1. Lloyder Автор
                  07.07.2022 15:48
                  #24505886

                  В этой формуле деление и не нужно. Зачем?


              1. v__17
                07.07.2022 15:51
                #24505914

                И, пожалуй, последнее противоречие

                где m это число вида (3 * (3* ... (3*( 3*(3*1 +1))+1*2)+1*4)+1*8) ... +1 * 2^y)

                откуда следует, что m > 2^y

                Лемма: m всегда меньше 3^x

                откуда из 3^x> m и m > 2^y следует 3^x > 2^y

                Лемма, докажем что 3^x<2^y. Доказательство от противного: если , 

                3^x>2^yто неравенство 1 не выполняется.

                Противоречие, доказательство некорректно, на этом я пожалуй оставлю свои попытки понять этот поток мыслей.


                1. Lloyder Автор
                  07.07.2022 15:56
                  #24505926

                  (3 * (3* ... (3*( 3*(3*1 +1))+1*2)+1*4)+1*8) ... +1 * 2^y) Y здесь, это не тот что в 2^y. Опять опечатка, исправлю.


                  1. v__17
                    07.07.2022 16:03
                    #24505952
                    +1

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


                    1. Lloyder Автор
                      07.07.2022 16:12
                      #24505988

                      Это моя первая в жизни публикация, не судите строго


                      1. v__17
                        07.07.2022 16:48
                        #24506178

                        Лемма, докажем что 3^x<2^y

                        ...
                        n(2^y- 3^x)>m 

                        (2)n>(2^y-3^x)/m

                        А это что за чудеса арифметики


                      1. serejk
                        07.07.2022 17:13
                        #24506256

                        Присоединяюсь.


                      1. Lloyder Автор
                        07.07.2022 17:25
                        #24506294

                        Ошибся, щас поправлю


  1. serejk
    07.07.2022 14:59
    #24505658

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


    1. Lloyder Автор
      07.07.2022 15:02
      #24505670

      То-есть у вас есть критика к аргументам тут? Или почему вы считаете что тут нет доказательства? Ну а описать прогресс, тут да, моя ошибся. Это было бы плюсом.


      1. serejk
        07.07.2022 15:06
        #24505684

        Признаться честно, у Вас довольно специфический язык изложения, для такого рода статей. Я пока не смог продраться :-) будет лучше, если Вы ещё раз вычитаете и систематизируете мысли.


        1. Lloyder Автор
          07.07.2022 15:08
          #24505704

          Ну тут согласен, прочитать ещё раз не повредит.


          1. serejk
            07.07.2022 15:25
            #24505784

            Но проблема мне видится уже в самом начале.

            «Докажем, что каждое число, кроме 1, в последовательности содержит число меньше данного. В таком случае взяв произвольное число, и применив к нему доказательство мы получим число меньше данного. Применив к полученному числу доказательство, мы получим опять число меньше данного и т.д. В итоге мы придём к 1, что и требовалось доказать»

            1. Если в последовательности чисел-градин (это официальная терминология), встретится число меньше исходного - разве это гарантирует, что начиная с этого меньшего числа вся последовательность не уйдёт в бесконечность?

            2. Ну и вывод о том, что в итоге придём к 1 - это утверждение , которое само по себе требует доказательства.


            1. Lloyder Автор
              07.07.2022 15:29
              #24505798

              Для обоих пунктов один ответ: На примере: Было число миллиард, по нашей теореме в его последовательности есть число меньше, это 500 миллионов. Для числа 500 млн в его последовательности есть число меньше. И тд. Но натуральный ряд нельзя уменьшать бесконечно, поэтому мы упрёмся в 1.


              1. LeXaNe
                07.07.2022 15:44
                #24505868

                Не обязательно должно уходить в бесконечность - есть доказательство, что где нибудь не зациклится?

                P.S Когда игрался с данной гипотезой, то мыслил примерно, как описано в статье


                1. Lloyder Автор
                  07.07.2022 15:46
                  #24505882

                  Допустим есть другой цикл. В этом цикле есть минимальный элемент. Но по нашей теореме каждый элемент кроме 1 имеет элемент меньше своего. Противоречие


                  1. LeXaNe
                    07.07.2022 16:30
                    #24506080

                    А как же увеличение числа, если оно не четное 3*n+1?


                    1. Lloyder Автор
                      07.07.2022 16:34
                      #24506116

                      Количество операций деления на 2 перебивают рост от 3n+1


                      1. LeXaNe
                        07.07.2022 16:45
                        #24506166

                        (27*3+1)/2=41 уже число больше получилось

                        (41*3+1)/2= 62 /2= 31 опять число больше исходного


                      1. Lloyder Автор
                        07.07.2022 16:47
                        #24506174

                        Будет же не одна операция деления на 2. Их будет больше чем операций 3n+1. Когда получите число меньше исходного, посчитайте количество тех и тех операций


                      1. LeXaNe
                        07.07.2022 16:53
                        #24506190

                        А если число вернётся в исходное? Допустим есть число гугол в гуглятой степени - нечётное. После несколько миллиард итераций, мы вернулись к исходному. Причем не дошли до той итерации, где мы выходили на число меньше, чем исходное


                      1. Lloyder Автор
                        07.07.2022 17:08
                        #24506242

                        Это новый цикл, почему его быть не может в моём доказательстве уже рассказывалось. И я вам комментарием уже рассказывал.


              1. serejk
                07.07.2022 17:16
                #24506266
                +1

                Нет, дальше этого я не могу прорваться.

                "Лемма: m всегда меньше 3^x. Действительно m содержит степень тройки, однако начинает умножение на шаг раньше, с 1, а прибавление степени двойки меньше, чем умножение на 3, сравнивая темпы роста производных."

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


                1. Lloyder Автор
                  07.07.2022 17:55
                  #24506396

                  Ну как строится m, сначала идёт число 1, а не 3, поэтому на одну степень тройки он будет отставать. Даже если прибавлять степень двойки, всё равно это меньше чем умножение на 3.


                  1. serejk
                    07.07.2022 18:07
                    #24506424

                    У Вас m - это по сути некоторая функция от t, так ведь? m при раскрытии скобок примет вид: 3^t + .... И как сравнить его с 3^x, при том, что и x, и t - неизвестны. Как Вы их сравниваете между собой?


                    1. Lloyder Автор
                      07.07.2022 18:13
                      #24506458

                      Нет, m не функция от t. Мы то возводим в степень, то прибавляем степень двойки. Эти операции чередуются. Но при любой доступной комбинации они меньше 3 в степени x


                      1. serejk
                        07.07.2022 18:23
                        #24506484

                        Что Вы имеете ввиду под "чередуются" ? Если текущее число нечетное, то в результате операции Коллатца всегда получим четное - это понятно. А вот при дальнейшем делении на 2 мы никогда не знаем наперед, четным или нечетным будет результат.

                        Для примера, чтобы стало чуть понятнее. Пусть исходное n - четное. Чему, согласно Вашей теории, равны x, y, и m?


                      1. Lloyder Автор
                        07.07.2022 20:39
                        #24506898

                        На по сути вообще не важна чётность числа m


                      1. serejk
                        08.07.2022 01:43
                        #24507562

                        Я не спрашивал про чётность m. Могли бы Вы ответить на мой вопрос, или он неясен?


                      1. Lloyder Автор
                        08.07.2022 06:52
                        #24507704

                        Мы обсуждали можно ли m определить через предыдущие члены последовательности. Я доказал что нельзя. Потом вы начали спрашивать про чётность. О каком ещё числе если не m идёт речь? Тогда давайте цитату из статьи.


                      1. serejk
                        08.07.2022 07:13
                        #24507734

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

                        Поскольку n - четное, то по условиям гипотезы, мы делим его на 2. То есть, x = 0, y = 1. Но получить мы должны n/2. Значит, m = 0, так? Но разве в той записи для m, что приведена - оно может стать нулевым?


              1. serejk
                07.07.2022 17:50
                #24506378
                +1

                Доказательства в математике не строятся на примерах. И в общем случае, наличие в последовательности чисел-градин такого, которое меньше исходного, не гарантирует абсолютно ничего. Утверждение, что цикл 4-2-1 - единственный - также требует доказательства.

                Математики говорят, что гипотеза Коллатца тем и опасна, что манит своей простотой. И на примерах она посчитана до очень больших значений. Но это не является ее математическим доказательством.


                1. Cdracm
                  07.07.2022 18:07
                  #24506426

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


                  1. Lloyder Автор
                    07.07.2022 18:12
                    #24506454

                    Согласен


  1. serejk
    07.07.2022 18:11
    #24506448
    +1

    А что за "проблема Какутани", которая обозначена в начале и в тегах?


    1. Lloyder Автор
      07.07.2022 20:33
      #24506872

      У этой задачи много имён, это одно из них


      1. serejk
        08.07.2022 01:44
        #24507566

        Есть ли ссылка, где данная задача так называется?


        1. Lloyder Автор
          08.07.2022 06:53
          #24507706

          https://www.youtube.com/watch?v=QgzBDZwanWA&ab_channel=VertDider


  1. Milliard
    07.07.2022 20:32
    #24506868
    +2

    Как ваше доказательство справится, если правило слегка модифицировать? Например 3n-1 сходится к следующим последовательностям:
    2, 1
    5, 14, 7, 20, 10
    25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68, 34, 17, 50


    1. Lloyder Автор
      07.07.2022 20:38
      #24506890

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


      1. unC0Rr
        07.07.2022 21:10
        #24507000

        А что именно в рассуждениях сломается?


        1. Lloyder Автор
          08.07.2022 06:53
          #24507708

          Затрудняюсь ответить


  1. 1SilentObserver1
    07.07.2022 20:35
    #24506876
    +6

    Основная проблема в этом доказательстве в самом начале: в предположении что если доказать, что из любого множества часть всегда становится меньше через какое-то количество шагов, а часть "переходит с теми же свойствами", то тогда гипотеза Коллатца доказана. На самом деле, это недостаточно для доказательства, что можно показать на достаточно простом примере:
    Пусть есть некоторое (предположительно большое) число N, для которого гипотеза Коллатца нарушается, а именно, числа в его последовательности никогда не становится меньше N.
    Тогда, если я правильно понял обозначения в статье, то вы доказали что с каждым шагом Коллатца, часть чисел в любом множестве Kₙ станет меньше, а часть образует новое множество Kₙ₊₁, для которого эта же теорема тоже верна. Но тогда наше число N может просто находиться во всех множествах K одновременно: да, с каждым шагом часть чисел становится меньше и "выпадает", а часть переходит на следующий шаг, но вполне может быть такое число N, которое всегда переходит на следующий шаг. Такое число будет с каждым шагом становиться все больше и больше, и всегда будет оставаться во множествах K, хотя, определенно, много других чисел будет выпадать на каждом шаге.
    Если честно, я так и не понял большую часть рассуждений в этой статье, но даже если они верны, гипотеза Коллатца все еще не следует из доказанной теоремы


    1. Lloyder Автор
      08.07.2022 06:49
      #24507702

      Спасибо за комментарий. Я всё перепроверил, да действительно. Ваш аргумент доказывает что я ошибся. Жаль.


  1. ytm1
    07.07.2022 20:35
    #24506878
    +1

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

    Лемма, докажем что 3^x<2^y. Доказательство от противного: если , 3^x>2^yто неравенство 1 не выполняется.

    Это конец доказательства леммы? Если да, то неубедительно, потому что неравенство (1) выше по тексту еще не доказано. Если нет, то непонятно, где у доказательства этой леммы конец.


    1. domix32
      08.07.2022 00:54
      #24507494
      +1

      Даже более того, 3^x растет быстрее 2^y и вроде никаких ограничений на то какими должны быть x и y. Так что где-то не доходя до этой леммы доказательство отваливается.


      1. Lloyder Автор
        08.07.2022 06:59
        #24507716

        На это я уже отвечал, читайте другие комментарии


        1. domix32
          08.07.2022 13:56
          #24508982
          +1

          Серьезно, без верификации при помощи пруверов доказательство не будет подтверждено, так что пишите код. Есть подозрение, что доказательство отваливается еще на постулировании о наличии меньшего члена в последовательности операций для любого нечетного.


  1. domix32
    08.07.2022 00:23
    #24507450

    Теперь надо всё то же самое, только при помощи формальной верификации доказать. На каком-нибудь Lean или Coq.


  1. Refridgerator
    08.07.2022 05:59
    #24507668

    Никакое это не доказательство. Правило, по которому считается каждый следующий член последовательности — это ни что иное, как реккурентно определяемая функция. Поэтому первое, с чего нужно начинать настоящее доказательство — это явным образом определить эту функцию. В этом собственно и состоит главная сложность. Второе — найти её предел при аргументе, стремящемся к бесконечности.


    1. serejk
      08.07.2022 06:20
      #24507682
      +1

      Автор же считает, что он получил такую формулу, на все попытки хоть как-то прояснить ход его мысли или указать на неверные суждения - отрицаются либо игнорируются. Такое вот ребячество :) При том, что данная гипотеза входит в нерешенные задачи математики, и ее решение - это был бы очень сильный результат, который с радостью опубликовали бы лучшие научные журналы мира по математике. Какова цель этой статьи тут - абсолютно непонятно. Получить фидбэк? Автор его игнорирует, да и, честно говоря, это какой-то плохо написанный и непроверенный черновик мыслей, в котором почти невозможно разобраться. Это что, завтра можно открывать любую другую нерешенную задачу, набросать своих мыслей, в конце написать - "Доказано" - и Хабр с радостью это опубликует? Все так плохо?


      1. Lloyder Автор
        08.07.2022 06:47
        #24507698

        Почему-то на те коменты на которые я ответил, вы внимания не обращаете. И говорите что я игнорю. А не приходила мысль что я не успел просто ответить? Коментариев много.


      1. Lloyder Автор
        08.07.2022 06:58
        #24507712

        Конкретно тут аргументов против доказательства я не услышал, поэтому и контр аргументировать не стану


    1. Lloyder Автор
      08.07.2022 06:57
      #24507710

      Рекурентная функция тут не подходит, я об этом уже отвечал в другом комментарии. Ибо тут есть ветвление. И к одинаковым значениям Y и X, можно прийти разными путями и будет разное значение m.


      1. Refridgerator
        08.07.2022 07:10
        #24507722

        Что значит «не подходит», если это она и есть? Понятно, что вся сложность в ветвлении. Придумайте, как его обойти. Слышали о многозначных функциях и функциях от нескольких аргументов? Там тоже к одинаковым значениям можно прийти разными путями, и это не мешает их аналитическому определению.


        1. Lloyder Автор
          08.07.2022 08:22
          #24507816

          С чего вы взяли что это она и есть?


          1. serejk
            08.07.2022 08:26
            #24507826

            Ну потому что это она и есть по определению. И, ветвление, как Вы выше писали, не является проблемой, посмотрите хотя бы на википедии примеры формул рекуррентных последовательностей.


            1. Lloyder Автор
              08.07.2022 09:29
              #24507988

              Я знаю определения рекурентной последовательности. Её применение в моём доказательстве не нужно.


        1. Refridgerator
          08.07.2022 08:57
          #24507902

          Например, от ветвления можно избавиться, если использовать вот эту вот функцию для определения следующего элемента последовательности:


          Проверьте.


          1. serejk
            08.07.2022 10:25
            #24508182

            Да, интересная мысль. Можно переписать, чтобы идея была видна лучше: x/2 + (x/2 + 2x +1)*t, где t = (1 - cos(pi*x))/2, некий признак четности числа. (Извините, не знаю, как вставить красивую формулу в комментарий)


            1. Refridgerator
              08.07.2022 10:58
              #24508328

              Красивые формулы в комментарий вставляются немного заморочено. Сначала типа такого ресурс, затем printscreen, затем вставить в paint, затем обрезать лишнее и сохранить, затем загрузить на habrastorage и скопировать оттуда ссылку.

              А подход стандартный, до упрощения формула выглядела так:


              1. serejk
                08.07.2022 11:13
                #24508376

                Ой, какая жесть со вставкой формул. Я причем пытался хелп найти, статья на хабре от 2017 года, где написано, что поддержки формул в комментариях пока нет.
                Да, идея понятная. Но, как Вы правильно заметили, это не функция, которую можно было бы анализировать.


  1. Mavolio-Bent
    08.07.2022 06:58
    #24507714
    +4

    (3^xn+m)2^{-y}

    Приведенная формула общего вида члена последовательности Коллатца неверна. Она опирается на предположение, что деления на два всегда следуют за умножениями на 3 и прибавлением единицей и не прерываются. Однако, контрпример:


    \frac{10\cdot2^2-1}{3}\cdot2 = 26

    или в обратном порядке: 26 -> 13 -> 40 -> 20 -> 10. Представимо в виде

    (3 \cdot 26 \cdot 2^{-1}+1) \cdot 2^{-2}

    И, возможно, представимо и в виде предлагаемом автором, но уже не соотносясь непосредственно с гипотезой Коллатца.

    Поскольку на этом строится доказательство, то его судьба незавидна.


  1. michael_v89
    08.07.2022 08:09
    #24507790

    Заметим, что числа: 7, 10, 13, 16. Изначально были: 9, 13, 17, 21

    Вы пропустили 34, которое на предыдущем шаге было 11. После деления на 2 оно будет 17, то есть все еще больше 11.
    Ошибка у вас в применении этого правила: "После первого шага видно что для чётных чисел гипотеза верна, ведь они стали числами меньше исходного."
    Они меньше того, которое было на предыдущем шаге вычислений, но исходным оно является только для первого шага. Поэтому на следующих шагах их нельзя отбрасывать только потому что они четные.
    Вам не надо рассматривать отдельно шаги "3x+1" и "x/2", рассматривайте 2 ветки "x/2" и "(3x+1)/2", так будет понятнее.


    1. Lloyder Автор
      08.07.2022 08:24
      #24507822

      Да, 11 не станет на втором шаге меньше исходного. Но оно и не часть последовательности 9, 13, 17, 21.


      1. michael_v89
        08.07.2022 08:46
        #24507866

        Ну так а почему вы рассматриваете только эту последовательность? Потому что другие числа вы отбросили, потому что для них уменьшение якобы доказано. А это не так.


        1. Lloyder Автор
          08.07.2022 11:24
          #24508412

          С чего вы взяли что для них уменьшение не доказано?


          1. michael_v89
            08.07.2022 11:46
            #24508496

            Потому что оно не доказано для 11.


            {16,4,34,7,52,10,70,13,88,16,...}
            Заметим, что числа: 7, 10, 13, 16. Изначально были: 9, 13, 17, 21.

            Вы взяли последовательность с 7 и начали про нее что-то доказывать, но почему-то отбросили 34 = 11*3 + 1, хотя про него еще ничего не доказано.


            1. Lloyder Автор
              08.07.2022 12:26
              #24508668

              А про последовательность 16, 34, и тд идёт речь дальше. По сути основное доказательство, это как раз про оставшуюся последовательность 16, 34 и тд


              1. michael_v89
                08.07.2022 13:14
                #24508836

                Но у вас же там отсылка к последовательности для 9:


                "Лемма, докажем что 3^x < 2^y. Доказательство от противного: если 3^x > 2^y то неравенство 1 не выполняется."
                А неравенство 1 справедливо только для последовательности с 9, а не с 11, потому что там деление на 4, а если начальное число на 2 больше, то результат на 4 делиться не будет.


                Рассмотрим общий вид числа после шагов, он следующий (3^x*n + m) / 2^y.

                На первом шаге для начального числа n следующее число имеет вид (3*n + 1) / 2 (после +1 всегда получается четное, поэтому всегда делим на 2).
                3 в первой степени, 2 тоже, неравенство 3^x < 2^y не выполняется.


  1. truefreewill
    08.07.2022 12:24
    #24508652
    +1

    Автор, конечно, хочет, чтобы ему точно указали его ошибки. Это правильное и естественное желание. Но чтобы точно указать ошибку нужно разобраться в написанном. А вот с этим проблемы. Написано плохо и не всегда понятно. Не всегда понятно что автор берет, что он с этим делает и т.п. Профессионал, вероятно, сумел бы догадаться. Но здесь нет профессионалов в гипотезе Колатца. На эту тему, видимо, даже не было статей на Хабре. Здесь нет даже любителей в этом вопросе. Вряд ли здесь помогут автору.

    Извините, автор, за прямоту, но Вы даже не овладели математическим языком, который должен быть ясным и предельно точным. Давайте договоримся. Вы возьмете любую статью в математическом журнале на эту тему. Разберетесь в ней, так, что бы могли ответить на любой вопрос. И после этого попробуете еще раз изложить свое доказательство.

    Искренне желаю успехов.


    1. serejk
      08.07.2022 15:10
      #24509168
      +4

      На Хабре есть статьи об этом, и не одна. По-моему, в прошлом году была, рассказывалось о последнем прогрессе в данном вопросе.

      Я скажу что думаю: у меня сложилось впечатление, что все, что автор знает о задаче - это видос с ютуба. И статья эта - она чисто ради статьи.


  1. truefreewill
    08.07.2022 18:13
    #24509818

    Я бы не сказал, что эта статья есть имитация статьи. Определенная идея в ней есть. После некоторой цепочки преобразований любое число уменьшается. Для этого нужно доказать, что делений на 2 значительно больше чем умножений на 3. Идея нехитрая, наверняка ее кто-то уже рассматривал. Но автор аккуратно проделать этого не смог.

    Странно читать безграмотные математические доказательства на сайте для программистов. Стали бы вы читать безграмотные программы на математическом сайте?