Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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/
```
Associated Topics:
College Algorithms
College Number Theory
High School Number Theory
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search