Формула или закономерность для последовательности

Автор темы wolfram 
ОбъявленияПоследний пост
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
09.06.2020 10:24
Формула или закономерность для последовательности
Можно ли вычислить формулу/закон/закономерность, по которой распространяется последовательность?

Идея такая. Изначально есть цифра 1. Справа к ней приписывается тоже самое число (вначале это цифра), но в ней заменяются нули на единицы, единицы на нули. Получается - 1 -> 10 -> 1001 -> 10010110 -> 1001011001101001 ... И так далее. Требуется найти M-ную цифру. На самом деле, это задача по программированию, и решается она просто постоянным "приписыванием", почти реализуется само условие задачи. Но таким способом мы никогда не сможем посчитать 2^100-5-ную цифру, требуется зверский компьютер. А 2^1000-5-ную?
Вот, например, последовательность после 10-ти приписываний:

1001011001101001011010011001011001101001100101101001011001101001011010011001011010010110011010011001011001101001011010011001011001101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001011010011001011010010110011010011001011001101001011010011001011010010110011010010110100110010110011010011001011010010110011010011001011001101001011010011001011001101001100101101001011001101001011010011001011010010110011010011001011001101001011010011001011001101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001100101100110100101101001100101100110100110010110100101100110100101101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001011010011001011010010110011010011001011001101001011010011001011001101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

Можно заметить, что всё состоит из "блоков" 1001 и 0110. Разделим на пробелы:

1001 0110 0110 1001 0110 1001 1001 0110 0110 1001 1001 0110 1001 0110 0110 1001 0110 1001 1001 0110 1001 0110 0110 1001 1001 0110 0110 1001 0110 1001 1001 0110 0110 1001 1001 0110 1001 0110 0110 1001 1001 0110 0110 1001 0110 1001 1001 0110 1001 0110 0110 1001 0110 1001 1001 0110 0110 1001 1001 0110 1001 0110 0110 1001 0110 1001 1001 0110 1001 0110 0110 1001 1001 0110 0110 1001 0110 1001 1001 0110 1001 0110 0110 1001 0110 1001 1001 0110 0110 1001 1001 0110 1001 0110 0110 1001 1001 0110 0110 1001 0110 1001 1001 0110 0110 1001 1001 0110 1001 0110 0110 1001 0110 1001 1001 0110 1001 0110 0110 1001 1001 0110 0110 1001 0110 1001 1001 0110 0110 1001 1001 0110 1001 0110 0110 1001 1001 0110 0110 1001 0110 1001 1001 0110 1001 0110 0110 1001 0110 1001 1001 0110 0110 1001 1001 0110 1001 0110 0110 1001 1001 0110 0110 1001 0110 1001 1001 0110 0110 1001 1001 0110 1001 0110 0110 1001 0110 1001 1001 0110 1001 0110 0110 1001 1001 0110 0110 1001 0110 1001 1001 0110 1001 0110 0110 1001 0110 1001 1001 0110 0110 1001 1001 0110 1001 0110 0110 1001 0110 1001 1001 0110 1001 0110 0110 1001 1001 0110 0110 1001 0110 1001 1001 0110 0110 1001 1001 0110 1001 0110 0110 1001 1001 0110 0110 1001 0110 1001 1001 0110 1001 0110 0110 1001 0110 1001 1001 0110 0110 1001 1001 0110 1001 0110 0110 1001

Я пытался найти то, как с каждым разом получаются всё новые такие блоки, но потом заметил: если заменить 1001 на 1, а 0110 на 0, то у нас получится таже самая последовательность, только после 8-мого приписывания. Если мы опять поделим всё на блоки и сделаем замену, то в конце просто придём ко второму приписыванию - 10. Таким образом, это ничего не даёт, потому что всё сводится к поиску закономерности исходной последовательности. Теоретически, можно сделать программу, основывающуюся на этом и "выбирать" только определённые части последовательности, предварительно посчитав необходимое количество приписываний (по степеням двойки) и посчитав в какой части находится необходимая M-ная цифра, но это не сильно облегчит задачу.

Также можно разбить последовательность по одному или два идущих подряд символа: 1 00 1 0 11 00 11 0 1 00 1, и вместо 0 или 1 писать 1, а вместо 00 или 11 писать 2. Тогда: 1 2 1 1 2 2 2 1 1 2 1. В такой последовательности с каждым новым приписыванием появляется новый уникальный элемент, (я раскрасил в ворде эту последовательность, элемент "2 2 2" одним цветом, и т. д.), и ничего вновь не получилось. Однако если найти "закон", по которому будет известно, 2-ка или единица на каком-то месте (в последовательности 121....), также можно будет решить задачу.

Кстати, в последовательности 121.... было три основных "блока" - "короткий", "длинный", и три двойки. "Короткие" и "длинные" находятся между "двойками". Так вот если выбросить "двойки", представить "короткий" за 1, "длинный" за 2, то такие "блоки" повторяют последовательность 121.... .

Я учусь в 10том классе, ни с чем подобным, разумеется, не знаком. Я не могу проверить возможно ли найти такую "закономерность", потому что последовательность простых чисел тоже можно описать словами, а математически никак нельзя, как, например, прогрессию. Или вдруг вы придумаете какое-нибудь другое решение - буду рад. Скорей всего "закон распространения" этих нулей и единиц найти нельзя. Скажите, что это не так.



Редактировалось 1 раз(а). Последний 09.06.2020 23:38.
09.06.2020 17:03
//
Цитата
wolfram
Скорей всего "закон распространения" этих нулей и единиц найти нельзя. Скажите, что это не так.

А для чего искать закон, даже если он есть? Таких "задач" можно понапридумывать великое множество и гораздо поинтереснее (см. числа - градины). Только вот пытались как-нибудь "приткнуть" эти, не помню как называются (типа, "регрессионные" что ли) задачи к криптографии, но ничего не вышло и доказано, что не выйдет. Сомневаюсь, что более они кому-либо интересны. В гипотезе Коллатца хоть народ интересует "а есть ли такое число?", и они там для энтузиазма распределенные вычисления замутили..smile
Тут же - никакого "интересного" результата не предвидится. Даже если найдется какая-то формула.
09.06.2020 23:40
Доходчиво
Доходчиво, однако. Спасибо за ответ! Просто загорелся такой идеей. Как вы поняли, потратил какое-то время на неё, появился свой спортивный интерес. Тогда придётся смириться)
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти