Задание 16. Информатика. ЕГЭ. Поляков-7827

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

• \(F(n) = F(n/2) + 5,\) если \(n\) чётное;
• \(F(n) = F(n/5) + 2,\) если \(n\) нечётное и делится на \(5;\)
• \(F(n) = 0,\) если \(n\) нечётное и не делится на \(5.\)

Сколько различных значений принимает функция \(F(n)\) для значений аргумента на отрезке \([1; \, 1000000]?\)

def F(n):
    if n % 2 == 0:
        return F(n // 2) + 5
    elif n % 5 == 0:
        return F(n // 5) + 2
    return 0

ans = set()
for i in range(1, 1000001):
    ans.add(F(i))
print(len(ans))