小编Dar*_* P.的帖子

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

然而，由于欧拉的工作，使用整数分区来解决这个问题是有好处的。解决方案是小于或等于 2000 的所有 5 倍数的不同分区的总和，类似于我几年前在 MathstackExchange 上发布的内容，其中使用“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 …