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

F(n) = G(n) = 1 при n = 1;
F(n) = F(n - 1) - n · G(n - 1); при n > 1;
G(n) = 2 · F(n - 1) + G(n - 1); при n > 1:

а) Чему равно значение функции G(15)?

б) Чему равна сумма цифр значения выражения G(37) - F(36)?


F(n) = 1 при n = 1;
F(n) = F(n - 1) - n · G(n - 1); при n > 1;

G(n) = 1 при n = 1;
G(n) = 2 · F(n - 1) + G(n - 1); при n > 1:

кэш   
'''

from functools import lru_cache

@lru_cache
def F(n):
    if n == 1:
        return 1
    return F(n-1) - n*G(n-1)

def G(n):
    if n == 1:
        return 1
    return 2*F(n-1) + G(n-1)

#res = G(15)
#print(res)  # 35788457 

res = G(37) - F(36)
res = abs(res)
sm = sum(int(d) for d in str(res))  # сумма цифр 

print(sm)  # 151 :)