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

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

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

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

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