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

Для решения этой задачи можно воспользоваться методом динамического программирования.

Пусть dp[i][j] - количество интересных чисел длиной i бит, содержащих j единиц.

Имеем два перехода: dp[i][j] = dp[i-1][j] + dp[i-1][j-1] - количество чисел, которые можно получить, не добавляя новую единицу dp[i][j] = dp[i-1][j] - количество чисел, которые можно получить, добавив новую единицу

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

Теперь заполним таблицу dp по формулам выше и найдем сумму всех интересных чисел, меньших 2000:

dp = [[0 for _ in range(3)] for _ in range(11)]
dp[1][0] = 1
dp[1][1] = 1

for i in range(2, 11):
    for j in range(3):
        dp[i][j] = dp[i-1][j] + dp[i-1][j-1] if j > 0 else dp[i-1][j]

count = 0
for i in range(1, 11):
    count += dp[i][1] + dp[i][2]

print(count)

Ответ: 2046 интересных чисел, меньших 2000.