16.01 Одна функция

Если внимательно посмотреть на перебор до 1000 например, то можно заметить, что у подходящих чисел ровно три единицы в 2 системе счисления. Значит эта рекурсия подсчитывает количество единиц в 2-сс.

Также мы знаем, что единицы в 2-сс появляются так: 2 умножаем на какую-то степень n и получаем единичку.

Например число 7: . И в 2-сс выглядит как . Как раз три единицы.

Также, чтобы получить единицы на трех разных местах мы должны возводить двойки в разные степени и складывать эти числа (как мы уже выяснили на числе 7).

ans = 0
for i in range(31):
    for j in range(i + 1, 31):
        for k in range(j + 1, 31):
            # Строим число с единицами в позициях i, j, k
            s = 2 ** i + 2 ** j + 2 ** k
            # Проверяем попадание в диапазон
            if 1 <= s <= 10 ** 9:
                ans += 1
print(ans)

Также можно увидеть, что ответ равен .

Все потому что больше миллиарда, но если поставить 3 первые единицы на позициях в 2-сс и остальные нули, то получим число меньше миллиарда.