Определите количество таких целых k, что 10⁹ ≤ k ≤ 2 · 10⁹ и F(k) = 2.

Решение по шагам

1. 1

   Как рассуждать

   Решение. Для примера найдем значение F(12345): $F ( 12345 ) = F ( 1234 ) = F ( 123 ) + 4 = F ( 12 ) + 4 = F ( 1 ) + 2 + 4 = F ( 0 ) + 2 + 4 = 6$ $F ( 12345 ) = F ( 1234 ) = F ( 123 ) + 4 =$ $= F ( 12 ) + 4 = F ( 1 ) + 2 + 4 = F ( 0 ) + 2 + 4 = 6$ То есть алгоритм считает сумму всех четных цифр в числе. Поскольку по условию задачи требуется найти числа, сумма четных цифр которых равна 2, то число может состоять только из нечетных цифр, нуля и одной двойки. Достаточно посчитать все возможные варианты. На первом месте может стоять 1, далее одна двойка на любом месте и цифры из набора 0 (так как 0 в сумме не увеличивает число), 1, 3, 5, 7, 9 (всего 6). Посчитаем количество чисел из диапазона 10⁹ ≤ k ≤ 2 · 10⁹−1, удовлетворяющих условию: $1 \cdot 9 \cdot 6 \cdot 6 \cdot 6 \cdot 6 \cdot 6 \cdot 6 \cdot 6 \cdot 6 = 15 116 544$ Также подходит число 2 · 10⁹, так как содержит одну двойку. Всего подходящих чисел: $15 116 544 + 1 = 15 116 545$