2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Жалкое подобие последовательности Колатца :)
Сообщение15.01.2006, 12:25 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Эта задачка (впрочем несложная даже для школьников) не должна быть широко известной в узких кругах. Придумал я её лет 10 или более назад и практически никому не показывал.
Преамбула для тех, кто не в курсе.
Есть очень известная проблема под названием 3х+1:
Пусть n - натуральное. Если оно чётное, то положим T(n)=n/2, иначе T(n)=3n+1. Предположение Колатца (Collatz), высказанное им в 1928 г. состоит в том, что стартуя с произвольного n, итерационная последовательность n, T(n), T(T(n)),... завершится циклом (1,4,2).
Рассказывают, что сам Колатц любил демонстрировать эту проблему таким образом:
- Возьмём для иллюстрации не очень большое число, гм, ну, скажем, 27...
Первоначально Колатц предлагал 100 $ из своего кармана за решение. Контрпример оценивал дешевле - баксов в 20.

Аналогично, можно поставить вопрос для 3х-1 или, что то же самое для 3х+1 в отрицательной части Z. Здесь всяк легко найдёт циклы с их образующими 5 и 17. На этом известные достижения заканчиваются.

По простоте формулировки эта проблема может соперничать с проблемой Ферма и уже множится армия дилетантов, бьющихся над её решением.

Итак,
Жалкое подобие последовательности 3х+1:
На множестве натуральных чисел определим отображение t следующим образом: в числе 3n+1 выделяем максимальный делитель, являющийся степенью двойки. Прибавив этот делитель к n, получим t(n). Стартовав с произвольного натурального n можем организовать последовательность: n, t(n), t(t(n)), ...
Пример: 94 95 97 101 117 149 213 341 ...

Описать поведение этой последовательности. Я намеренно даю формулировку в такой форме. Сформулировать, что именно нужно доказывать - это начальный этап задачи.

Аналогично организуется жалкое подобие последовательности 3х-1 с тем же вопросом.

ЗЫ. Возможно я и ошибаюсь в оценке простоты задачки - уже неделю безответно (если не считать зашифрованного ответа от преподавателя) на двух форумах висит, впрочем малолюдных в виду сессии.

 Профиль  
                  
 
 фигня по сравнению с задачей Колатца
Сообщение16.01.2006, 19:13 


04/10/05
272
ВМиК МГУ
Ну некоторое описание дать можно. Опишем функцию t(n). Будем записывать двоичные записи начиная с младших разрядов к старшим (то есть не как обычно, а наоборот). Пусть k - максимальное число такое, что k младших разрядов числа n образуют последовательность 10101010.... . И пусть n=AB, где A-k младших разрядов n, а B-все остальные. Тогда t(n)=A(B+1). Здесь B+1 - это двоичная запись числа (1+число, двоичная запись которого есть B). То есть начиная с k-ого разряда находится последовательность вида 11...110 (возможно, количество единиц равно нулю) и заменяется на 00...001. Это и будет t(n). Все это доказывается простейшими теоретико-числовыми рассуждениями (даже выписывать неохота). Можно заметить, что значение k от члена к члену строго возрастает и начиная с некоторого номера наступит некоторая стабилизация, то есть каждый следующий член будет отличаться от предыдущего добавленной единицей на месте старшего разряда + 2.

И еще. Пусть последовательность есть t_0,t_1,\ldots,\quad t_{n+1}=t_n+2^{k_n}, тогда k_n монотонно возрастает и множество значений, которые она принимает можно описать с помощью конечного автомата с 4 состояниями, которому на вход подается двоичная запись t_0 начиная с младшего разряда. Если нужно, могу выписать.

 Профиль  
                  
 
 
Сообщение16.01.2006, 19:56 


04/10/05
272
ВМиК МГУ
А автомат такой (пока не забыл).
У него 4 состояния: A00, A01, A10, A11.
Переходы при подаче 0:
A00->A10, выдать
A01->A10
A10->A00
A11->A01, выдать
Переходы при подаче 1:
A00->A10
A01->A11, выдать
A10->A01, выдать
A11->A01
Инициальное состояние - A00.
Если при подаче k-ой цифры автомат сказал "выдать", то k принадлежит множеству значений последовательности k_n.
Можно отметить, что этот автомат минимальный.

 Профиль  
                  
 
 Не фигня, а мегафигня
Сообщение17.01.2006, 08:16 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Можно ещё и так сказать, что начиная с некоторого номера (который легко вычисляется) эта жалкая последовательность является хвостом последовательности

1, 11, 111, 1111, ... :D

Некоторое сходство всё же есть - отсюда и название. Подправим T(n) в определении последовательности Колатца (m - нечётное):

$ T(2^k m)=2^k(3m+1)$

Тогда предположение Колатца состоит в том, что стартующая с любого n итерационная последовательность является хвостом одной из двух последовательностей

1, 10, 100, 1000, 10000, ...
2, 20, 200, 2000, 20000, ...

 Профиль  
                  
 
 
Сообщение17.01.2006, 08:59 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Жалкое подобие последовательности 3 х+1 быстро сходиться к $\frac{2^{2n}-1}{3}$;
жалкое подобие последовательности 3 х-1 быстро сходиться к $\frac{2^{2 n -1}+1}{3}$.
"Быстро" в данном случае означает не медленее чем ${\rm O}(\log_2 x)$.
Вероятно, это тоже самое утверждение, что и bot'а.

 Профиль  
                  
 
 
Сообщение17.01.2006, 09:12 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Ну ещё могу добавить, что можно вычислить точный номер стабилизации - точнее написать реккуррентную формулу. Двоичная запись числа представляется как чередование частоколов из единичек и дырок из нулей. Самый старший забор отщепляем и в зависимости от величины дыры до следующего по старшинству забора и чётности оставшихся символов получим реккуррентную формулу. Вот только проще ли это будет, чем сам алгоритм? Да и формула - это тоже алгоритм.
Так что это не та задача, которой стоит заниматься.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group