Given a number N, find the number of ways to write it as a sum of two or more consecutive integers

Here is the problem that tagged as dynamic-programming (Given a number N, find the number of ways to write it as a sum of two or more consecutive integers) and example 15 = 7+8, 1+2+3+4+5, 4+5+6

I solved with math like that :

a + (a + 1) + (a + 2) + (a + 3) + ... + (a + k) = N

(k + 1)*a + (1 + 2 + 3 + ... + k) = N

(k + 1)a + k(k+1)/2 = N

(k + 1)*(2*a + k)/2 = N

Then check that if N divisible by (k+1) and (2*a+k) then I can find answer in O(sqrt(N)) time

Here is my question how can you solve this by dynamic-programming ? and what is the complexity (O) ?

P.S : excuse me, if it is a duplicate question. I searched but I can find

5 Answers
5

We can use dynamic programming to calculate the sums of 1+2+3+...+K for all K up to N. sum[i] below represents the sum 1+2+3+...+i.

sum[i]

sum = [0]
for i in 1..N:
append sum[i-1] + i to sum


With these sums we can quickly find all sequences of consecutive integers summing to N. The sum i+(i+1)+(i+2)+...j is equal to sum[j] - sum[i] + 1. If the sum is less than N, we increment j. If the sum is greater than N, we increment i. If the sum is equal to N, we increment our counter and both i and j.

sum[j] - sum[i] + 1

j

i

i

j

i = 0
j = 0
count = 0
while j <= N:
cur_sum = sum[j] - sum[i] + 1
if cur_sum == N:
count++
if cur_sum <= N:
j++
if cur_sum >= N:
i++


There are better alternatives than using this dynamic programming solution though. The sum array can be calculated mathematically using the formula k(k+1)/2, so we could calculate it on-the-fly without need for the additional storage. Even better though, since we only ever shift the end-points of the sum we're working with by at most 1 in each iteration, we can calculate it even more efficiently on the fly by adding/subtracting the added/removed values.

sum

i = 0
j = 0
sum = 0
count = 0
while j <= N:
cur_sum = sum[j] - sum[i] + 1
if cur_sum == N:
count++
if cur_sum <= N:
j++
sum += j
if cur_sum >= N:
sum -= i
i++


For odd N, this problem is equivalent to finding the number of divisors of N not exceeding sqrt(N). (For even N, there is a couple of twists.) That task takes O(sqrt(N)/ln(N)) if you have access to a list of primes, O(sqrt(N)) otherwise.

sqrt(N)

O(sqrt(N)/ln(N))

O(sqrt(N))

I don't see how dynamic programming can help here.

In order to solve the problem we will try all sums of consecutive integers in [1, M], where M is derived from M(M+1)/2 = N.

int count = 0
for i in [1,M]
for j in [i, M]
s = sum(i, j) // s = i + (i+1) + ... + (j-1) + j
if s == N
count++
if s >= N
break
return count


Since we do not want to calculate sum(i, j) in every iteration from scratch we'll use a technique known as "memoization". Let's create a matrix of integers sum[M+1][M+1] and set sum[i][j] to i + (i+1) + ... + (j-1) + j.

sum(i, j)

sum[M+1][M+1]

sum[i][j]

for i in [1, M]
sum[i][i] = i



int count = 0
for i in [1, M]
for j in [i + 1, M]
sum[i][j] = sum[i][j-1] + j
if sum[i][j] == N
count++
if sum[i][j] >= N
break
return count

int count = 0
for i in [1, M]
for j in [i + 1, M]
sum[i][j] = sum[i][j-1] + j
if sum[i][j] == N
count++
if sum[i][j] >= N
break
return count

The complexity is obviously O(M^2), i.e. O(N)

1) For n >= 0 an integer, the sum of integers from 0 to n is n*(n+1)/2. This is classic : write this sum first like this :
S = 0 + 1 + ... + n
and then like this :
S = n + (n-1) + ... + 0
You see that 2*S is equal to (0+n) + (1 + n-1)) + ... + (n+0) = (n+1)n, so that S = n(n+1)/2 indeed. (Well known but is prefered my answer to be self contained).

2) From 1, if we note cons(m,n) the sum m+(m+1)+...(n-1)+n the consecutive sum of integers between posiive (that is >=0) such that 1<=m<=n we see that :
cons(m,n) = (0+1+...+n) - (0+1+...+(m-1)) which gives from 1 :
cons(m,n) = n*(n+1)/ - m(m-1)/2

3) The question is then recasted into the following : in how many ways can we write N in the form N = cons(m,n) with m,n integers such that 1<=m<=n ? If we have N = cons(m,n), this is equivalent to m^2 - m + (2N -n^2 -n) = 0, that is, the real polynomial T^2 - m + (2N -n^2 -n) has a real root, m : its discriminant delta must then be a square. But we have :

delta = 1 - 3*(2*N - n^2 - n)


And this delta is an integer which must be a square. There exists therefore an integer M such that :

delta = 1 - 3*(2*N - n^2 - n) = M^2


that is

M^2 = 1 - 6*N + n(n+1)


n(n+1) is always dividible by 2 (it's for instance 2 times our S from the beginning, but here is a more trivial reason, among to consecutive integers, one must be even) and therefore M^2 is odd, implying that M must be odd.

4) Rewrite or previous equation as :

n^2 + n + (1-6*N - M^2) = 0


This show that the real polynomial X^2 + X + (1-6*N - M^2) has a real zero, n : its discriminant gamma must therefore be a square, but :

gamma = 1 - 4*(1-6*N-M^2)


and this must be a square, so that here again, there exist an integer G such that

G^2 = 1 - 4*(1-6*N-M^2)

G^2 = 1 + 4*(2*N + m*(m-1))


which shows that, as M is odd, G is odd also.

5) Substracting M^2 = 1 - 4*(2*N - n*(n+1)) to G^2 = 1 + 4*(2*N + m*(m-1))) yields to :

G^2 - M^2 = 4*(2*N + m*(m-1)) + 4*(2*N -n*(n+1))
= 16*N + 4*( m*(m-1) - n*(n+1) )
= 16*N - 8*N (because N = cons(m,n))
= 8*N


And finally this can be rewritten as :

(G-M)*(G+M) = 8*N, that is

[(G-M)/2]*[(G+M)/2] = 2*N


where (G-M)/2 and (G+M)/2 are integers (G-M and G+M are even since G and M are odd)

6) Thus, at each manner to write N as cons(m,n), we can associate a way (and only one way, as M and G are uniquely determined) to factor 2*N into the product x*y, with x = (G-M)/2 and y = (G+M)/2 where G and M are two odd integers. Since G = x + y and M = -x + y, as G and M are odd, we see that x and y should have opposite parities. Thus among x and y, one is even and the other is odd. Thus 2*N = x*y where among x and y, one is even and the other is odd. Lets c be the odd one among x and y, and d be the even one. Then 2*N = c*d, thus N = c*(d/2). So c is and odd number dividing N, and is uniquely determined by N, as soon as N = cons(m,n). Reciprocally, as soon as N has an odd divisor, one can reverse engineer all this stuff to find n and m.

7) *Conclusion : there exist a one to one correspondance between the number of ways of writing N = cons(m,n) (which is the number of ways of writing N as sum of consecutive integers, as we have seen) and the number of odd divisors of N.*

8) Finally, the number we are looking for is the number of odd divisors of n. I guess that solving this one by DP or whatever is easier than solving the previous one.

The accepted answer was great but the better approach wasn't clearly presented. Posting my java code as below for reference. It might be quite verbose, but explains the idea more clearly. This assumes that the consecutive integers are all positive.

private static int count(int n) {
int i = 1, j = 1, count = 0, sum = 1;
while (j<n) {
if (sum == n) { // matched, move sub-array section forward by 1
count++;
sum -= i;
i++;
j++;
sum +=j;
} else if (sum < n) { // not matched yet, extend sub-array at end
j++;
sum += j;
} else { // exceeded, reduce sub-array at start
sum -= i;
i++;
}
}
return count;
}


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.