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

### Finding a Set of Consecutive Odd Integers That Sum to a Given Number

```Date: 02/21/2004 at 21:28:23
From: Chris
Subject: sum of consecutive odd numbers equaling a given number

Given a number n, which is the sum of some consecutive odd numbers, is
there an efficient way to find this span of odd numbers?  We will
consider the first odd number to be 3, not 1.

For example:

For n = 33, the answer would be 9 + 11 + 13.

For n = 57, the answer would be 17 + 19 + 21.

I currently use a method which works well for small values of n, but
would be very inefficient for large ones.  Here's my method.

For 33, add consecutive odd numbers until the sum is greater than 33:

3 + 5 + 7 + 9 + 11 = 35

35 - 33 = 2, which is less than anything that can be subtracted from
the current list of numbers.  Add the next number, which is 13 in this
case:

3 + 5 + 7 + 9 + 11 + 13 = 48

48 - 33 = 15, so I have 15 too much in my list.  3 + 5 + 7 = 15, so
subtract 3, 5, and 7 from the list.  Now I'm left with 9 + 11 + 13 =
33.  Since I can only really add 1 number each time I advance, this
algorithm will not be efficient for large n.  Is there a better way?

```

```
Date: 02/21/2004 at 23:28:48
From: Doctor Greenie
Subject: Re: sum of consecutive odd numbers equaling a given number

Hi, Chris--

That is a very interesting algorithm you found for doing this job.  It
does have some drawbacks, though.  In addition to being very
inefficient for large numbers, it also does not find all the possible

There are at least a couple of ways of attacking your problem which
are more efficient and which (if used properly) find all the answers
for a given "n".  Below are descriptions of two such methods, along
with several examples.

Method 1:  using the idea of the sum of an arithmetic series

Any time you have a sum of consecutive odd integers, you have an
arithmetic series--a sum of a sequence of numbers in which the
difference between successive elements is constant.  The sum of ANY
group of numbers is

(average of all the numbers) * (how many numbers there are)

For an arithmetic series, it is important to note that, because the
elements are equally spaced, the average of all the numbers is the
"one in the middle".  So for an arithmetic series, the sum is

("number in the middle") * (how many numbers there are)

If we have an arithmetic series consisting of consecutive odd
integers, then there are two cases to consider:

(1) If the number of terms is odd, then the "number in the middle" is
one of those odd numbers.  In this case, the sum of the series of
consecutive odd numbers is then the product of two odd numbers.

(2) If the number of terms is even, then the "number in the middle" is
not one of the consecutive odd integers; instead, it is the number
halfway between two of them--in other words, it is an even number.  So
in this case, the sum of the series of consecutive odd numbers is the
product of two even numbers.

The preceding analysis tells us that, whenever we can express an
integer n as the product either of two odd integers or of two even
integers, then we can find a sequence of consecutive odd integers
whose sum is n and in which the number of elements is one of the two
factors.

A few examples:

n = 33 (one of your examples)

33 = 11*3

This means we can express 33 as the sum of 3 consecutive odd integers
whose average is 11.  11 is the middle number, leaving two other
numbers--one on each side of 11.  So the numbers are 9, 11, and 13.

(Note: with 33 = 11*3, we can also express 33 as the sum of 11
consecutive odd integers whose average is 3.  The numbers are -7, -5,
-3, -1, 1, 3, 5, 7, 9, 11, and 13.  In this sum, the negative numbers
"cancel out" the positive odd integers through 7, leaving the other
solution consisting of 9, 11, and 13.  But apparently you aren't
considering negative integers in your problem, so I won't consider
solutions involving negative integers from here on.)

n = 45

45 = 15*3

So we can write 45 as the sum of 3 consecutive odd integers whose
average is 15:  13, 15, 17.

n = 45 again

45 = 9*5

So we can also write 45 as the sum of 5 consecutive odd integers whose
average is 9:  5, 7, 9, 11, 13.

Note your algorithm finds the second of these solutions, because it
starts with a smaller number.

n = 40

40 = 20*2

So we can write 40 as the sum of 2 consecutive odd integers whose
average is 20:  19, 21.

n = 40 again

40 = 10*4

So we can write 40 as the sum of 4 consecutive odd integers whose
average is 10:  7, 9, 11, 13.

n = 42

42 = 21*2
42 = 14*3
42 = 7*6

None of these factorizations consists of either two odd or two even
integers; this means that 42 cannot be written as the sum of
consecutive odd integers.

Method 2:  using the fact that the sum of the first "k" positive odd
integers is k^2

Suppose we have the series of consecutive odd integers 9, 11, 13 (the
solution to your example where the sum is n = 33).  "9" is the 5th
positive odd integer, and 13 is the 7th positive odd integer.  So the
sum

9 + 11 + 13

can be considered as a difference between two sums:

(1+3+5+7+9+11+13) - (1+3+5+7)

So the sum 9+11+13 can be considered to be the difference between the
sum of the first 7 odd integers and the sum of the first 4 odd
integers.  But the sum of the first 7 odd integers is 7^2 = 49, and
the sum of the first 4 odd integers is 4^2 = 16.  So

9+11+13 = (1+3+5+7+9+11+13) - (1+3+5+7) = 7^2 - 4^2 = 49 - 16 = 33

Now let's turn this all around and suppose we start with the sum 33
and want to express it as the sum of consecutive odd integers.  We
first want to express 33 as the difference of two squares:

33 = x^2 - y^2 = (x + y)(x - y)

Now we try to write 33 as the product of two integers and then solve
the equations which make those two integers equal to (x + y) and
(x - y):

33 = 11*3 = (7 + 4)(7 - 4) = 7^2 - 4^2

This tells us that 33 is the difference between the sum of the first
7 odd integers and the sum of the first 4 odd integers--i.e., it is
the sum of the 5th through 7th odd integers--which are 9, 11, and 13.

I will show this method for the other examples I worked with the
preceding method....

n = 45

45 = 15*3 = (9 + 6)(9 - 6) = 9^2 - 6^2

This tells us that 45 is the difference between the sum of the first
9 odd integers and the sum of the first 6 odd integers--i.e., it is
the sum of the 7th through 9th odd integers--which are 13, 15, and 17.

n = 45 again

45 = 9*5 = (7 + 2)(7 - 2) = 7^2 - 2^2

This tells us that ... 45 is the sum of the 3rd through 7th odd
integers--which are 5, 7, 9, 11, and 13.

n = 40

40 = 20*2 = (11 + 9)(11 - 9) = 11^2 - 9^2

This tells us that ... 40 is the sum of the 10th through 11th odd
integers--which are 19 and 21.

n = 40 again

40 = 10*4 = (7 + 3)(7 - 3) = 7^2 - 3^2

This tells us that ... 40 is the sum of the 4th through 7th odd
integers--which are 7, 9, 11, and 13.

n = 42

42 = 21*2
42 = 14*3
42 = 7*6

None of these factorizations can be written as (x + y)(x - y) where x
and y are integers.  So again we find 42 cannot be written as the sum
of consecutive odd integers.

Note that if x and y are integers, (x + y) and (x - y) are either both
odd or both even, exactly corresponding to the restriction on the
factorization of n we found using the first method.

I hope at least some of this helps, and that it is not too much for
you to digest.  Please write back if you have any further questions
on any of this.

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory

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