НГУ

Форумы НГУ
Текущее время: Пт фев 23, 2018 7:18 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 14 ] 
Автор Сообщение
СообщениеДобавлено: Пн янв 09, 2006 7:31 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
Есть очень известная проблема под названием 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 $ из своего кармана за решение. Контрпример он оценивал дешевле.

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

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

Наша задача (придумал её давно - более 10 лет назад, а сейчас вдруг вспомнил) будет значительно скромнее и даже доступна тем, кто уже начал успешно заваливать текущую сессию. Будем надеяться, что её решение даст таким повод поддержать их пошатнувшуюся веру в свои силы и поможет довести сессию до победного конца.

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

Пример: 40, 41, 45, 53, 85, ...

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

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

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 12, 2006 5:17 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб янв 07, 2006 3:05 am
Сообщения: 1041
Откуда: ага
n t(n) t(t(n)) t(t(t(n))) .....
1 5 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
2 3 5 21 85 341 1365 5461 21845 87381 349525 1398101 5592405
3 5 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
4 5 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
5 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
6 7 9 13 21 85 341 1365 5461 21845 87381 349525 1398101
7 9 13 21 85 341 1365 5461 21845 87381 349525 1398101 5592405
8 9 13 21 85 341 1365 5461 21845 87381 349525 1398101 5592405
9 13 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
10 11 13 21 85 341 1365 5461 21845 87381 349525 1398101 5592405
11 13 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
12 13 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
13 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
14 15 17 21 85 341 1365 5461 21845 87381 349525 1398101 5592405
15 17 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
16 17 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
17 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
18 19 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
19 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
20 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485 357913941
22 23 25 29 37 53 85 341 1365 5461 21845 87381 349525
23 25 29 37 53 85 341 1365 5461 21845 87381 349525 1398101
24 25 29 37 53 85 341 1365 5461 21845 87381 349525 1398101
25 29 37 53 85 341 1365 5461 21845 87381 349525 1398101 5592405
26 27 29 37 53 85 341 1365 5461 21845 87381 349525 1398101
27 29 37 53 85 341 1365 5461 21845 87381 349525 1398101 5592405
28 29 37 53 85 341 1365 5461 21845 87381 349525 1398101 5592405
29 37 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
30 31 33 37 53 85 341 1365 5461 21845 87381 349525 1398101
31 33 37 53 85 341 1365 5461 21845 87381 349525 1398101 5592405
32 33 37 53 85 341 1365 5461 21845 87381 349525 1398101 5592405
33 37 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
34 35 37 53 85 341 1365 5461 21845 87381 349525 1398101 5592405
35 37 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
36 37 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
37 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
38 39 41 45 53 85 341 1365 5461 21845 87381 349525 1398101
39 41 45 53 85 341 1365 5461 21845 87381 349525 1398101 5592405
40 41 45 53 85 341 1365 5461 21845 87381 349525 1398101 5592405
41 45 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
42 43 45 53 85 341 1365 5461 21845 87381 349525 1398101 5592405
43 45 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
44 45 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
45 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
46 47 49 53 85 341 1365 5461 21845 87381 349525 1398101 5592405
47 49 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
48 49 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
49 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
50 51 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
51 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
52 53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
53 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485 357913941
54 55 57 61 69 85 341 1365 5461 21845 87381 349525 1398101
55 57 61 69 85 341 1365 5461 21845 87381 349525 1398101 5592405
56 57 61 69 85 341 1365 5461 21845 87381 349525 1398101 5592405
57 61 69 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
58 59 61 69 85 341 1365 5461 21845 87381 349525 1398101 5592405
59 61 69 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
60 61 69 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
61 69 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
62 63 65 69 85 341 1365 5461 21845 87381 349525 1398101 5592405
63 65 69 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
64 65 69 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
65 69 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
66 67 69 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
67 69 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
68 69 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
69 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485 357913941
70 71 73 77 85 341 1365 5461 21845 87381 349525 1398101 5592405
71 73 77 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
72 73 77 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
73 77 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
74 75 77 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
75 77 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
76 77 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
77 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485 357913941
78 79 81 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
79 81 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
80 81 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
81 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485 357913941
82 83 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485
83 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485 357913941
84 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485 357913941
85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621 89478485 357913941 1431655765
86 87 89 93 101 117 149 213 341 1365 5461 21845 87381
87 89 93 101 117 149 213 341 1365 5461 21845 87381 349525
88 89 93 101 117 149 213 341 1365 5461 21845 87381 349525
89 93 101 117 149 213 341 1365 5461 21845 87381 349525 1398101
90 91 93 101 117 149 213 341 1365 5461 21845 87381 349525
91 93 101 117 149 213 341 1365 5461 21845 87381 349525 1398101
92 93 101 117 149 213 341 1365 5461 21845 87381 349525 1398101
93 101 117 149 213 341 1365 5461 21845 87381 349525 1398101 5592405
94 95 97 101 117 149 213 341 1365 5461 21845 87381 349525
95 97 101 117 149 213 341 1365 5461 21845 87381 349525 1398101
96 97 101 117 149 213 341 1365 5461 21845 87381 349525 1398101
97 101 117 149 213 341 1365 5461 21845 87381 349525 1398101 5592405
98 99 101 117 149 213 341 1365 5461 21845 87381 349525 1398101
99 101 117 149 213 341 1365 5461 21845 87381 349525 1398101 5592405

Все последовательности, начиная с какого-то элемента, входят в состав одной


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт янв 13, 2006 11:38 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
Николай Ш писал(а):
Все последовательности, начиная с какого-то элемента, входят в состав одной
В состав вот этой:
1, 11, 111, 1111, 11111, ...
Причем медленнее всего входят числа вида 1...12, например:
1112-->1113-->1121-->1131-->1211-->1311-->2111-->3111-->11111-->111111...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб янв 14, 2006 3:18 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб янв 07, 2006 3:05 am
Сообщения: 1041
Откуда: ага
Не понял.
12 13 21 85 341 1365 5461 21845 87381 349525 1398101 5592405 22369621
112 113 117 149 213 341 1365 5461 21845 87381 349525 1398101 5592405
1112 1113 1117 1125 1141 1173 1237 1365 5461 21845 87381 349525 1398101
11112 11113 11117 11125 11157 11221 11349 11605 13653 21845 87381 349525 1398101
111112 111113 111117 111125 111189 111445 111957 120149 152917 218453 349525 1398101 5592405
1111112 1111113 1111117 1111125 1111381 1119573 1135957 1398101 5592405 22369621 89478485 357913941 1431655765
11111112 11111113 11111117 11111125 11111253 11111765 11113813 11130197 11162965 11228501 11359573 11883861 13981013
111111112 111111113 111111117 111111125 111111253 111111509 111113557 111121749 111138133 111170901 111236437 111498581 112547157
1111111112 1111111113 1111111117 1111111125 1111111253 1111111509 1111112021 1111113045 1111115093 1111119189 1111184725 1111315797 1111840085


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс янв 15, 2006 1:29 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
И что? Такой богатый эмпирический материал ещё не навёл на размышления? :(
Впрочем, не лучше ли Вам на алгебру приналечь, чем хвастать своим забивательством на Land7 ?
Я ведь карт-бланш, данный мне деканатом, ещё не весь использовал. :)

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн янв 16, 2006 12:30 pm 
Не в сети
Редкий гость

Зарегистрирован: Вс янв 08, 2006 2:47 am
Сообщения: 12
Сам считал, или как?!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт янв 17, 2006 12:26 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб янв 07, 2006 3:05 am
Сообщения: 1041
Откуда: ага
Или как :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт янв 17, 2006 12:40 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
Подправим функцию T(n) в определении Колатца следующим образом (m - нечётное):

T(m*2^k) = (3m+1)*2^k. Тогда предположение Колатца состоит в том,

что его последовательность начиная с некоторого номера (в жалком подобии он легко вычисляется) совпадает с хвостом одной из двух последовательностей:

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

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт янв 17, 2006 1:26 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
bolbot писал(а):
Подправим функцию T(n) в определении Колатца следующим образом (m - нечётное):
T(m*2^k) = (3m+1)*2^k.

Здесь непонятно. Эта последовательность не является ни Колатца, ни жалким подобием. Из каждого следующего члена последовательности Колатца можно убирать сразу все степени двойки, поэтому все числа последовательности Колатца не делятся ни на 2, ни на 3 (за искл м.б. первого числа).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт янв 17, 2006 1:43 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
Гост_Я писал(а):
Из каждого следующего члена последовательности Колатца можно убирать сразу все степени двойки

Своё же не узнали? :)
Можно убирать, а можно и не убирать, а выносить. В этом случае последовательность Колатца монотонизируется.
Вот ещё вариант (m - нечётное): T(m*2^k) = (3m+1)*2^(k-1).
Тогда вторую из двух моих белых последовательностей можно убрать.

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт янв 17, 2006 3:11 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
bolbot писал(а):
Можно убирать, а можно и не убирать, а выносить. В этом случае последовательность Колатца монотонизируется.

Непонятно, так как если выносить, то степень двойки обязательно увеличивается.
Нельзя ли написать конкретную формулу, которой связаны T(n) и T(n+1) - два последоватьльных члена (модернизированной или еще какой) последовательности? Например для последовательности Колатца эта формула такая: 3*T(n)+1=T(n+1)*2^k, где k>0.
Число k равно длине участка, со стороны младших разрядов, на котором в двоичной записи число T(n) совпадает с числом ...0101010101. Например, если T(n)=111000110101, то k=5.
Да, числа ЖП последовательности быстро принимают вид ...0101010101, но что это дает для последовательности Колатца?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт янв 17, 2006 4:07 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
Последовательность Колатца для числа 9 такая:
9 -> 28 -> 14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.

Если сокращать одну двойку, а остальные выносить, то получится:

m*2^k - 1 -> m*3*2^(k-1) - 1 -> ... -> m*3^k - 1 =(m'*2^k' - 1)*2^s -> ...

Пример: 9=5*2-1 -> 5*3 - 1 = 2(8-1) -> ... -> 2(27-1) = 4(7*2 - 1) -> 4 (7*3 - 1) = 16(3*2-1) -> 16(9-1)=128(2 -1) -> 128(3-1) = ...

ЖП (на то она и Ж) для последовательности Колатца ничего не даёт.
В первой стабилизация очевидна, а во второй - проблема.

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт янв 17, 2006 5:09 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
Теперь понятно.
Замечено, что числа вида m*2^k-1=???11 растут закономерно до 2*m*3^(k-1)-1, а вот следующее число m*3^k-1 (из-за возможного сокращение на дополнительные двойки) может быть меньше предыдущего, закономерность разрушается.
Для практической оценки количества членов последовательности я начинал, например, с 2^100000-1 (сплошные единицы в двоичной записи). Число росло в течении первых 100000-1 шагов до прибл. 2^160000, затем (немонотонно) уменьшалось до 1 за прибл. 500000 шагов (сокращения на степени двоек за шаги не считались).
Интересно, существует ли доказательство невозможности циклического поведения последовательности?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 18, 2006 10:39 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
Гост_Я писал(а):
Интересно, существует ли доказательство невозможности циклического поведения последовательности?

За исключением тривиального, разумеется. Если я только не пропустил, то и этого нет.

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

_________________
Наука умеет много гитик.


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

Часовой пояс: UTC + 7 часов


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

Сейчас этот форум просматривают: Bing [Bot] и гости: 14


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

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB