Обозначим через a%b остаток от деления натурального числа a на натуральное
число b, а через a//b – целую часть от деления a на b.
Функция F(n), где n – неотрицательное целое число, задана следующими
соотношениями:
F(n) = 0, если n = 0;
F(n) = F(n//10) + n%10, если n>0 и n чётно;
F(n) = F(n//10), если n нечётно.
Сколько существует таких натуральных чисел n, что 107 ≤ n ≤ 6·107 и F(n) = 0?
Чтобы решить задачу, давайте проанализируем функцию \( F(n) \) и определить, когда она равна 0.
Функция \( F(n) \) определена следующим образом:
1. \( F(n) = 0 \), если \( n = 0 \).
2. \( F(n) = F(n//10) + n \% 10 \), если \( n > 0 \) и \( n \) — четное.
3. \( F(n) = F(n//10) \), если \( n \) — нечетное.
Теперь рассмотрим второй и третий случаи:
- **Если \( n \) четное:**
- Здесь функция будет добавлять последнюю цифру \( n \) (то есть \( n \% 10 \)) к значению \( F(n//10) \).
- Если последняя цифра четна (0, 2, 4, 6, 8), это может привести к тому, что функция будет добавлять к своему значению что-то больше нуля, и, таким образом, \( F(n) \) не станет равной 0.
- Однако, если последняя цифра равна 0, то \( F(n) = F(n//10) + 0 = F(n//10) \).
- **Если \( n \) нечетное:**
- Здесь функция не добавляет ничего, и просто вызывает себя с делением \( n \) на 10 (отсекается последняя цифра).
- Это значит, что если \( n \) нечетное, \( F(n) = F(n//10) \).
Теперь нам нужно определить, когда \( F(n) = 0 \) для натуральных чисел \( n \).
### Условия для \( F(n) = 0 \)
- \( F(n) = 0 \) только тогда, когда:
- Если \( n \) четное и заканчивается на 0, то будет \( F(n) = F(n//10) \), и чтобы \( F(n) \) было 0, требуется, чтобы и \( n//10 \) также соответствовал тому же условию.
- Это значит, что \( n \) должен быть четным, заканчивающимся на 0 (такие числа натуральные, например, 10, 20, ..., 100, ...).
- Все нечетные числа приводят только к \( F(n) \neq 0 \).
Таким образом, мы ищем четные числа \( n \), которые заканчиваются на 0, в диапазоне от \( 107 \) до \( 6 \cdot 10^7 \).
### Диапазон четных чисел от 107 до \( 6 \cdot 10^7 \)
- **Минимальное \( n \)** в диапазоне \( 107 \leq n \) должно быть \( 110 \) (это первое четное число, большее 107).
- **Максимальное \( n \)** в диапазоне \( n \leq 6 \cdot 10^7 \) будет \( 60000000 \).
### Подсчет таких чисел
Четные числа, заканчивающиеся на 0, это 110, 120, 130, ..., 60000000. Таковые можно найти по формуле арифметической прогрессии.
1. Обозначим \( a_1 = 110 \) (первый член).
2. Обозначим \( a_n = 60000000 \).
3. Разность прогрессии \( d = 10 \).
Теперь найдем количество членов \( n = \frac{a_n - a_1}{d} + 1 \):
\[
n = \frac{60000000 - 110}{10} + 1 = \frac{59999890}{10} + 1 = 5999989 + 1 = 5999990.
\]
Таким образом, количество натуральных чисел \( n \), для которых \( 107 \leq n \leq 6 \cdot 10^7 \) и \( F(n) = 0 \), равно **5999990**.
