如何生成连续序列，其总和等于N

Question

给定一个数N，生成一个公差为1的等差数列，使得有限元素求和后得到数字N。 例如：

For Example:
N=10
1 + 2 + 3 + 4 =10
N=20
2+3+4+5+6 = 20
N=30
4+5+6+7+8 = 30

N < 1000000

- Satish Patel

---

并非所有的N都具有这样的求和形式，例如2和4。 - Memming

这个问题不适合讨论，因为它涉及到数学。如果您希望我们将其视为编程问题，请展示您的代码。 - High Performance Mark

是的，它们确实如此。 2 = 2 和 4 = 4（即N可以被视为仅有一个数字的等差数列）。 - Bernhard Barker

如果考虑@Dukeling的解决方案，那么所有情况下最简单的解决方案将是N本身。因此，我认为总和中最大的数字必须小于N（在这种情况下，并不总是存在解决方案）。或者也许我们正在寻找最长的序列？ - Dennis Jaheruddin

此外，如果 N mod 2 == 1，那么对于非一数序列，你可以直接返回 (n+1)/2, (n-1)/2。我真的认为我们应该寻找最长的序列。例如，对于 N = 15，我们应该返回 [1,2,3,4,5] 还是 [7,8]？ - Geobits

Answer 1

1. 将sum的初始值设为0。

2. 将当前数字设置为1。

3. 将当前数字加到sum中。

4. 如果sum > N，从被加到sum中的第一个数字开始减去数字，直到sum <= N。

5. 如果sum = N，停止（成功）。

6. 增加当前数字。

7. 回到步骤 3。

你只需要记住被加到sum中的第一个数字，在步骤 4 中将其逐一从sum中减去（感谢 Niko）。

作为优化，你还可以使用公式 (n(n+1)/2) 批量添加数字，而不是一个一个地添加（在N很大的情况下）。

示例：

N = 30

Sum = 0
Add 1 -> 1
Add 2 -> 3
Add 3 -> 6
Add 4 -> 10
Add 5 -> 15
Add 6 -> 21
Add 7 -> 28
Add 8 -> 36
36 > 30, so:
  Subtract 1 -> 35
  Subtract 2 -> 33
  Subtract 3 -> 30
Done.

- Bernhard Barker

---

你可能也需要一个终止条件来处理失败的情况，例如“一旦你要添加当前数字N+1就停止”。 - G. Bach

@G.Bach 当仅有N在总和中时，它将始终终止。 - Bernhard Barker

哦，你说得对。也许是关于运行时间的问题？考虑到最坏情况下有2n个加法和log n位，应该是O(n log n)。 - G. Bach

@G.Bach 是的，如果你认为加法是一个log n操作，那么它就是O(n log n)。 - Bernhard Barker

Answer 2

让T表示数字

所以在第一种情况下，即N=4时，N(N+1)/2 = T

所以在第二种情况下，即N=6且K=1时，N(N+1)/2 - K(K+1)/2 = T

所以在第三种情况下，即N=8且K=3时，N(N+1)/2 - K(K+1)/2 = T

因此，你需要解决基本的N问题，这可以通过乘法和简化得到：

N^2 + N - (2T + K^2 + K) = 0

对于N的二次公式应用如下：

N= (-b + sqrt(b^2 - 4ac))/2a

即可得：

N = (-1 +- sqrt(1 + 8T + 4K^2 + 4K))/2

N必须为正数，我们可以去掉负面的情况

因此，N必须等于

N = (sqrt(8T + (2k+1)^2) - 1)/2

您可以从K=0开始迭代，直到获得一个自然数N为止，这将是您的答案

希望有所帮助，我正在尝试找到更好的方法（感谢这个有趣的问题）

- Ram G Athreya

---

这似乎可以相当高效地完成（线性复杂度？！）。改进的方法可能是从K = N/2（或更聪明的东西）开始，然后在log(N)步骤中进行搜索。 - Dennis Jaheruddin

这很棒，不过我想知道你如何确定N是自然数？ - neeKo

n=(int)n 那不是最简单的方法吗？在JavaScript中，我会使用n==parseInt(n) & n>0 - Ram G Athreya

@Ram 谢谢你，Ram。非常出色的方法。 - Satish Patel

Answer 3

int NumSum(int val)
{
    int n = 0, i = 0, j;
    while (n != val)
    {
        n = 0;
        j = ++i;
        while (n < val)
            n += j++;
    }
    return i;
}

没有花哨的数学，只需简单的方法...返回要开始计数的数字。

- user2746020

Answer 4

设 N = pq，其中 p 是一个正奇整数，q 是任意正整数。

(1) 你可以将 N 写成 p 个连续整数的和，且其中 q 是中间值。

(2) 如果 p 和 q 都是奇数（比如说，q = 2k+1），那么你还可以将 N 写成 2p 个连续整数的和，且其中 k 和 k+1 是中间值。

例如，令 N = 15 = 5 x 3。

如果我们选择 p=5，那么按照规则 (1)，可以得到 1+2+3+4+5 = 15。 或者按照规则 (2)，也可以得到 (-3)+(-2)+(-1)+0+1+2+3+4+5+6 = 15。

我们还可以选择 p = 3，得到 4+5+6 = 15 和 0+1+2+3+4+5 = 15。

- Worakarn Isaratham

Answer 5

这更像是一个技巧性的方法，我认为它可能有效。

假设数字是10，则从n/2即5开始一个序列。 现在序列不能是

5 + 6，因为10 > 11，所以我们还要向后计算，同时5是我们需要考虑的数字的上限，因为像6 + 7等数字将超过10，所以序列的最后一个（最高）数字将是5。 向后移动5 + 4 = 9 < 10

5 + 4 + 3 = 12 > 10，因此删除第一个元素，有点像队列。

因此，对于20，我们有 start = 20/2 = 10

1. 10 + 9 = 19 -> 什么也不做
2. 10 + 9 + 8 = 27 -> 移除第一个元素10
3. 9 + 8 + 7 = 24 -> 移除9
4. 8 + 7 + 6 = 21 -> 移除8
5. 7 + 6 + 5 = 18 -> 什么也不做
6. 7 + 6 + 5 + 4 = 22 -> 移除7
7. 6 + 5 + 4 + 3 = 18 -> 什么也不做
8. 6 + 5 + 4 + 3 + 2 = 20 -> 我们需要的答案

我猜这是对已接受答案的变体，但仍然认为我可以添加这个作为替代解决方案。

- Ram G Athreya

Answer 6

首先，每个奇数都是长度为2的等差数列的和，因为 n = floor(n/2) + ceil(n/2)。

更有趣的是，一个有奇数因子d的数字是围绕着n/d的长度为d的等差数列（差为1）的和。例如，30可以被5整除，因此它是围绕6的等差数列之和：30 = 4 + 5 + 6 + 7 + 8。

没有奇数因子的数字是2的幂。虽然1 = 0 + 1和2 = -1 + 0 + 1 + 2，但更大的幂不是任何（非平凡的）等差数列的和。为什么？假设2**m = a + (a+1) + .. + (a+k-1)。求和系列= k (2a + k-1) / 2。k必须是奇数或偶数，但任何一种选择都会与总和为2的幂矛盾。

- Colonel Panic