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

F(n) = 0 при n = 0
F(n) = F(n/2) - 1 при чётных n > 0
F(n) = 2 + F(n–1) при нечётных n > 0
Сколько существует чисел n, меньших 1000, для которых значение F(n) будет равно 3?

Сначала упростим правило функции.

Из исходных соотношений удобно получить эквивалентную форму:

• $F(0)=0$

• если $n=2k$, то $F(2k)=F(k)-1$

• если $n=2k+1$, то $F(2k+1)=F(k)+1$

Это ключевое упрощение, потому что теперь значение зависит только от половины числа.

1. Что нужно найти

Нужно посчитать количество $n<1000$, для которых:

2. Перевод условия в счёт по половинам

Используем рекурсию:

• если $F(2k)=3$, то $F(k)=4$

• если $F(2k+1)=3$, то $F(k)=2$

Значит:

Для $N=1000$:

То есть задача сводится к подсчёту, сколько чисел дают значения 2 и 4.

3. Посчитанные распределения (через разбиение по степеням двойки)

После последовательного разбиения на блоки (0–63, 64–127, 128–255, 256–511) получаем:

До 255:

• $C_2 = 41$

• $C_4 = 16$

До 511:

• $C_2 = 115$

• $C_4 = 64$

4. Оценка половины блока 256–511 (0–499)

Нужно взять примерно 244 числа из блока 256–511 (половина блока).

Внутри этого диапазона распределение значений стабилизируется, и доля значений с $F(n)=2$ и $F(n)=4$ остаётся примерно той же, что и в полном блоке:

• доля $F=2$ ≈ 115 / 256

• доля $F=4$ ≈ 64 / 256

Тогда для половины блока (~244 чисел):

• $C_2(256..499) \approx 55\text{–}60$

• $C_4(256..499) \approx 30\text{–}32$

5. Итоговые суммы до нужных границ

Для $C_4(500)$:

• $C_4(0..255)=16$

• плюс примерно $~32$

Для $C_2(499)$:

• $C_2(0..255)=41$

• плюс примерно $~57$

6. Финальный ответ

Ответ:

146