2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задача 3n+1
Сообщение16.10.2007, 21:54 
Рассмотрим следующий алгоритм генерации последовательности чисел. Начнем с целого числа 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.

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

 
 
 
 
Сообщение17.10.2007, 02:11 
Аватара пользователя
Это последовательность Коллатца (Collatz). В Вашей формулировке её любат давать как задачу по программированию. 8-)

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

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

 
 
 
 Re: Задача 3n+1
Сообщение20.10.2007, 10:40 
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.
(Изменения происходят от того, что кто-то в какой-то момент как-бы забывает взять остаток :D :D :D )
В случае справедливости моего предположения можно утверждать, что гарантированно придем к 1.

 
 
 
 Re: Задача 3n+1
Сообщение20.10.2007, 11:11 
Аватара пользователя
Батороев писал(а):
Рискну предположить, что указанный ряд - это несколько измененный и перевернутый ряд остатков степеней числа 2 по основанию 27.
(Изменения происходят от того, что кто-то в какой-то момент как-бы забывает взять остаток :D :D :D )
В случае справедливости моего предположения можно утверждать, что гарантированно придем к 1.
А перевернутый оттого, что кто-то забывает сделать что? :D

 
 
 
 Re: Задача 3n+1
Сообщение20.10.2007, 11:46 
TOTAL писал(а):
А перевернутый оттого, что кто-то забывает сделать что? :D

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

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

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

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

 
 
 
 
Сообщение25.04.2008, 14:06 
Аватара пользователя
 !  PAV:
Господа, обращаю внимание, что автор темы не спрашивал про решение математической задачи, а только лишь про учебную задачу по программированию. Тема переезжает в соответствующий раздел, а обсуждение данной гипотезы, а также ее обобщений прошу в этой теме прекратить.

 
 
 
 
Сообщение25.04.2008, 23:17 
bot писал(а):
Программу, конечно, надо писать для чисел в двоичной системе - в ней очень легко переходить от n к 3n+1 - это чисто логическая операция, а стало быть и самая быстрая,

Это какую такую операцию Вы имели ввиду? Сильно сомневаюсь, что это будет быстрее чем
Код:
lea eax,[eax*2+eax+1]

 
 
 
 
Сообщение27.04.2008, 13:42 
ScarAngel писал(а):
bot писал(а):
Программу, конечно, надо писать для чисел в двоичной системе - в ней очень легко переходить от n к 3n+1 - это чисто логическая операция, а стало быть и самая быстрая,

Это какую такую операцию Вы имели ввиду? Сильно сомневаюсь, что это будет быстрее чем
Код:
lea eax,[eax*2+eax+1]

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

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

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

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group