Поделюсь интересными результатами анализа одной маленькой, но интересной теоремы, гипотезы Коллатца.

Формулировка такая: вам даётся натуральное число. Если оно чётное, вы его делите на два, а если нечётное, умножаете на три и добавляете единицу. И так по кругу. Гипотеза состоит в том, что для натуральных чисел иной судьбы, чем скатиться в цикл 1->4->2->1 нет. То есть, предположение состоит в том, что не появится других циклов — и тем более, таких чисел, которые при такой обработке в среднем всегда только возрастают.

Как бы на это посмотрел бы программист? Прежде всего, целое число для него это набор бит. Количество бит у числа приблизительно подсчитывается логарифмом по основанию 2, с округлением в большую сторону. Семь это три бита «111», восемь это уже четыре бита «1000». Двоичная система счисления — как будто у вас отобрали все цифры с 2 по 9, а числа обозначать надо. Сперва трудно, но привыкнуть можно.

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

https://habr.com/ru/post/685224/?utm_source=habrahabr&utm_medium=rss&utm_campaign=685224