Обозначим через 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, что 4 · 107≤ n ≤ 9 · 107 и F(n) = 0?
Приведём аналитическое решение Юрия Красильникова.
Функция подсчитывает сумму чётных цифр числа. Если функция равна нулю, это значит, что в числе нет чётных цифр (за исключением нуля).
Первой цифрой числа может быть или 5, или 7, или 9. В последнем случае число только одно - это 90000000, т. к. число не должно превосходить это значение.
Если первая цифра - 5 или 7, то остальные семь цифр могут быть любыми из множества «013579» (всего 6 различных цифр).
Ответ к задаче - это 2 · 67+1=559873.
Функция выдает сумму четных цифр (больших 0) в числе. Для того, чтобы F(n) = 0 необходимо, чтобы в числе не было четных цифр больших 0.
Приведём решение на языке Python.
from itertools import product
count = 0
for i in product('013579', repeat=8):
if i[0] != '0':
if i[0] =='5' or i[0] =='7':
count += 1
print(count+1)#+1 так как учитываем число 9*10**7
Ответ: 559873.