Последовательность нулей и единиц строится по такому закону: сначала пишется 0, затем к написанной последовательности приписывается та же последовательность с заменой 0 на 1 и наоборот: 0110100110010110... Сколько единиц встречается среди первых 2017 членов этой последовательности?

задан 15 Ноя '17 2:02

10|600 символов нужно символов осталось
1

Эта последовательность может быть ещё описана так: берётся 0, а потом 0 заменяется на 01, и 1 на 10. По индукции доказывается, что это одно и то же.

Перед 2017-й цифрой идёт 1008 пар. Их "сворачиваем", то есть применяем обратное преобразование. Далее, если 1009-м шёл 0, то он же идёт и 2017-м.

По этой схеме, 1009 заменится на 505, потом 253, 127, а потом 64. Здесь уже цифра противоположна 32-й, а потому совпадает с 16-й, потом с 4-й, и в итоге с 1-й, то есть это 0.

Имеется совсем быстрый способ определения n-й цифры. Надо взять двоичную запись числа n-1 (для 2016 это 11111100000) и посмотреть на чётность числа единиц. Если чётно, то 0, если нечётно, то 1. Поэтому нумеровать члены естественнее с нуля.

Вообще, у этой последовательности очень интересная история, и куча всяких полезных и вкусных свойств!

ссылка

отвечен 15 Ноя '17 3:04

@falcao, большое спасибо! А что за история?

(16 Ноя '17 2:01) Аллочка Шакед

@Аллочка Шакед: эта последовательность обладает тем свойством, что она не содержит трёх повторов групп символов подряд. Более того, если она содержит XX (где X - непустое подслово), то следующая буква уже не равна первой букве X. У нас на этот результат ссылались как на лемму Аршона, доказанную в 1937 (sic!) году. Потом в конце 70-х нашли работу Акселя Туэ от 1908 года, где он это же доказал. Результат переоткрывался много раз и другими людьми. Сейчас принято говорить о последовательности Туэ - Морса. (Продолжение следует.)

(16 Ноя '17 2:30) falcao

Потом откопали работу некого Prouhet от примерно 1850 года. У него не было доказано свойство "сильной бескубности", но сама последовательность была в связи с примерно этой задачей. Один мой коллега-алгебраист пошутил, что скоро следы этой последовательности найдут в наскальных рисунках первобытного человека :)

(16 Ноя '17 2:33) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,401
×1,116
×370
×310
×150

задан
15 Ноя '17 2:02

показан
461 раз

обновлен
16 Ноя '17 2:33

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru