Finding a Set of Consecutive Odd Integers That Sum to a Given NumberDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/