Решение №1

def build_bin(string, lenght):
    # Если длина построенного слова совпадает с максимальной длинной
    if len(string) == lenght:
        return string.count(’0’) == 3 and int(string, 2) <= 10**9
    counter = 0
    # Строим новые двоичные числа (прибавляем 0 или 1)
    if string.count(’0’) < 3:
        counter += build_bin(string + ’0’, lenght) + \
                   build_bin(string + ’1’, lenght)
    # Если дошли до количества равного 3, то прибавляем данное
    # число (дописываем единицы)
    if string.count(’0’) == 3:
        counter += int(string + ’1’ * (lenght - len(string)), 2) <= 10**9
    return counter

ans = 0
for i in range(4, 31):
    ans += build_bin(’1’, i)
print(ans)

Решение №2

ans = 0
# Будем строить вида "из всех единичек"
# Напимер: 1111111 и нужно перебрать три единички
# То есть вычесть 3 единички из двоичного числа
# Поэтому вычитаем степени двойки
for i in range(31):
    for j in range(i + 1, 31):
        for k in range(j + 1, 31):
            for a in range(k + 1, 31):
                N = 2 ** (a + 1)
                N -= 1
                N = N - 2 ** k - 2 ** j - 2 ** i
                if 1 <= N <= 10 ** 9:
                    ans += 1
print(ans)