Comments 36
Она же проблема 3n+1. Это, наверное, самая сложная проблема с самой простой формулировкой - условие может понять и ребенок.
В статье есть формулировка этой проблемы?
https://en.wikipedia.org/wiki/Collatz_conjecture
Я думал она общеизвестна
хабр еще не готов к формулировке проблем такой сложности
Не, нету. Объясняю: есть функция
step(uint n) -> uint
{
if ( n % 2 == 0 ) return n / 2;
return 3*n + 1;
}
Доказать, что цикл while (n != 1) step(n) при любом исходном n > 0 всегда выйдет.
Да, всего то проблема останова)
Ну как вариант можно дать ссылку на другую статью на Хабре про эту гипотезу https://habr.com/ru/post/675594/ (свеженькая, но без красивых картинок).
n = step(n)
Употреблять иностранное слово, когда есть равносильное ему русское слово, - значит оскорблять и здравый смысл, и здравый вкус.
Что русский язык — один из богатейших языков в мире, в этом нет никакого сомнения.
(с) Белинский В.Г.
Гипотеза на русском:
https://ru.wikipedia.org/wiki/Гипотеза_Коллатца
Обожаю последовательность (не в математическом смысле, а в чужом глазу).
Дано: f(n,a,b). Для начала объясним, почему не будем брать "а" четным. Объяснили? А теперь погнали экспериментировать!
Вопрос с задних рядов: профессор, а почему мы берем именно b=3? Потому что другие значения в каком-то смысле эквивалентны такому выбору, и этому есть простое и красивое доказетльство? Или просто "потому что потому!"?
Или вот другая последовательность: "статья про игру жизнь", "статья про игру жизнь", "статья про игру жизнь", "статья, в которой затрагивается вопрос варьирования параметров в..."
Читатель уж ждет рифму "в алгоритме игры жизнь!" - но нет, сиракузы.
Ну это же издевательство! Так и не узнаю: почему в игре жинь выбран именно такой алгоритм, и что будет, если его менять? А еще интереснее, изменить число измерений, хотя бы рассмотреть случай трех осей? Или, совсем уж на десерт: а если в правила ввести элемент случайности (аналог квантовости в реальном мире), как будут выглядеть (псевдо?)вечные образования?
Но нет. Доктор сказал, что сиракузы интереснее - значит, сиракузы интереснее.
Вариантов варьирования столь много, что каждому открыта дорога попробовать свое. Вы же не ожидали что я смогу охватить все?
Так не в варьировании как таковом дело - а в интересности. С другими правилами игра жизнь лучше (интереснее, богаче), или хуже? Если хуже, то чем выбранные правила такие особенные? Если лучше, то почему продолжают считать по традиционным правилам?
У меня просто в голове не укладывается, как можно играть, потом немножко исследовать игру, программировать что-то для этого, писать несколько статей по теме - и не заинтересоваться этим вопросом.
http://shcoding.ru/cryptozoe/
Я попробовал добавить элемент случайности и ещё немножко вещей.. Из полученного опыта могу сказать, что правила игры жизнь тем и хороши, что они максимально просты, но это не точно.
Цикл заканчивается, когда значение попадает на число, являющееся степенью двойки. Но в приведенных примерах увидел, что оно всегда равно 16. Получается, что ежели 3н+1 будет степенью двойки, то это последний цикл. Дальше можно думать до бесконечности, но лениво.
С любым делителем будет 100% вероятность найти его степень, так как их число бесконечно. Задача сама по себе не корректна.
Вернемся к оригинальной задаче :) Любое не четное станет четным после применения формулы 3n+1, а значит следующий шаг будет деление на 2. В задаче изначально заложен дисбаланс между умножением и делением (делить мы будем каждый раз после умножения, а в некоторых случаях и по несколько раз), если записывать все шаги то делений всегда больше. Но все примеры показывают только не четные числа тем самым вводя в заблуждение легкостью решения.
В реальности есть очень много чисел в разложение которых будет входить 2 в некоторой степени. Так как после 3n+1 число всегда четное, а значит может содержать 2^x, то и делений выходит больше чем умножений. Формула вводит в заблуждение тем, что намекает на выражение 3 > 2, но не показывает 3<4 или 3<8. Нужно помнить, что у нас есть каждое 4-е число, каждое 8-е, каждое 16-е в счетном множестве которые обязательно встретяться с некоторой большой вероятностью. Мне лениво точно считать, но от 0 до 100 из всех четных будет 50% кратных 4, 25% кратных 16, 12.5% кратных 32.
Потому что степени двойки чередуются: 3n+1, 3n-1 (если начинать с нулевой).
Я как-то пытался искать доказательство в четверичной системе исчисления (где 3 обладает свойствами «девятки»). Но как-то закопался, как обычно.
По этой теме видео у Vert Dider интересное:
Интересно было бы увидеть графики для других значений тройки, например 7n+1.
Я так понимаю это фракталы
,многократное последовательное применение которой (согласно гипотезе Коллатца) должно приводить к единице, зеленый — график функции из публикации
Замахнемся на гипотезу Коллаца