16.02.2023 08:33
Tzimie 36 9700 Источник

Она же проблема 3n+1 (Collatz conjecture). Это, наверное, самая сложная проблема с самой простой формулировкой — условие может понять и ребенок. А вот сложность самой проблемы такова, что великий математик Эрдош сказал, что «математика еще не готова к решению проблем такой сложности». Ее также сравнивают с сиреной — она манит своей простотой, и некоторые математики увязают в ней надолго без какого либо практического результата.

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

Итак, 3n+1. А почему, собственно, +1? А не +2? +3? С +2 не получится — 3n+2 при нечетных n будет снова нечетным, и мы получим runaway. А вот все нечетные числа можно попробовать. Но пробовать не просто так, а написав код, который тестирует вся начальные числа до миллиона и ищет получившиеcя циклы. Циклы мы обозначаем как кортежи (количество элементов (период), минимальный элемент, максимальный элемент). Для 3n+1 мы получим единственный цикл: (3, 1, 4) (хотя для однозначной идентификации цикла достаточно его знать его минимальный элемент)

Теперь мы готовы отправиться в путешествие, перебирая все нечетные a (adder) в формуле 3n+a.

Степени тройки

Для a=3 мы получим единственный цикл (3, 3, 12). А вот для a=5 мы получим аж шесть циклов: (4, 1, 8), (8, 19, 152), (3, 5, 20), (8, 23, 116), (44, 187, 8324), (44, 347, 10 196). Для a=7 два цикла: (6, 5, 40), (3, 7, 28), для a=9 один: (3, 9, 36)

Далее я использую свою гипотезу H1, что для любого нечетного a количество циклов конечно, то есть нет 'runaways'.

Лишь изредка цикл только один, и имеет период 3. Числа a, для которых это так:

  • a=1 (3, 1, 4)

  • a=3 (3, 3, 12)

  • a=9 (3, 9, 36)

  • a=27 (3, 27, 108)

  • a=81 (3, 81, 324)

  • a=243 (3, 243, 972)

  • a=729 (3, 729, 2916)

  • a=2187 (3, 2187, 8748)

  • a=6561 (3, 6561, 26244)

  • a=19683 (3, 19683, 78732)

Здесь напрашиваются сразу две гипотезы:

H2: все степени тройки <a> создают только один цикл вида (3,a,*). Возможно это не так и при больших значениях a возникают и другие циклы. Мы этого на знаем даже для a=1

H3: никакие другие значения a не дают циклов вида (3,*,*).

Рекорды

Если цикл (3, *, *) это пример компактности, то рассмотрим противоположные случаи.

Рекордсмены по периоду цикла из проверенных мной:

  • a=24917 len=8882 (8882, 13, 98850680), (52, 144043, 21257540), (104, 168379, 89205632), (104, 88267, 106267040), (52, 181931, 35733860), (52, 213163, 20599568)

  • a=22097 len=7784 (7784, 25, 169564136), (778, 247, 2749604), (16, 5815, 144212)

  • впрочем, для больших a это не очень интересно, интереснее, когда len>>a, что встречается только для небольших значений a:

  • a=5 len=44 (4, 1, 8), (8, 19, 152), (3, 5, 20), (8, 23, 116), (44, 187, 8324), (44, 347, 10196)

  • a=17 len=49 (9, 1, 32), (49, 23, 560), (3, 17, 68)

  • a=23 len=69 (69, 41, 4976), (7, 5, 80), (7, 7, 56), (3, 23, 92)

  • a=29 len=106 (6, 1, 32), (26, 11, 392), (3, 29, 116), (106, 3811, 6831320), (106, 7055, 3154208)

  • a=61 len=107 (7, 1, 64), (3, 61, 244), (107, 235, 99832)

  • n=85 len=156 (156, 7, 11332), (9, 5, 160), (4, 17, 136), (49, 115, 2800), (8, 323, 2584), (3, 85, 340), (8, 391, 1972), (44, 3179, 141508), (44, 5899, 173332)

  • n=107 len=159 (159, 1, 36416), (3, 107, 428)

Теперь поищем неудачные значения a с наибольшим числом циклов (все циклы перечислять не буду):

  • a=26207 loops=562

  • a=14197 len=294 loops=330

  • для небольших a

  • a=55 loops=11

  • a=499 loops=53

Фракталы

Я пытался на основе полученных данных построить графики, но ничего красивого не выходило. А вот фрактал получился потрясающий!

Строится он по следующей формуле:

Обратите внимание, как хитро она составлена — при целых значениях z функция f(z) делает итерацию по известной формуле для простых чисел. Зато мы можем в качестве z использовать комплексное число, а adder (обведен красным) мы можем менять плавно и даже придавать ему некорректные значения (2, например).

Обычно фрактал «прижимается» к оси y=0 (вещественная ось, мнимые значения малы по модулю). Это происходит из‑за того, что для мнимых аргументов косинус превращается в гиперболический косинус (цепную линию), а тот убегает в бесконечность как экспонента.

x [0, 20], y [-1.5. 1.5]
x [0, 20], y [-1.5. 1.5]

Хочется увеличить нетривиальные зоны:

x [0,2.5], y [-0.4, 0.4]
x [0,2.5], y [-0.4, 0.4]
x [1.8,2.09], y [0,0.2]
x [1.8,2.09], y [0,0.2]

Самое интересное происходит в этой области, когда adder начинает меняться и фрактал начинает 'течь':

x [1.92,2.0], y [0.05,0.13] adder=1.01
x [1.92,2.0], y [0.05,0.13] adder=1.01

Эту красоту в движении вы можете увидеть на видео. Напоследок замечу, что самое интересное происходит около adder=1, так что выбор единицы неслучаен.

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


  1. little-brother
    00.00.0000 00:00
    #25235914
    +25

    Она же проблема 3n+1. Это, наверное, самая сложная проблема с самой простой формулировкой - условие может понять и ребенок.

    В статье есть формулировка этой проблемы?


    1. Tzimie Автор
      00.00.0000 00:00
      #25235940
      +1

      https://en.wikipedia.org/wiki/Collatz_conjecture

      Я думал она общеизвестна


      1. kay_kay
        00.00.0000 00:00
        #25238966
        +9

        Ваша гипотеза ошибочна.


    1. GospodinKolhoznik
      00.00.0000 00:00
      #25235942
      +39

      хабр еще не готов к формулировке проблем такой сложности


    1. MountainGoat
      00.00.0000 00:00
      #25235954
      +5

      Не, нету. Объясняю: есть функция

      step(uint n) -> uint 
{
    if ( n % 2 == 0 ) return n / 2;
    return 3*n + 1;
}

      Доказать, что цикл while (n != 1) step(n) при любом исходном n > 0 всегда выйдет.


      1. Tzimie Автор
        00.00.0000 00:00
        #25236000
        +1

        Да, всего то проблема останова)


        1. leok
          00.00.0000 00:00
          #25236014
          +3

          Для конкретного алгоритма.


      1. little-brother
        00.00.0000 00:00
        #25236008
        +1

        Ну как вариант можно дать ссылку на другую статью на Хабре про эту гипотезу https://habr.com/ru/post/675594/ (свеженькая, но без красивых картинок).


        1. Nikita22007
          00.00.0000 00:00
          #25244528
          +2

          Что-то так себе статейка. С ходу коротко "доказали" гипотезу, которая пока не поддалась никому. В комментариях много кто выразил сомнения.


      1. alex-khv
        00.00.0000 00:00
        #25236176
        +1

        n = step(n)


    1. MasterMentor
      00.00.0000 00:00
      #25236042
      +4

      Употреблять иностранное слово, когда есть равносильное ему русское слово, - значит оскорблять и здравый смысл, и здравый вкус.
      Что русский язык — один из богатейших языков в мире, в этом нет никакого сомнения.
      (с) Белинский В.Г.

      Гипотеза на русском:
      https://ru.wikipedia.org/wiki/Гипотеза_Коллатца


      1. Tzimie Автор
        00.00.0000 00:00
        #25236388
        +4

        русская статья в 5 раз короче и про фракталы там ни слова.


  1. ksbes
    00.00.0000 00:00
    #25236080
    +1

    Интересно проварьирвать не только слагаемое, но и множитель с делителем. Сдаётся мне там будет что-то красивое на простых числах…


  1. smrl
    00.00.0000 00:00
    #25236208
    +3

    Обожаю последовательность (не в математическом смысле, а в чужом глазу).

    Дано: f(n,a,b). Для начала объясним, почему не будем брать "а" четным. Объяснили? А теперь погнали экспериментировать!

    Вопрос с задних рядов: профессор, а почему мы берем именно b=3? Потому что другие значения в каком-то смысле эквивалентны такому выбору, и этому есть простое и красивое доказетльство? Или просто "потому что потому!"?

    Или вот другая последовательность: "статья про игру жизнь", "статья про игру жизнь", "статья про игру жизнь", "статья, в которой затрагивается вопрос варьирования параметров в..."
    Читатель уж ждет рифму "в алгоритме игры жизнь!" - но нет, сиракузы.
    Ну это же издевательство! Так и не узнаю: почему в игре жинь выбран именно такой алгоритм, и что будет, если его менять? А еще интереснее, изменить число измерений, хотя бы рассмотреть случай трех осей? Или, совсем уж на десерт: а если в правила ввести элемент случайности (аналог квантовости в реальном мире), как будут выглядеть (псевдо?)вечные образования?
    Но нет. Доктор сказал, что сиракузы интереснее - значит, сиракузы интереснее.


    1. Tzimie Автор
      00.00.0000 00:00
      #25236252
      +1

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


      1. smrl
        00.00.0000 00:00
        #25236358
        +1

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


        1. Tzimie Автор
          00.00.0000 00:00
          #25236430
          +2

          А почему вы считаете, что я не интересуюсь?


          1. smrl
            00.00.0000 00:00
            #25236506

            Можно надеяться на статью?


            1. Tzimie Автор
              00.00.0000 00:00
              #25236530
              +2

              Да. Я уже собираю материал для следующей статьи. Пока скажу что там идет автоматический перебор вариантов правил в некотором пространстве и полуавтоматическая оценка 'интересности' результата


              1. wormball
                00.00.0000 00:00
                #25237666

                Кстати говоря. Можно заодно попробовать обсуждаемое правило 3n+1.


    1. DarthPadla
      00.00.0000 00:00
      #25238618
      +2

      http://shcoding.ru/cryptozoe/

      Я попробовал добавить элемент случайности и ещё немножко вещей.. Из полученного опыта могу сказать, что правила игры жизнь тем и хороши, что они максимально просты, но это не точно.


    1. Refridgerator
      00.00.0000 00:00
      #25238992

      Если вам интересны клеточные автоматы — сюда посмотрите, там их миллион, не только Жизнь.


  1. starik-2005
    00.00.0000 00:00
    #25236266
    -2

    Цикл заканчивается, когда значение попадает на число, являющееся степенью двойки. Но в приведенных примерах увидел, что оно всегда равно 16. Получается, что ежели 3н+1 будет степенью двойки, то это последний цикл. Дальше можно думать до бесконечности, но лениво.


    1. dreesh
      00.00.0000 00:00
      #25236304

      С любым делителем будет 100% вероятность найти его степень, так как их число бесконечно. Задача сама по себе не корректна.


      1. ksbes
        00.00.0000 00:00
        #25236352

        Не факт — может мы как-то хитро «ходом коня» будем все эти степени обскакивать?


        1. dreesh
          00.00.0000 00:00
          #25236574

          Вернемся к оригинальной задаче :) Любое не четное станет четным после применения формулы 3n+1, а значит следующий шаг будет деление на 2. В задаче изначально заложен дисбаланс между умножением и делением (делить мы будем каждый раз после умножения, а в некоторых случаях и по несколько раз), если записывать все шаги то делений всегда больше. Но все примеры показывают только не четные числа тем самым вводя в заблуждение легкостью решения.


          1. ksbes
            00.00.0000 00:00
            #25236636
            +2

            Но последовательным делением-умножением мы увеличиваем число каждый раз в 1,5 раза. Т.е. гипотетически мы можем выйти на «убегающую» последоветельность, где за каждым умножением идёт в среднем менее 1,5 делений.


            1. dreesh
              00.00.0000 00:00
              #25240256
              -1

              В реальности есть очень много чисел в разложение которых будет входить 2 в некоторой степени. Так как после 3n+1 число всегда четное, а значит может содержать 2^x, то и делений выходит больше чем умножений. Формула вводит в заблуждение тем, что намекает на выражение 3 > 2, но не показывает 3<4 или 3<8. Нужно помнить, что у нас есть каждое 4-е число, каждое 8-е, каждое 16-е в счетном множестве которые обязательно встретяться с некоторой большой вероятностью. Мне лениво точно считать, но от 0 до 100 из всех четных будет 50% кратных 4, 25% кратных 16, 12.5% кратных 32.


    1. ksbes
      00.00.0000 00:00
      #25236324

      Не совсем любая степень двойки — на восьмёрку, например, можно попасть только если её выбрать первой, либо в процессе «спуска» с по степеням двойки.
      Потому что степени двойки чередуются: 3n+1, 3n-1 (если начинать с нулевой).

      Я как-то пытался искать доказательство в четверичной системе исчисления (где 3 обладает свойствами «девятки»). Но как-то закопался, как обычно.


  1. SeregaSA73
    00.00.0000 00:00
    #25236414
    +4

    По этой теме видео у Vert Dider интересное:

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


  1. TimsTims
    00.00.0000 00:00
    #25238812

    Интересно было бы увидеть графики для других значений тройки, например 7n+1.


    1. Tzimie Автор
      00.00.0000 00:00
      #25239694
      +2

      Будет runaway: после 3n+1 всегда идет деление на два, то есть (3n+1)/2 = примерно полтора. То есть увеличиваем в полтора раза, а делим на два, в среднем значения уменьшаются. Уже при 5n+1 это не так.


      1. TimsTims
        00.00.0000 00:00
        #25241402

        Точно, спасибо.


  1. BoltHold
    00.00.0000 00:00
    #25239684

    Я так понимаю это фракталы


  1. belch84
    00.00.0000 00:00
    #25239850
    +2

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

    Графики
    Оранжевый — график функции
    image,
    многократное последовательное применение которой (согласно гипотезе Коллатца) должно приводить к единице, зеленый — график функции из публикации

    image


    1. Tzimie Автор
      00.00.0000 00:00
      #25239926
      +2

      Ну да. Нули косинуса и синуса становятся 1 или 0, и играют роль 'IF'