python - 多项式系数的最大递归

Question

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

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

毫无疑问，Grant Sanderson 的解决方案是优雅的，因为它不需要计算机，无需冗长的计算即可找到。

我的代码是:

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

Answer 1

另一种方法是计算达到 5 个模值 (0,1,2,3,4) 中每一个的和的组合。将这些计数保存在列表中并逐渐增加它们。最后，对零取模，得到加起来是 5 倍数的组数:

def sumDiv5Count(numbers):
    modCounts = [0]*5
    for n in numbers:
        modCounts = [c+modCounts[(i-n)%5] for i,c in enumerate(modCounts)]
        modCounts[n%5] += 1        
    return modCounts[0]

每个数字的模 5 与 5 个可能的模相结合，以添加更多方式来生成 5 个不同的结果模值。

例如 13%5 -> 3，

• 产生 0 的方法被添加到产生 0+3 的方法 --> 槽 3

• 产生 1 的方法被添加到产生 1+3 的方法 --> 槽 4

• 产生 2 的方法被添加到产生 2+3 的方法中 --> 插槽 0 (2+3)%5 = 0

• 产生 3 的方法被添加到产生 3+3 的方法中 --> 槽 1 (3+3)%5 = 1

• 产生 4 的方法被添加到产生 4+3 的方法中 --> 槽 2 (4+3)%5 = 2

• 还有一种方法可以单独生成 3

输出:

print(sumDiv5Count(range(1,10)))
# 103

print(sumDiv5Count(range(1,50)))
# 112589990684671

print(sumDiv5Count(range(1,100)))
# 126765060022822940149670739967

print(sumDiv5Count(range(1,500)))
# 327339060789614187001318969682759915221664204604306478948329136809613379640467455488327009232590415715088668412756007101428785894679831065931534041087

print(sumDiv5Count(range(1,1000)))
# 1071508607186267320948425049060001810561404811705533607443750388370351051124936122493198378815695858127594672917553146825187145285692314043598457757469857480393456777482423098542107460506237114187795418215304647498358194126739876755916554395250481509160715757985439053702508024174143636196837700927487

print(sumDiv5Count(range(1,2001)))
# 22962613905485090484656664023553639680446354041773904009552854736515325227847406277133189726330125398368919292779749255468942379217261106628518627123333063707825997829062456000137755829648008974285785398012697248956323092729277672789463405208093270794180999311632479761788925921124662329907232844394066536268833781796891701120475896961582811780186955300085800543341325166104401626447256258352253576663441319799079283625404355971680808431970636650308177886780418384110991556717934409897816293912852988275811422719154702569434391547265221166310540389294622648560061463880851178273858239474974548427800575

这种方法的一个好处是，它可以很容易地变成一个生成器，在遍历数字时逐渐生成计数。它也不依赖于按顺序排列的数字，甚至不依赖于不同的数字。鉴于它是一个 O(n) 过程，性能很好(几毫秒)。