Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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 
answers for a given "n"; it always finds a single answer.

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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/