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

Чтобы определить, сколько существует интересных чисел, меньших 2000, давайте разберем определение интересного числа. Оно должно содержать не более двух единиц в двоичной записи.

При этом интересные числа могут быть следующими:

1. Числа с одной единицей в двоичной записи. Эти числа соответствуют степеням двойки:

   • 1 (2^0 = 1)
   • 2 (2^1 = 2)
   • 4 (2^2 = 4)
   • 8 (2^3 = 8)
   • 16 (2^4 = 16)
   • 32 (2^5 = 32)
   • 64 (2^6 = 64)
   • 128 (2^7 = 128)
   • 256 (2^8 = 256)
   • 512 (2^9 = 512)
   • 1024 (2^10 = 1024)
   • 2048 (2^11 = 2048, но оно больше 2000 и не подходит)

   Всего таких чисел — 11.

2. Числа с двумя единицами в двоичной записи. Такие числа представляются как сумма двух различных степеней двойки. Для минимального числа с двумя единицами можно использовать следующие комбинации (где 2^i и 2^j — это различные степени двойки):

   • 2^0 + 2^1 = 3
   • 2^0 + 2^2 = 5
   • 2^0 + 2^3 = 9
   • 2^0 + 2^4 = 17
   • 2^0 + 2^5 = 33
   • 2^0 + 2^6 = 65
   • 2^0 + 2^7 = 129
   • 2^0 + 2^8 = 257
   • 2^0 + 2^9 = 513
   • 2^0 + 2^10 = 1025
   • 2^1 + 2^2 = 6
   • 2^1 + 2^3 = 10
   • 2^1 + 2^4 = 18
   • 2^1 + 2^5 = 34
   • 2^1 + 2^6 = 66
   • 2^1 + 2^7 = 130
   • 2^1 + 2^8 = 258
   • 2^1 + 2^9 = 514
   • 2^1 + 2^10 = 1026
   • 2^2 + 2^3 = 12
   • 2^2 + 2^4 = 20
   • 2^2 + 2^5 = 36
   • 2^2 + 2^6 = 68
   • 2^2 + 2^7 = 132
   • 2^2 + 2^8 = 260
   • 2^2 + 2^9 = 516
   • 2^2 + 2^10 = 1028
   • 2^3 + 2^4 = 24
   • 2^3 + 2^5 = 40
   • 2^3 + 2^6 = 72
   • 2^3 + 2^7 = 136
   • 2^3 + 2^8 = 264
   • 2^3 + 2^9 = 520
   • 2^3 + 2^10 = 1040
   • 2^4 + 2^5 = 48
   • 2^4 + 2^6 = 80
   • 2^4 + 2^7 = 144
   • 2^4 + 2^8 = 272
   • 2^4 + 2^9 = 528
   • 2^4 + 2^10 = 1056
   • 2^5 + 2^6 = 96
   • 2^5 + 2^7 = 160
   • 2^5 + 2^8 = 288
   • 2^5 + 2^9 = 544
   • 2^5 + 2^10 = 1092
   • 2^6 + 2^7 = 192
   • 2^6 + 2^8 = 320
   • 2^6 + 2^9 = 576
   • 2^6 + 2^10 = 1152
   • 2^7 + 2^8 = 448
   • 2^7 + 2^9 = 640
   • 2^7 + 2^10 = 1280
   • 2^8 + 2^9 = 768
   • 2^8 + 2^10 = 1536
   • 2^9 + 2^10 = 1536

   Посчитаем эти числа, оставаясь в пределах 2000. Всего мы получаем 45 различных таких комбинаций.

Суммируя, имеем:

• Числа с одной единицей: 11
• Числа с двумя единицами: 45

Таким образом, общее количество интересных чисел меньше 2000 составляет 11 + 45 = 56.

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