Math
Гипотеза Коллатца
Чётное — пополам, нечётное — утроить и прибавить единицу. Всегда ли положительное целое придёт к единице? Исследуйте полёт числа, времена остановки до 4096 и отличия правил 3n − 1 и 5n + 1. Общее утверждение для 3n + 1 остаётся гипотезой.
Что происходит
Одно правило: чётное число раздели пополам, нечётное утрой и прибавь единицу, и повторяй. Каждый старт, который кто-либо пробовал, падает к единице — 27 взбирается до 9232 к 77-му шагу и приземляется на 111-м, — и никто не доказал, что падает каждый. Сцена полёта рисует путь одного числа шаг за шагом в логарифмическом масштабе: светящаяся голова взбирается на нечётных шагах (оранжевые) и падает на делениях пополам (золотые), а два соседа идут призраками: 26 приземляется за десять шагов, 28 за восемнадцать, 27 за сто одиннадцать. Сцена ландшафта раскладывает полное время остановки каждого числа до 4096 рельефом светящихся столбиков: рекордсмены — каждому нужно больше шагов, чем любому меньшему старту, — подсвечены красным, последний из них 3711 с 237 шагами; клик по столбику читает его. Среднее 75, самое частое время остановки 43, а подгонка по ln n идёт с наклоном 11 и отрицательным свободным членом, выше асимптотической эвристики 2/ln(4/3) = 6.95: в среднем нечётный шаг умножает на 3/2, и за ним обязательно идёт деление пополам, так что пара стоит множителя 3/4 — дрейф вниз, и это вся причина, по которой в гипотезу верят, и ничуть не доказательство. Сцена правил меняет константу: по шестьдесят полётов, окрашенных по судьбе. 3n + 1 отправляет домой всю первую тысячу стартов. У 3n − 1 два лишних цикла, через 5 и через 17, и 651 из первой тысячи кончает в одном из них. У 5n + 1 дрейф 5/4 вверх: 833 из первой тысячи вылетают за 2^60, за верхний край графика, и одна семёрка тратит на это 719 шагов.
Уравнения модуля
Уравнения правило: n → n/2 (n чётно), n → 3n + 1 (n нечётно); полное время остановки = число шагов до 1; 27: 111 шагов, пик 9232 на шаге 77, 41 нечётный шаг и 70 делений пополам; 26: 10 шагов, 28: 18, 97: 118 (снова пик 9232), 871: 178 (пик 190996) дрейф: нечётный шаг даёт 3n + 1 ≈ 3n/2 после неизбежного следующего деления пополам, поэтому пара из нечётного и следующего за ним чётного шага в среднем стоит множителя 3/4, а траектория с k нечётными шагами требует более k·log₂3 = 1.585 k делений пополам, чтобы спуститься; 3^41 / 2^70 = 0.031 < 1/27, как и должно быть, чтобы приземлиться на 1 ландшафт до 4096: рекордсмены (каждому нужно больше шагов, чем любому меньшему старту): 1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711 (237 шагов); среднее 75.13; самое частое время остановки 43 (87 стартов); метод наименьших квадратов: время остановки ≈ 11.12 ln n − 6.22 на 2 … 4096; эвристический (асимптотический) наклон 2/ln(4/3) = 6.95 3n − 1: первая тысяча стартов: 349 приходят в 1, 651 - в цикл через 5 (5 → 14 → 7 → 20 → 10 → 5, 306 стартов) или через 17 (18 членов, 345 стартов); наивысший пик среди приземлившихся: 132860 5n + 1: дрейф 5/4 > 1; первая тысяча стартов: 81 приходят в 1, 86 - в цикл через 13 (63) или 17 (23), а 833 превышают 2^60; одному только 7 нужно 719 шагов, чтобы превысить 2^60; наивысший пик среди приземлившихся: 1170496
