Задача 3n+1

[InSidEr]

Рассмотрим следующий алгоритм генерации последовательности чисел. Начнем с целого числа n.Если n четно, то поделим на 2.Если n нечетно, то умножим на 3 и добавим 1.Будем повторять этот процесс с новыми полученным n, пока n не станет равным 1. Например, для n = 22 будет сгенерирована след. посл. чисел :
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Докажите, что алгоритм сведется к n = 1 для целых чисел до 1 000 000.

[Руст]

Это уже обсуждалось здесь. Сейчас оно проверено примерно до $n=2^{64}.$

[нг]

Это последовательность Коллатца (Collatz). В Вашей формулировке её любат давать как задачу по программированию.

[InSidEr]

Есть такое дело... Мне ее тоже дали как задачу по программированию, просто хотел узнать кто-то может знает как доказать это, или есть ссылка на док-во...

[bot]

Вам уже сказали, что доказательства гипотезы Колатца нет, следовательно и ссылки на доказательство быть не может. В своё время сам проверил где-то до $2^{30} - 2^{32}$ - дальше комп не потянул, впрочем целью проверки была не совсем сама проверка.
Что до $2^{64}$ проверили - вполне доверяю.
Программу, конечно, надо писать для чисел в двоичной системе - в ней очень легко переходить от n к 3n+1 - это чисто логическая операция, а стало быть и самая быстрая, а делить на 2 ещё легче, ясен пень надо сразу на наивысшую возможную степень двойки - сдвинул и готово.
Так как $1 000 000 < 2^{18} << 2^{30}$, то моя программа справилась бы с этим делом за пару минут.

[Батороев]

InSidEr писал(а):

Рассмотрим следующий алгоритм генерации последовательности чисел. Начнем с целого числа n.Если n четно, то поделим на 2.Если n нечетно, то умножим на 3 и добавим 1.Будем повторять этот процесс с новыми полученным n, пока n не станет равным 1. Например, для n = 22 будет сгенерирована след. посл. чисел :
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Рискну предположить, что указанный ряд - это несколько измененный и перевернутый ряд остатков степеней числа 2 по основанию 27.
(Изменения происходят от того, что кто-то в какой-то момент как-бы забывает взять остаток )
В случае справедливости моего предположения можно утверждать, что гарантированно придем к 1.

[TOTAL]

Батороев писал(а):

Рискну предположить, что указанный ряд - это несколько измененный и перевернутый ряд остатков степеней числа 2 по основанию 27.
(Изменения происходят от того, что кто-то в какой-то момент как-бы забывает взять остаток )
В случае справедливости моего предположения можно утверждать, что гарантированно придем к 1.

А перевернутый оттого, что кто-то забывает сделать что?

[Батороев]

TOTAL писал(а):

А перевернутый оттого, что кто-то забывает сделать что?

А он, этот кто-то - житель антимира и для него 2 =14.

[Sonic86]

Добавлю для смеха немного кустарных соображений :
Можно задачу обобщить на отображения вида $n-->n/d$ и $n-->an+b$. Тогда для целочисленности необходимо $d=2, b=1 or b=-1$. В случае $3n-1$ и, кажется, $5n+1$ есть цикл. В остальных случаях эмпирически видно, что есть последовательности, стремящиеся к бесконечности. Возможно, это даже легко доказать.(?)

[bot]

Задача 3n-1 это та же 3n+1, только для отрицательных чисел. Все известные циклы на настоящий момент, указываю только образующие:
-17, -5, -1, 0, 1.

Sonic86 писал(а):

Можно задачу обобщить

Не вижу никакого смысла в обобщении ради обобщения. Была бы плодотворная идея, позволяющая из этого обобщения извлечь пользу для самой задачи - другое дело.
Приведу пример плодотворного обобщения. Нужно взять определённый интеграл, а в подинтегральной функции есть циферка 5. Берём и обобщаем - заменяем 5 на $\alpha$, получаем интеграл, зависящий от параметра. Дифференцируем по параметру (проверив возможность такого действия) и получаем легко берущийся интеграл, берём его, интегрируем полученное по параметру, находим константу интегрирования и наконец подставляем в результат $\alpha = 5$

[PAV]

PAV:

Господа, обращаю внимание, что автор темы не спрашивал про решение математической задачи, а только лишь про учебную задачу по программированию. Тема переезжает в соответствующий раздел, а обсуждение данной гипотезы, а также ее обобщений прошу в этой теме прекратить.

[ScarAngel]

bot писал(а):

Программу, конечно, надо писать для чисел в двоичной системе - в ней очень легко переходить от n к 3n+1 - это чисто логическая операция, а стало быть и самая быстрая,

Это какую такую операцию Вы имели ввиду? Сильно сомневаюсь, что это будет быстрее чем

lea eax,[eax*2+eax+1]

[abc_qmost]

ScarAngel писал(а):

bot писал(а):

Программу, конечно, надо писать для чисел в двоичной системе - в ней очень легко переходить от n к 3n+1 - это чисто логическая операция, а стало быть и самая быстрая,

Это какую такую операцию Вы имели ввиду? Сильно сомневаюсь, что это будет быстрее чем

lea eax,[eax*2+eax+1]

Т.к. в общем случае задействованы значения $n>2^{32}$, то лучше всего работать под EM64T.

[Pyphagor]

Белка сидит на бесконечной лестнице, ступеньки которой занумерованы натуральным рядом.
После, она начинает прыгать по правилу:если она сидит на четной ступеньке $n$ то перескакивает на ступеньку $\frac{n}{2}$, если же она сидит на нечетной ступеньке $n$, то перескакивает на ступеньку $3n+1$. Доказать, что где бы ни находилась белка вначале, через конечное число прыжков она окажется на первой ступеньке.

[maxal]

Pyphagor
Это открытая проблема известная как Гипотеза Коллаца (или "проблема 3x+1"). У нас на форуме было несколько обсуждений этой гипотезы и смежных вопросов, включая данную тему (куда я перенес ваше сообщение) и http://dxdy.ru/topic1186.html