Finding a Series Given the Sum

Date: 09/27/1999 at 00:32:19
From: Mike
Subject: Subrange Sums

Dear Dr. Math,

This is probably a fairly simple question, for which I can't find a 
formula. Given an input (integer) number, let's call it x, I must find 
all subrange sums that equal the integer x.

I am given that in the case x = 1986, the subrange sums are:
{160 ... 171}, {495 ... 498}, and {661 ... 663}.

I have figured out that in the first set {160 ... 171} there are 12 
integers making up the subrange sum (160 through 171) and that 
1986/12 = 165.5, which is the midpoint of the subrange sum. I have 
also figured this out for the next two sets. However, I can't figure 
out a general formula is for this. Can you please help?

Thanks.

Date: 10/02/1999 at 12:54:29
From: Doctor TWE
Subject: Re: Subrange Sums

Hi Mike. Thanks for writing to Dr. Math.

You ask an interesting question. To generalize the procedure, I first 
took a look at subranges of a given length and worked backwards. For 
subranges of length 2 we have:

     1 + 2 = 3
     2 + 3 = 5
     3 + 4 = 7
     4 + 5 = 9

and so on. Each subrange sum is 2 greater than the previous, because 
we're adding 1 to each of the 2 numbers being added. We can generalize 
this by saying that all subrange sums of length 2 are in the form:

     2z + 1

where z is any integer. If we want to restrict the subrange to only 
sums of positive integers, then we can add the restriction z >= 1.

Next, I looked at subranges of length 3. I got:

     1 + 2 + 3 = 6
     2 + 3 + 4 = 9
     3 + 4 + 5 = 12
     4 + 5 + 6 = 15

and so on. Each subrange sum is 3 greater than the previous, because 
we're adding 1 to each of the 3 numbers being added. We can generalize 
this by saying that all subrange sums of length 3 are in the form:

     3z

where z is any integer. Again, if we want to restrict the subrange 
to only sums of positive integers, then we can add the restriction 
z >= 2.

Looking at subranges of length 4, I got:

     1 + 2 + 3 + 4 = 10
     2 + 3 + 4 + 5 = 14
     3 + 4 + 5 + 6 = 18
     4 + 5 + 6 + 7 = 22

and so on. Each subrange sum is 4 greater than the previous, because 
we're adding 1 to each of the 4 numbers being added. We can generalize 
this by saying that all subrange sums of length 4 are in the form:

    4z + 2

where z is any integer. Again, if we want to restrict the subrange 
to only sums of positive integers, then we can add the restriction 
z >= 2.

Looking at subranges of length 5, I got:

     1 + 2 + 3 + 4 + 5 = 15
     2 + 3 + 4 + 5 + 6 = 20
     3 + 4 + 5 + 6 + 7 = 25
     4 + 5 + 6 + 7 + 8 = 30

and so on. Each subrange sum is 5 greater than the previous, because 
we're adding 1 to each of the 5 numbers being added. We can generalize 
this by saying that all subrange sums of length 5 are in the form:

     5z

where z is any integer. Again, if we want to restrict the subrange 
to only sums of positive integers, then we can add the restriction 
z >= 3.

We can start to see a pattern here. For subranges of odd length n, the 
subrange sum is of the general form:

     n*z

For subranges of even length n, the subrange sum is of the general 
form:

     n*z + n/2

In both cases, z is an integer (greater than or equal to n/2 rounded 
up if we want to restrict the subranges to only positive integers). 
Can you see why even and odd length subranges are different? (Think 
about "pairing up" the low and high values in the subrange.)

Enlightening, but does this help? We want to find an algorithm (a 
method) for finding all the subranges whose sum is a given value k.

To start with, we know that k will be the sum of an odd length n 
subrange if k is of the form n*z; i.e. that k is divisible by an odd 
integer n. Thus, we can test for divisibility by all odd integers less 
than k. Can we eliminate some of these? (For example, though 500 is 
divisible by 125, surely a sequence of 125 numbers that add to 500 has 
to include negative values.)

For even length subranges, we know that k will be the sum of an even 
length n subrange if k is of the form n*z + n/2; i.e. when k is 
divided by an even integer n, the fractional part is 1/2. So we can 
test for the fraction of 1/2 when dividing by any even integer less 
than k.

Once we know what length the valid subranges are, you observed that 
dividing your number k by n gives the midpoint of the range. From that 
information, determining an algorithm for the starting and ending 
numbers of the subrange should not be too difficult.

Let's do an example. Suppose we want to know all of the subranges 
whose sum is 500.

We first test 500 for divisibility by odd integers 1 through 499, and 
test for a remainder of 1/2 when dividing by even integers 2 through 
498. We find that 500 is divisible by 5, 25 and 125; and produces a 
fraction of 1/2 when divided by 8, 40 and 200.

   500/5   = 100,  so  100 is the midpoint and 500 = Sum(98 ... 102),

   500/25  = 20,   so   20 is the midpoint and 500 = Sum(8 ... 32),

   500/125 = 4,    so    4 is the midpoint and 500 = Sum(-58 ... 66),
      (not allowed if only positive integers are used)

   500/8   = 62.5, so 62.5 is the midpoint and 500 = Sum(59 ... 66),

   500/40  = 12.5, so 12.5 is the midpoint and 500 = Sum(-7 ... 32),
      (not allowed if only positive integers are used)

   500/200 = 2.5,  so  2.5 is the midpoint and 500 = Sum(-97 ... 102)
      (not allowed if only positive integers are used)

Note that each of the positive-only subranges has a corresponding 
positive-and-negative subrange. If the positive-only subrange is from 
a to b, the corresponding positive-and-negative subrange is from 
-(a-1) to b. Can you see why this is so? 

Can we simplify this further? Can we test for divisibility by n (or a 
remainder of 1/2) with a more systematic method than trial-and-error? 
If we can, it will greatly simplify the algorithm. Good luck with 
this!

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/