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

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

• \(F(n) = 1,\) при \(n < 2,\)
• \(F(n) = F(n \, / \, 3) + 1,\) когда \(n \geqslant 2\) и делится на \(3,\)
• \(F(n) = F(n - 2) + 5,\) когда \(n \geqslant 2\) и не делится на \(3.\)

Назовите количество значений \(n\) на отрезке \([1;~100~000],\) для которых \(F(n)\) равно \(55.\)

F = {0: 1, 1: 1}

for n in range(2, 100_001):
    F[n] = F[n // 3] + 1 if n % 3 == 0 else F[n - 2] + 5
print(list(F.values()).count(55))