有多少种方法可以得到总和为 x 的连续整数之和？

Question

如何以编程方式解决这些问题：

How many different ways are there to write:

a) 2021 as the sum of consecutive whole numbers?

b) x as the sum of consecutive whole numbers?

Answer 1

假设数字的顺序不重要，有 8518741657943308344041302580996941768179250799 种方法可以将 2021 写成正整数的总和。它被称为 partition number。没有一个简单的公式，但是有一个递归关系可以计算很多值。

函数实现在Python的sympy:

from sympy import partition

print(partition(2021))

现在新题，把2021写成连续整数的和：n + n+1 + ... + m-1 + m = 2021。首先请注意 n 的负值不会添加任何有趣的内容。当n < -m时，总和显然是负数。否则，负值只会“吃掉”相应的正值，您得到的总和与正解相同。

从1到m的数字之和为tri(m)=m*(m+1)/2,(the triangular number). The sum of the numbers from n to m is just tri(m)-tri(n-1). These equations can be solved by a SAT/SMT solver such as Z3:

from z3 import Int, Solver, And, Or, sat

s = Solver()
m = Int('m')
n = Int('n')
s.add(And(n > 0, n < 2022))
s.add(n <= m)
s.add(And(m > 0, m < 2022))
s.add(m * (m + 1) - n * (n - 1) == 2021 * 2)
while s.check() == sat:
    mi = s.model()[m].as_long()
    ni = s.model()[n].as_long()
    if ni > mi - 30:
        print("+".join([str(i) for i in range(ni, mi + 1)]), end="=")
    else:
        print("+".join([str(i) for i in range(ni, ni + 6)]), "+...+",
              "+".join([str(i) for i in range(mi - 4, mi + 1)]), end="=", sep="")
    print(sum([i for i in range(ni, mi + 1)]))
    s.add(Or(m != mi, n != ni))

输出：

26+27+28+29+30+...+64+65+66+67+68=2021
20+21+22+23+24+...+62+63+64+65+66=2021
1010+1011=2021
2021=2021

因此，对于 2021 年，有 4 个正解（以及 4 个相应的解，其中包括从 1-n 到 m 的负数）。

有多少种方法可以得到总和为 x 的连续整数之和？

How many ways to get a sum of consecutive whole numbers that total x?

math

permutation