最大数量的连续奇数整数等于一个目标

Question

我目前正在寻找最大数量的连续奇数加在一起，以等于一个目标数。

我当前查找3个连续整数的代码如下所示

public class consecutiveOdd {
    public static void main(String[] args){
        int target = 160701;
        boolean found = false;

        for(int i = 1; i < target; i++){
            if(i + (i+2) + (i+4) == target){
                System.out.print(i + " + " + (i+2) + " + " + (i+4));
                found = true;
            }

         }
         if(!found){
            System.out.println("Sorry none");
         }
     }
}

我认为需要对(i+2)增量进行一个with循环构建迭代，但在开发正确的算法方面遇到了困难。任何帮助或提示将是非常感谢的！

最好的，奥特曼

Answer 1

假设答案等于k (k > 0)。然后，对于一些奇怪的i，我们可以写：i + (i + 2) + (i + 4) + ... + (i + 2k - 2) = target。您可以看到这是算术级数的和，因此您可以使用一个众所周知的公式来计算它。应用我们可以得到的公式：i = target/k - k + 1。

根据这个公式，我建议以下算法：

1. 迭代k的值。
2. 如果target/k - k + 1是正奇数，请更新答案。

简单的实现。

int answer = -1;
for (int k = 1;; k++) {
    int i = target / k - k + 1;
    if (i <= 0) {
        break;
    }
    // Check if calculated i, can be the start of 'odd' sequence.
    if (target % k == 0 && i % 2 == 1) {
        answer = k;
    }
}

该算法的运行时间为O(sqrt(target))。

Answer 2

看一看模式：

1. 1求和，i = target
2. 对于两个求和，方程是2*i + 2 = target，所以i = (target - 2) / 2
3. 对于3个求和，方程是3*i + 6 = target，所以i = (target - 6) / 3
4. 对于4个求和，方程是4*i + 12 = target，所以i = (target - 12) / 4

显然，i在任何情况下都必须是一个奇数。

您可以计算出n求和的通用表达式，并将其简化为显示算法，但您可能已经看到了一个算法.

应用@rossum的建议：

1. 1求和，2m + 1 = target
2. 对于两个求和，2m + 1 = (target - 2) / 2，所以m = (target - 4) / 4
3. 3求和，2m + 1 = (target - 6) / 3，so m = (target - 9) / 6
4. 对于4个求和，2m + 1 = (target - 12) / 4，so m = (target - 16) / 8

Answer 3

n奇数整数序列的和可以计算为平均值(中点m)乘以值数(n)，因此：

sum  =  5 + 7 + 9       =  m * n  =  7 * 3  =  21
sum  =  5 + 7 + 9 + 11  =  m * n  =  8 * 4  =  32

如果n是奇数，那么m就会是奇数，如果n是偶数，那么m就是偶数。

序列的first和last数可以计算为：

first  =  m - n + 1  =  8 - 4 + 1  =  5
last   =  m + n - 1  =  8 + 4 - 1  =  11

其他有趣的公式：

m  =  sum / n
m  =  (first + last) / 2
last  =  first + (n - 1) * 2  =  first + 2 * n - 2
m  =  (first + first + 2 * n - 2) / 2  =  first + n - 1

最长的序列必须以最低可能的first值开始，意思是1，因此我们得到：

sum  =  m * n  =  (first + n - 1) * n  =  n * n

这意味着任何给定sum的最长序列最多只能是sqrt(sum) long。

所以从sqrt(sum)开始，向下搜索直到找到一个有效的n

/**
  * Returns length of sequence, or 0 if no sequence can be found
  */
private static int findLongestConsecutiveOddIntegers(int sum) {
    for (int n = (int)Math.sqrt(sum); n > 1; n--) {
        if (sum % n == 0) { // m must be an integer
            int m = sum / n;
            if ((n & 1) == (m & 1)) // If n is odd, mid must be odd. If n is even, m must be even.
                return n;
        }
    }
    return 0;
}

结果：

n  =  findLongestConsecutiveOddIntegers(160701)  =  391
m  =  sum / n  =  160701 / 391  =  411
first  =  m - n + 1  =  411 - 391 + 1  =  21
last   =  m + n - 1  =  411 + 391 - 1  =  801

从sqrt(160701) = 400.875...开始，结果出现在10迭代中(400到391，包括在内)。

结论：

最大数量的连续奇数整数等于160701：391

21 + 23 + 25 + ... + 799 + 801 = 160701