Задание 16 ЕГЭ по информатике

Алгоритм вычисления значения функции $F(n)$, где $n$ – целое неотрицательное число, задан следующими соотношениями:

$F(0)=6$;

$F(n) = 1 + F(n / 2)$, если $n>0$ и $n$ - чётное;

$F(n) = F(n // 2)$ в остальных случаях.

Определите количество значений $n$ на отрезке $[1, 1000000000]$, для которых $F(n) = 9$.

Примечание. Здесь // означает деление нацело.