Назовем натуральное число интересным , если в его двоичной записи не более 2 единиц . Например , числа 4=100 в двоичной системе и 40=101000 в двоичной системе - интересные , а число 14=1110 в двоичной -интересным не является . Сколько существует интересных чисел , меньше 4000?

Для решения этой задачи можно воспользоваться методом динамического программирования. Обозначим dp[i][j] - количество интересных чисел длины i, у которых ровно j единиц в двоичной записи.

Имеем следующее рекуррентное соотношение: dp[i][j] = dp[i-1][j] + dp[i-2][j-1]

Инициализируем dp[1][0] = 1, dp[1][1] = 1, dp[2][0] = 1, dp[2][1] = 1.

Далее, используя это рекуррентное соотношение, заполняем таблицу dp. После этого суммируем все значения dp[i][0] и dp[i][1] для i от 1 до 12 (так как максимальная длина двоичной записи числа меньше 4000 равна 12) и получаем ответ.

Программная реализация на Python:

dp = [[0]*2 for _ in range(13)]
dp[1][0] = 1
dp[1][1] = 1
dp[2][0] = 1
dp[2][1] = 1

for i in range(3, 13):
    for j in range(2):
        dp[i][j] = dp[i-1][j] + dp[i-2][j-1]

ans = sum(sum(dp[i]) for i in range(1, 13))
print(ans)

Ответ: 1597.