Python 3.12.5
The algorithm for calculating the value of the function F(n), where n is a natural number, is given
by the following ratios:
F(n) = 1 for n = 1;
F(n) = 2 for n = 2;
F(n) = n * (n - 1) + F(n - 1) + F(n - 2) if n > 2.
What is the value of the expression F(2024) - F(2022) - 2 * F(2021) - F(2020)?
At first I just used recursion with the big limit, but I found out that the program runs TOOOOOOO slow (because I didn't use @lru_cache), I watched a video with the solution of this task and used this code
from functools import lru_cache
import sys
sys.setrecursionlimit(50000000)
@lru_cache
def F(n):
if n == 1:
return 1
if n == 2:
return 2
return n*(n-1) + F(n-1) + F(n-2)
print(F(2024) - F(2022) - 2*F(2021) - F(2020))
It worked for the author of the video. When I had tried it in an online interpretator, it worked too and I got the correct answer. But it doesn't work on my PC. I get RecursionError although I set the recursion limit to 50000000:
return n*(n-1) + F(n-1) + F(n-2)
^^^^^^
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
What do I do? Maybe there are some other solutions?
It seems you have bumped into the same bug as reported in issue #112215 - 3.12 setrecursionlimit is ignored in connection with @functools.cache. See also #112282. It looks like a major regression was introduced in 3.12 and is still present in 3.12.5.
For the actual challenge you try to solve, you don't need a function that calculates Fibonacci-like numbers at all. You can derive the answer by expanding the recursive š¹-terms with greater arguments until we're left with an expression that just has a number of š¹2021 and š¹2020, which happen to cancel each other:
We start with:
Ā Ā Ā š¹2024 ā š¹2022 ā 2š¹2021 ā š¹2020
We can expand that š¹2024:
Ā Ā Ā 2024ā 2023 + š¹2023 + š¹2022 ā š¹2022 ā 2š¹2021 ā š¹2020
We can eliminate š¹2022 ā š¹2022:
Ā Ā Ā 2024ā 2023 + š¹2023 ā 2š¹2021 ā š¹2020
We can expand that š¹2023:
Ā Ā Ā 2024ā 2023 + 2023ā 2022 + š¹2022 + š¹2021 ā 2š¹2021 ā š¹2020
We can reduce š¹2021 ā 2š¹2021, to ā š¹2021:
Ā Ā Ā 2024ā 2023 + 2023ā 2022 + š¹2022 ā š¹2021 ā š¹2020
We can expand that š¹2022:
Ā Ā Ā 2024ā 2023 + 2023ā 2022 + 2022ā 2021 + š¹2021 + š¹2020 ā š¹2021 ā š¹2020
We can now eliminate all š¹ terms, and so the result is:
Ā Ā Ā 2024ā 2023 + 2023ā 2022 + 2022ā 2021 = 12271520