将整数分解为连续正整数之和

将一个整数 N 分解为连续正整数之和，如 15 可以分解为：

15 = 1 + 2 + 3 + 4 + 5

15 = 4 + 5 + 6

15 = 7 + 8

=============================================

计算从 i 开始连续 k 个数之和：

sum = k * (2 * i + k - 1) / 2;

 

当 sum == N 时，有 k * k + (2 * i - 1) * k - 2 * n = 0 ，

 

变形为 i = ( 2*n / k - k + 1) / 2。

 

在 [2, 2*n / k - k + 1 > 0] 范围枚举 k 即可。

 

#!/usr/bin/python3
def spt(num):
	k = 2
	while 2 * num // k > k - 1:
		if 2 * num % k == 0:			
			tmp = 2 * num // k - k + 1
			if tmp % 2 == 0:
				i = tmp // 2
				print(num, ' = ', ' + '.join(map(str, [x for x in range(i, i + k)])))
		k += 1 # DO NOT forget !!!

 ===================================================

 2*n / k - k + 1 > 0  ===> k * k - k - 2 * N > 0 ===> (1 - sqrt(8 * N + 1)) / 2 < k < (1 + sqrt(8 * N + 1)) / 2

又 k >= 2， 所以 2 <= k < (1 + sqrt(8 * N + 1)) / 2 = 1/2 + sqrt(8 * N + 1) / 2 < sqrt((8 * N + 1) / 4) = sqrt(2 * n + 1/4) < sqrt(2 * N)

即，k 的枚举范围为 [2, sqrt(2 * N))