Когда впервые придумали задачу "for(;;) x%2? x=x*3+1 : x/=2; //почему в итоге всегда x=1?", работа матфака какого-то университета (кроме положенной по расписанию) была реально парализована на месяц - все искали решение этой "ну очень же простой" задачи. Задача не решена до сих пор...
Если в 0 не попадём. 0 - неподвижная точка, с него можно стартовать, а при 16-разрядной unsigned сетке, например, 21845 перейдёт в 0.
А про эквивалентное сопротивление я комикс постил у себя как-то, и там были ссылки на решения. Но из-за гондонов из яндекс, которые убили поиск по блогам, и придурков из гугля, которые просто неспособны в моём блоге ничего найти почему-то, я не могу дать ссылку.
Да, спасибо, я про неположительные числа как-то не подумал :)
Поэтому строгая формулировка задачи должна звучать так: 1. Берется некоторое натуральное число Х. 2. Если Х - нечетное, оно заменяется на 3Х+1; если же Х четное, оно заменяется на Х/2. 3. Если Х>1, то возвращаемся к пункту 2. Доказать либо опровергнуть, что, независимо от выбора начального значения Х, рано или поздно алгоритм завершится (разрядность Х считается неограниченной).
Задача не решена до сих пор, хотя прошли десятилетия. Компьютерные эксперименты показывают, что рано или поздно Х всегда достигает единицы. Доказательства нет. Некоторые математики на основе теоремы Гёделя всерьез подозревают, что задача может быть неразрешимой в принципе - то есть, для любого Х рано или поздно получится 1, однако это невозможно вывести логическими преобразованиями из аксиом арифметики...
Для неограниченной разрядности сложнее, да. Отрезание младших нулей в двоичной записи - операция простая и приятная, осталось только доказать, что операция 3х+1 с этим самым отрезанием приведёт в конце концов к степени двойки.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2015-09-19 03:13 pm (UTC)Да, так какое там эквивалентное сопротивление? :D
no subject
Date: 2015-09-21 12:43 pm (UTC)А про эквивалентное сопротивление я комикс постил у себя как-то, и там были ссылки на решения. Но из-за гондонов из яндекс, которые убили поиск по блогам, и придурков из гугля, которые просто неспособны в моём блоге ничего найти почему-то, я не могу дать ссылку.
no subject
Date: 2015-09-21 06:18 pm (UTC)no subject
Date: 2015-09-21 01:15 pm (UTC)Потому что там / , а не >>>
:)
no subject
Date: 2015-09-21 06:17 pm (UTC)Поэтому строгая формулировка задачи должна звучать так:
1. Берется некоторое натуральное число Х.
2. Если Х - нечетное, оно заменяется на 3Х+1; если же Х четное, оно заменяется на Х/2.
3. Если Х>1, то возвращаемся к пункту 2.
Доказать либо опровергнуть, что, независимо от выбора начального значения Х, рано или поздно алгоритм завершится (разрядность Х считается неограниченной).
Задача не решена до сих пор, хотя прошли десятилетия. Компьютерные эксперименты показывают, что рано или поздно Х всегда достигает единицы. Доказательства нет.
Некоторые математики на основе теоремы Гёделя всерьез подозревают, что задача может быть неразрешимой в принципе - то есть, для любого Х рано или поздно получится 1, однако это невозможно вывести логическими преобразованиями из аксиом арифметики...
no subject
Date: 2015-09-22 06:33 am (UTC)