和为n的连续自然数序列

题目：输入一个正数n，输出所有和为n的连续正数序列，例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6、7-8。

思路1：我们用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1，big初始化为2，如果从small到big的序列的和大于n的话，我们向右移动small，相当于从序列中去掉较小的数字。如果从small到big的序列的和小于n的话，我们向右移动big，相当于向序列中添加big的下一个数字，一直到small等于(1+n)/2，因为序列中至少要有两个数字。

 

view plainprint?

1. void FindContinuousSequence(int n)  
2. {  
3.     assert(n >= 3);  
4.   
5.     int small = 1;   
6.     int big = 2;  
7.     int mid = (1+n)/2;  
8.     int sum = small+big;  
9.     while(small < mid)  
10.     {  
11.         if(sum == n)  
12.         {  
13.             cout << small << "-" << big << endl;  
14.             sum -= small;  
15.             small++;  
16.         }  
17.         else if(sum > n)  
18.         {  
19.             sum -= small;  
20.             small++;  
21.         }  
22.         else  
23.         {  
24.             big++;  
25.             sum += big;  
26.         }  
27.     }  
28. }  

 

思路2：按照等差数列计算，连续数列有i个数，首数为x，和为n=(2x+i-1)*i/2，解得x=(2n/i-i+1)/2，注意x>0且i为整数，可得i的取值范围为[2, sqrt(2*n)]，又x为整数，故2n/i为整数，且(2n/i-i+1)/2为整数。

 

view plainprint?

1. void FindContinuousSequence(int n)  
2. {  
3.     assert(n >= 3);  
4.       
5.     for(int i=2; i<=sqrt(2*n); i++)  
6.     {  
7.         if((2*n)%i == 0)  
8.         {  
9.             int temp = 2*n/i-i+1;  
10.             if(temp%2 == 0)  
11.             {  
12.                 cout << temp/2 << "-" << temp/2+i-1 << endl;  
13.             }  
14.         }  
15.     }  
16. }  

扩展题目1：某些数n并不能表示为一系列连续的自然数之和，例如4、8、32就不行，那么这样的数有什么规律呢？能否证明你的结论？

思路：2的整数次幂不能表示为一系列连续的自然数之和，如上思路2所示，若要2n/i为整数，则i必为偶数，而当i为偶数时，2n/i-i为偶数，2n/i-i+1为奇数，此时(2n/i-i+1)/2就不可能为整数了，即不存在连续自然数之和了，故命题得证。

扩展题目2：在64位正整数范围内，子序列数目最多的是哪一个？能否用数学知识推导出来？求思路

（转载）