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