Алгоритм вычисления значения функции 
, где 
– целое неотрицательное число, задан следующими соотношениями:
при 
если 
1 » class=»math» width=»auto»> и 
кратно 3
в остальных случаях
Сколько существует значений n на отрезке [1, 1500], для которых сумма цифр значения функции F(n) является простым числом?
from functools import lru_cache
@lru_cache(None)
def f(n):
if n <= 1:
return 1
elif n > 1 and n % 3 == 0:
return f(n — 1) + f(n — 2) + n
else:
return f(n — 2) + 2
def summa(n):
s = n
ans = 0
while s > 0:
ans += (s % 10)
s //= 10
return ans
def is_prime(n):
if n < 2: return False
for j in range(2, int(n ** 0.5) + 1):
if n % j == 0:
return False
return True
ans = 0
for i in range(1, 1500 + 1):
if is_prime(summa(f(i))):
ans += 1
print(ans)
@lru_cache(None)
def f(n):
if n <= 1:
return 1
elif n > 1 and n % 3 == 0:
return f(n — 1) + f(n — 2) + n
else:
return f(n — 2) + 2
def summa(n):
s = n
ans = 0
while s > 0:
ans += (s % 10)
s //= 10
return ans
def is_prime(n):
if n < 2: return False
for j in range(2, int(n ** 0.5) + 1):
if n % j == 0:
return False
return True
ans = 0
for i in range(1, 1500 + 1):
if is_prime(summa(f(i))):
ans += 1
print(ans)
Ответ: 301