Чтобы найти количество интересных чисел, меньших 4000, нужно определить какие числа являются интересными в соответствии с заданным критерием. Напомним, что интересное число в двоичной записи содержит не более 2 единиц.

Числа с одной единицей в двоичной записи – это степени двойки:

(2^0 = 1)(2^1 = 2)(2^2 = 4)(2^3 = 8)(2^4 = 16)(2^5 = 32)(2^6 = 64)(2^7 = 128)(2^8 = 256)(2^9 = 512)(2^{10} = 1024)(2^{11} = 2048)(2^{12} = 4096) (но это число больше 4000, его учитывать не будем)

Итак, у нас есть 12 чисел с одной единицей.

Теперь числа с двумя единицами. Эти числа можно записать в виде (2^a + 2^b), где (a > b). Чтобы посчитать такие числа, найдем все возможные пары ( (a, b) ):

Для (a = 1): (2^1 + 2^0 = 2 + 1 = 3)Для (a = 2):
(2^2 + 2^0 = 4 + 1 = 5)(2^2 + 2^1 = 4 + 2 = 6)Для (a = 3):
(2^3 + 2^0 = 8 + 1 = 9)(2^3 + 2^1 = 8 + 2 = 10)(2^3 + 2^2 = 8 + 4 = 12)Для (a = 4):
(2^4 + 2^0 = 16 + 1 = 17)(2^4 + 2^1 = 16 + 2 = 18)(2^4 + 2^2 = 16 + 4 = 20)(2^4 + 2^3 = 16 + 8 = 24)Для (a = 5):
(2^5 + 2^0 = 32 + 1 = 33)(2^5 + 2^1 = 32 + 2 = 34)(2^5 + 2^2 = 32 + 4 = 36)(2^5 + 2^3 = 32 + 8 = 40)(2^5 + 2^4 = 32 + 16 = 48)Для (a = 6):
(2^6 + 2^0 = 64 + 1 = 65)(2^6 + 2^1 = 64 + 2 = 66)(2^6 + 2^2 = 64 + 4 = 68)(2^6 + 2^3 = 64 + 8 = 72)(2^6 + 2^4 = 64 + 16 = 80)(2^6 + 2^5 = 64 + 32 = 96)Для (a = 7):
(2^7 + 2^0 = 128 + 1 = 129)(2^7 + 2^1 = 128 + 2 = 130)(2^7 + 2^2 = 128 + 4 = 132)(2^7 + 2^3 = 128 + 8 = 136)(2^7 + 2^4 = 128 + 16 = 144)(2^7 + 2^5 = 128 + 32 = 160)(2^7 + 2^6 = 128 + 64 = 192)Для (a = 8):
(2^8 + 2^0 = 256 + 1 = 257)(2^8 + 2^1 = 256 + 2 = 258)(2^8 + 2^2 = 256 + 4 = 260)(2^8 + 2^3 = 256 + 8 = 264)(2^8 + 2^4 = 256 + 16 = 272)(2^8 + 2^5 = 256 + 32 = 288)(2^8 + 2^6 = 256 + 64 = 320)(2^8 + 2^7 = 256 + 128 = 384)Для (a = 9):
(2^9 + 2^0 = 512 + 1 = 513)(2^9 + 2^1 = 512 + 2 = 514)(2^9 + 2^2 = 512 + 4 = 516)(2^9 + 2^3 = 512 + 8 = 520)(2^9 + 2^4 = 512 + 16 = 528)(2^9 + 2^5 = 512 + 32 = 544)(2^9 + 2^6 = 512 + 64 = 576)(2^9 + 2^7 = 512 + 128 = 640)(2^9 + 2^8 = 512 + 256 = 768)Для (a = 10):
(2^{10} + 2^0 = 1024 + 1 = 1025)(2^{10} + 2^1 = 1024 + 2 = 1026)(2^{10} + 2^2 = 1024 + 4 = 1028)(2^{10} + 2^3 = 1024 + 8 = 1032)(2^{10} + 2^4 = 1024 + 16 = 1040)(2^{10} + 2^5 = 1024 + 32 = 1056)(2^{10} + 2^6 = 1024 + 64 = 1088)(2^{10} + 2^7 = 1024 + 128 = 1152)(2^{10} + 2^8 = 1024 + 256 = 1280)(2^{10} + 2^9 = 1024 + 512 = 1536)Для (a = 11):
(2^{11} + 2^0 = 2048 + 1 = 2049)(2^{11} + 2^1 = 2048 + 2 = 2050)(2^{11} + 2^2 = 2048 + 4 = 2052)(2^{11} + 2^3 = 2048 + 8 = 2056)(2^{11} + 2^4 = 2048 + 16 = 2064)(2^{11} + 2^5 = 2048 + 32 = 2080)(2^{11} + 2^6 = 2048 + 64 = 2112)(2^{11} + 2^7 = 2048 + 128 = 2176)(2^{11} + 2^8 = 2048 + 256 = 2304)(2^{11} + 2^9 = 2048 + 512 = 2560) (2^{11} + 2^{10} = 2048 + 1024 = 3072)

Пары (a, b), которые давали числа меньше 4000, это:

( (11, 0) ) — 2049( (11, 1) ) — 2050( (11, 2) ) — 2052( (11, 3) ) — 2056( (11, 4) ) — 2064( (11, 5) ) — 2080( (11, 6) ) — 2112( (11, 7) ) — 2176( (11, 8) ) — 2304( (11, 9) ) — 2560( (11, 10) ) — 3072( (10, 9) ) — 1536( (10, 8) ) — 1280( (10, 7) ) — 1152( (10, 6) ) — 1088( (10, 5) ) — 1056( (10, 4) ) — 1040( (10, 3) ) — 1032( (10, 2) ) — 1028( (10, 1) ) — 1026( (10, 0) ) — 1025

Посчитав, можно заметить, что существует 12 чисел с одной единицей и 66 чисел с двумя единицами.

Таким образом, общее количество интересных чисел:
[
12 + 66 = 78
]

Поэтому ответ: 78 интересных чисел, меньших 4000.