Она же проблема 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
Фракталы
Я пытался на основе полученных данных построить графики, но ничего красивого не выходило. А вот фрактал получился потрясающий!
Строится он по следующей формуле:
![](https://habrastorage.org/getpro/habr/upload_files/aba/f31/842/abaf31842c7118c61de7abd485b7394a.png)
Обратите внимание, как хитро она составлена — при целых значениях z функция f(z) делает итерацию по известной формуле для простых чисел. Зато мы можем в качестве z использовать комплексное число, а adder (обведен красным) мы можем менять плавно и даже придавать ему некорректные значения (2, например).
Обычно фрактал «прижимается» к оси y=0 (вещественная ось, мнимые значения малы по модулю). Это происходит из‑за того, что для мнимых аргументов косинус превращается в гиперболический косинус (цепную линию), а тот убегает в бесконечность как экспонента.
![x [0, 20], y [-1.5. 1.5] x [0, 20], y [-1.5. 1.5]](https://habrastorage.org/getpro/habr/upload_files/807/7b8/44c/8077b844cfcb095af98bfd5688c97bd2.png)
Хочется увеличить нетривиальные зоны:
![x [0,2.5], y [-0.4, 0.4] x [0,2.5], y [-0.4, 0.4]](https://habrastorage.org/getpro/habr/upload_files/bcc/e7a/324/bcce7a3243ff991acc4cb219f7d5610e.png)
![x [1.8,2.09], y [0,0.2] x [1.8,2.09], y [0,0.2]](https://habrastorage.org/getpro/habr/upload_files/499/05c/96c/49905c96c33268f45ccad78926b32a5a.png)
Самое интересное происходит в этой области, когда 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](https://habrastorage.org/getpro/habr/upload_files/79e/6b8/59c/79e6b859c4c99a24710fefde19e84bf6.png)
Эту красоту в движении вы можете увидеть на видео. Напоследок замечу, что самое интересное происходит около adder=1, так что выбор единицы неслучаен.