Решение программой:

for i in range(1, 1000000):
    s = bin(i)[2::]
    s += ’1’
    if s.count(’1’) % 2 == 0:
        s += ’0’
    else:
        s += ’1’
    # второй if не нужен, потому что всегда будет дописываться 0
    # подумайте почему)
    if s.count(’1’) % 2 == 0:
        s += ’0’
    else:
        s += ’1’
    if int(s, 2) > 212:
        print(int(s, 2))
        break

Аналитическое решение:

Каким бы не было число, на втором шаге к нему всегда дописывается единица, так что давайте называть это число «изначальным».

Если изначальное число имеет чётное количество единиц, то после добавления нуля количество единиц не изменится, а потому на следующем шаге также добавится ноль. Итого к числу допишут два нуля.

Если изначально число имеет нечётное количество единиц, то после добавления единицы количество единиц увеличится на , что означает, что количество единиц станет чётным числом, а значит на следующем шаге уже будут добавлять ноль. Итого к числу допишут единицу и ноль.

Значит мы будем проверять только числа, которые кончаются на или .

Могло ли получиться число ? Нет, в двоичной СС оно выглядит как , а значит получиться после алгоритма не могло.

Могло ли получиться число ? В двоичной СС оно выглядит как . Так что вполне возможно. Если откинем последние три цифры, то у нас останется число , добавим к нему единицу и получим число , у него чётное число единиц, а значит после работы алгоритма к нему дописали бы два нуля, но мы откинули , а значит это не то число, которое нам нужно.

Могло ли получиться число ? Нет, в двоичной СС оно выглядит как , а значит получиться после алгоритма не могло.

Могло ли получиться число ? Нет, в двоичной СС оно выглядит как , а значит получиться после алгоритма не могло.

Могло ли получиться число ? Нет, в двоичной СС оно выглядит как , а значит получиться после алгоритма не могло.

Могло ли получиться число ? Нет, в двоичной СС оно выглядит как , а значит получиться после алгоритма не могло.

Могло ли получиться число ? Нет, в двоичной СС оно выглядит как , а значит получиться после алгоритма не могло.

Могло ли получиться число ? В двоичной СС оно выглядит как . Так что вполне возможно. Если откинем последние три цифры, то у нас останется число , добавим к нему единицу и получим число , у него нечётное число единиц, а значит после работы алгоритма к нему дописали бы единицу и ноль, но мы откинули , а значит это не то число, которое нам нужно.

Могло ли получиться число ? Нет, в двоичной СС оно выглядит как , а значит получиться после алгоритма не могло.

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