连续自然数之和的数 -Beauty of Programming

比咕网 | 关注搜索和自然语言处理技术

知道：

1＋2＝3；

4＋5＝9；

2＋3＋4＝9；

等式的左边都是两个或两个以上连续的自然数相加，那么是不是所有的整数都可以写成这样的形式呢？稍微考虑一下，我们发现，4、8等数并不能写成这样的形式。
问题1：写一个程序，对于一个64位正整数，输出它所有可能的连续自然数（两个及以上）之和的算式。
问题2：大家在测试上面程序的过程中，肯定会注意到有一些数字不能表达为一系列连续的自然之和，例如32好像就找不到，那么，这样的数字有什么规律呢？能否证明你的结论？
问题3：在64位正整数范围内，子序列数目最多的数是哪一个？这个问题要用程序蛮力搜索，恐怕要运行很长的时间，能否用数学知识推导出来？

就刚刚那个笨方法，我们明显觉得，很多数试探到ａ/２的数就差不多了，白费力计算不少不必要的数字，不妨来用数学公式推导一下，看能不能优化一下计算量

http://blog.csdn.net/yutianzuijin/article/details/10300067

将一个正整数表示成连续自然数之和，即N=s+(s+1)+(s+2)+…+(e-1)+e。利用等差数列求和公式，我们有



也即2N=(s+e)(e-s+1),该等式表示可以将2N分解成两个正整数的乘积。我们设x=s+e, y=e-s+1(其中x>y)。利用x、y我们可以求解获得s和e：


因为s和e都是整数，因而为了使上面的式子能整除，则x和y必须一奇一偶。因为2N=xy，2N含有偶因子，所以N必须含有奇因子才能使等式成立。这也就证明了N能表示成连续自然数的充要条件：N必须含有奇数因子，问题二得证。

利用公式（2），我们即可获得正整数N的一个连续自然数序列。为了输出所有的连续自然数序列，我们需要获得所有的x和y组合，也即求2N的所有因子组合。我们可以利用算法基本定理将2N分解成有限个质数的乘积：

我们将2N按照质因子进行分解，由于x和y只有一个偶数，所以2N的分解式中质因子2的所有组合都只能在其中一个数中，否则x和y都是偶数。不妨假设x是偶数，则

其中。由此我们可以知道，2N的所有质因子组共有(j+1) (k+1)…组。由于当x等于2N时，y等于1，此时的连续自然数个数为1，小于2，所以满足条件的连续自然数序列个数为：(j+1) (k+1)…-1，这就回答了问题一，我们可以首先获得2N的所有质因子分解，然后组合质因子并满足x>y即可获得所有的序列。

问题三按照网上的资料，有两种理解方式：1）、可以表示为最多个序列的那个数；2）、序列中项最多的那个数。但是按照题意其实应该是第一种理解方式。由于质因子2只能在x和y的某一个数中，对质因子分解不起作用，所以为了让序列个数尽可能多，N的质因子中不能包含2。因此若让子序列个数最多，则即(j+1) (k+1)…最大。通过简单分析我们可以获得具有最多序列个数的正整数j、k等质因子指数的两个性质：

性质一可以通过替换来证明，假设当前的最大序列个数不满足性质一，设第一个不满足性质的两个指数为a和b，满足a<b。由于序列个数为(j+1) ∙ (k+1) ∙…，我们通过将两个质因子的指数交换可以获得相同的序列个数。此外，由于前面的质因子小，交换之后总的乘积会变小，从而可能产生一个更大的指数，使序列个数更多。通过这样依次交换不满足性质的相邻两个指数，最终我们会得到满足性质一并且使序列个数最多的指数序列。这也与经验相吻合，要想使序列个数尽可能多，则正整数必须尽量少含有大的质因子。对于性质二，当正整数只包含质因子3时，质因子之和最大，此时为40。而当正整数含有越多较大的质因子时，则质因子之和就越小，在满足性质一的前提下，当正整数等于3 ∙5 ∙…∙53时，和最小，此时共有15个质因子，含有的序列个数为2^15-1。该正整数含有的序列个数已经非常多，但不一定是最多，例如将53替换为27，则序列个数升为5∙2^13-1。如果我们继续替换，将3^4 ∙5 ∙…∙47变为3^3 ∙5^2 ∙…∙47，则序列个数又升为6∙2^13-1。该数可能已经是具有最多序列的数，但是要想获得准确的最大序列个数，我们还需要利用性质一二去遍历所有可能的情况。如果按照第二种理解方式，则我们可以证明具有最多项的数N的最多项必从1开始。假设最多项不从1开始而是从s（s>1）开始，则我们可以将该最多项的每一项均减去s-1，则最多项等价于从1开始的最多项，也即我们至少可以构造和之前的最多项一样长的新序列。此外，由于每一项均减少了s-1，如果此时减少的和大于最多项的最大项，我们还可以添加新的项到最多项的末尾，产生更长的最多项。

Read full article from 比咕网 | 关注搜索和自然语言处理技术