最近,我在YouTube上遇到了一个有趣的计数问题,由3Blue1Brown-OlympiadLevelCounting提出。这个问题是找到集合{1,2,...,2000}中元素之和能被5整除的子集的数量。Grant Sanderson提出了一个漂亮的解决方案,但他也讨论了如果在计算机上实现以有效地解决这个问题,算法会变得多么繁琐。
然而,由于欧拉的工作,使用整数分区来解决这个问题是很好的。解决方案是所有小于或等于2000的5的倍数的distinct partitions的总和,这与我多年前在MathstackExchange上发布的内容类似,其中使用“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
2条答案
按热度按时间bxgwgixi1#
另一种方法是计算达到5个模值(0,1,2,3,4)的总和的组合。将这些计数保存在列表中并逐渐增加它们。最后,将零取模的计数计算为总和为5的倍数的集合的数量:
每个数的模5与5个可能的模组合以添加更多的方式来产生5个不同的结果模值。
例如13%5 -〉3,
输出:
这种方法的一个优点是,它可以很容易地变成一个生成器,当它通过数字时,它会逐渐产生计数。它也不依赖于数字是否在序列中,甚至是不同的。考虑到它是一个O(n)过程,性能很好(几毫秒)。
u1ehiz5o2#
这不会抛出递归错误!对原始代码所做的更改:
sys.setrecursionlimit(2500)
gmpy2
抛出了错误的数字。所以使用了decimal.Decimal