C++ тестирование сириус задача8

Найдём первые полтора десятка членов последовательности:

 F(0) = 0

F(1) = F(0) + 1 = 1

F(2) = F(1)     = 1

F(3) = F(2) + 1 = 2

F(4) = F(2)     = 1

F(5) = F(4) + 1 = 2

F(6) = F(3)     = 2

F(7) = F(6) + 1 = 3

F(8) = F(4)     = 1

F(9) = F(8) + 1 = 2

F(10) = F(5)    = 2

F(11) = F(10) + 1 = 3

F(12) = F(6)      = 2

F(13) = F(12) + 1 = 3

F(14) = F(7)      = 3

F(15) = F(14) + 1 = 4

... 

Какую видим закономерность? F(n) = кол-во единичных бит в n

 F(2n) = F(n)  - потому что кол-во единичных бит при умножении на 2 сохраняется

F(2n + 1) = F(2n) + 1 - потому что чётное число имеет в младшем бите 0,

        и при добавлении к нему 1 кол-во единичных бит увеличивается на 1 

Отсюда, для любого целого k:

 F(2ᵏ)     = 1

F(2ᵏ - 1) = k 

Но у нас граница диапазона (1 млрд = 10⁹) не является степенью двойки или соседним с ней числом. Как найти максимально возможное количество единичных бит в этом случае? Найдём ближайшие к миллиарду степени двойки:

 2²⁹ < 10⁹ < 2³⁰ 

Мы не можем достичь 30 единичных бит, т.к. минимальное число, в котором они встречаются, - это

 2³⁰ - 1 > 10⁹ 

А кол-во единичных бит в 2²⁹ - это как раз 29. Значит, наше искомое число nmax содержит 29 единичных бит.
А всего в записи числа 10⁹ содержится 30 бит, старший из которых равен единице.
Значит, мы ищем число с 29-ю единичными и одним нулевым битом.
В числе 10⁹ - как минимум 9 нулевых бит, т.к. оно делится на 2⁹, значит, оно нам не подходит.
Где вообще должен находиться тот единственный нулевой бит, чтобы число было максимальным? Как можно ближе к младшему разряду, но чтобы число не превышало 10⁹.
Итак, искомое число nmax выглядит так:

 nmax = 10⁹ - j = 2³⁰ - 1 - 2ᵏ

j > 0

0 < k < 30 

k легко находится аналитически:

 2³⁰ - 1 - 10⁹ = 2ᵏ - j

1073741823 - 1000000000 = 2ᵏ - j

73741823 = 2ᵏ - j

 2²⁶ < 73741823 < 2²⁷

(2²⁶ = 67108864, 2²⁷ = 134217728)

k = 27, j = 60475905

nmax = 2³⁰ - 1 - 2²⁷ = 2²⁷ ∙ (2³ - 1) - 1 = 2²⁷ ∙ 7 - 1 

В двоичной записи этого числа нулевой бит будет стоять на 27-й позиции (где 2²⁷), правее него будет 27 единичных бит (полученных вычитанием единицы с заёмом), а левее - 2 единичных бита (оставшихся от трёх бит семёрки), итого F(nmax) = 29, как и планировалось. Это число - максимальное в пределах миллиарда с 29-ю единичными битами: если бы мы взяли 2³⁰-2²⁶-1, то результат превысил бы миллиард, а если бы взяли 2³⁰-2²⁸-1, то результат был бы меньше найденного нами.

 nmax = 2²⁷ ∙ 7 - 1 = 939524095₁₀ = 11 0111 1111 1111 1111 1111 1111 1111₂ 

Это рекурсивная функция. Значение F(n) определяется предыдущими значениями F(n). Максимальное значение F(n) для n в диапазоне 100000000⩽n⩽1000000000 может быть найдено путем анализа функции.

Для нечетного n, F(n) = F(n-1) + 1. Это означает, что при нечетном n значение F(n) увеличивается на 1 по сравнению с предыдущим значением.

Для четного n, F(n) = F(n/2). Это означает, что для четного n значение F(n) равно значению F(n/2).

Поэтому, чтобы максимизировать значение F(n), нам нужно найти наибольшее нечетное число в заданном диапазоне. Наибольшее нечетное число в диапазоне 100000000⩽n⩽1000000000 равно 999999999. Значит, максимальное значение F(n) для n в заданном диапазоне равно F(999999999).

Хотите, чтобы я объяснил, как вычислить значение F(999999999)?