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

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

Изначально заполним dp[1][0] = 1, dp[1][1] = 1, так как единственное интересное число длиной 1 бит - это число 1.

Далее, используя формулу dp[i][j] = dp[i-1][j] + dp[i-1][j-1], заполним таблицу dp для всех i от 2 до 12 (так как 2^12 = 4096).

После этого просуммируем все значения dp[i][j] для i от 1 до 12 и j от 0 до 2, чтобы найти общее количество интересных чисел меньше 4000.

Итоговый ответ: 2196 интересных чисел меньше 4000.