Замахнемся на гипотезу Коллаца

Она же проблема 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 (вещественная ось, мнимые значения малы по модулю). Это происходит из‑за того, что для мнимых аргументов косинус превращается в гиперболический косинус (цепную линию), а тот убегает в бесконечность как экспонента.

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

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

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