v0val, во-первых, можно кэшировать результаты вызовов - хоть в массиве, хоть в словаре, хоть декоратором из functools:
Код
from functools import lru_cache
@lru_cache
def F(n):
...
Ответ для 10_000_000 (в Python можно прямо писать числа с подчёркиваниями) хоть для 2, хоть для 3 будет получен менее чем за минуту.
Во-вторых, с миллиардом что Python, что C++ будут возиться не меньше нескольких минут. Решение "в лоб" с циклом неоптимально даже без вызовов рекурсивной функции, а для кэширования не хватит памяти. Надо придумывать что-то принципиально другое.
Посмотрите на двоичную запись нужных чисел:
Код
if F(n) == 3:
k +=1
print(n, F(n), bin(n))
Заметили?
С учётом особенностей числа 1_000_000_000 задачу можно решить так:
Код
import math
p = 1_000_000_000
print(bin(p))
n = len(bin(p)) - 2
s = 0
for i in range(n):
s += math.comb(i, 2)
print(s)
Однострочник для ценителей:
Код
import math; print(sum([math.comb(i, 2) for i in range(len(bin(1_000_000_000)) - 2)]))
