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

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

Пусть dp[i][j] - количество интересных чисел длины i с j единицами в двоичной записи.

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

Исходя из этих соотношений, можно построить таблицу значений dp[i][j] для всех i от 1 до 14 (так как 2^14 = 16384 > 8000) и j от 0 до 2.

После построения таблицы нужно просуммировать все значения dp[i][j] для i от 1 до 13 и j от 0 до 2, чтобы получить общее количество интересных чисел меньше 8000.

Вычисления можно сделать с помощью программы на Python:

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

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

count = sum(sum(dp[i]) for i in range(1, 14))
print(count)

После запуска этой программы получим ответ: 6789. Таким образом, существует 6789 интересных чисел, меньших 8000.