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

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

• \(F(n) = n,\) если \(n > 1000000;\)
• \(F(n) = 3n + F(5n),\) если \(n \leqslant 1000000.\)
• \(G(n) = F(n) \, / \, n.\)

Определите количество натуральных чисел \(n\) (включая \(n = 3000),\) для которых \(G(n) = G(3000).\)

F = {n: n for n in range(1_000_001, 5_000_001)}
for n in range(1_000_000, 0, -1):
    F[n] = 3 * n + F[5 * n]
q = 0
G = F[3000] // 3000
for n in range(1, 5_000_000):
    q += F[n] // n == G
print(q)