Python 多项式系数的最大递归

最近，我在YouTube上遇到了一个有趣的3Blue1Brown-OlympiadLevelCounting提出的计数问题.问题是找出集合{1，2，…，2000}的子集的个数，这些子集的元素之和可以被5整除.格兰特·桑德森提出了一个漂亮的解决方案，但他也讨论了如果在计算机上实施该算法以有效解决问题可能会变得多么繁琐.

然而，由于Euler的工作，使用整数分区来解决这个问题是有好处的.解决方案是小于或等于2000的所有5的倍数的distinct partitions之和，类似于我的posted on MathstackExchange years ago，其中使用"dxiv"的注释是该代码的关键.

毫无疑问，格兰特·桑德森的解决方案是优雅的，因为它不需要计算机，而且不需要冗长的计算就能找到.

我的代码是:

import numpy as np

def p(k):
    if k == 1:
        return np.array([1, 1])
    else:
        q = p(k - 1)
    return add(q, np.append(np.zeros(k, int), q))


def add(u, v):
    u = np.append(u, np.zeros(len(v) - len(u), int))
    return np.add(u, v)


def test(n):
    a = 1 << n
    b = 1 << (n//5)
    b *= 4
    return (a+b)//5


n = 1000      
generating_function = sum(p(n)[0:-1:5])+1
grant_sanderson = test(n)
print(generating_function)
print(grant_sanderson)
print(generating_function == grant_sanderson)

我的困难是，当n是一个大数字时.另外，这些数字太大了，所以我必须使用gmpy2.这是一个显示数组关于n//2对称的图:

Traceback (most recent call last):
  File "c:\Users\patil\OneDrive\Documents\GitHub\Theorie-der-Zahlen\Distinct partitions\distinctParitions-gmp2\main.py", line 15, in <module>
    generating_function = sum(p(n)[0:-1:5])+1
                              ^^^^
  File "c:\Users\patil\OneDrive\Documents\GitHub\Theorie-der-Zahlen\Distinct partitions\distinctParitions-gmp2\generatingfunction.py", line 8, in p
    q = p(k - 1)
        ^^^^^^^^
  File "c:\Users\patil\OneDrive\Documents\GitHub\Theorie-der-Zahlen\Distinct partitions\distinctParitions-gmp2\generatingfunction.py", line 8, in p
    q = p(k - 1)
        ^^^^^^^^
  File "c:\Users\patil\OneDrive\Documents\GitHub\Theorie-der-Zahlen\Distinct partitions\distinctParitions-gmp2\generatingfunction.py", line 8, in p
    q = p(k - 1)
        ^^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

下面的代码可以显示事情是如何迅速失控的:

import gmpy2

def q(n):
    Q = [gmpy2.mpz(0)] * (n+1)
    Q[0] = gmpy2.mpz(1)
    for k in range(1, n):
        for i in range(n, k-1, -1):
            Q[i] += Q[i-k]
    return Q[n] + 1