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

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

Изначально dp[1][0] = 1 (единственное число длины 1 без единиц), dp[1][1] = 1 (единственное число длины 1 с одной единицей).

Далее пересчитываем значения dp[i][j] по формуле: dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

Таким образом, можем построить таблицу значений dp и найти сумму всех интересных чисел длиной от 1 до 13 (так как 2^13 = 8192 > 8000).

Суммируя все значения dp[i][j] для i от 1 до 13 и j от 0 до 2, получаем ответ: 1 + 2 + 3 + 3 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 = 45.

Итак, существует 45 интересных чисел, меньших 8000.