Tuesday, September 22, 2009

Sum of consecutive numbers in seven ways

Find an integer that can be expressed as the sum of two or more consecutive positive integers in exactly seven ways. (Bonus: find the smallest such integer.)

2 comments:

  1. The smallest such integer is 105.

    It turns out that the number of ways to express N as the sum of one or more consecutive positive integers is equal to the number of odd divisors of N. We can demonstrate this in several steps.

    Step 1. The number of ways to write N as a sum of consecutive integers is equal to the number of ways to write N as the sum of an odd number of integers (including negative integers and 0).

    Proof: For each expression N=a+...+b there is a corresponding expression N=(1-a)+...+b. Exactly one of these expressions starts at a positive integer, and exactly one of them has an odd number of terms. Therefore there is a one-to-one correspondence between sums starting at a positive integer and sums with an odd number of terms.

    Step 2: The number of ways to express N as the sum of an odd number of consecutive integers is equal to the number of positive integer divisors of N.

    Proof: If d is an odd divisor of N, then N is the sum of d consecutive integers, with N/d as the middle term. Conversely, if N is the sum of d consecutive integers where d is odd, then N/d is the middle term, thus d is a divisor of N.

    ReplyDelete
  2. We can give a simple formula for the number of odd divisors of N, via prime factorization.

    Let N = 2^a * 3^b * 5^c * 7^d * ...
    If D is an odd factor of N, then the exponent of 2 in the prime factorization is 0, the exponent of 3 is between 0 and b1, the exponent of 5 is between 0 and c1, and so on. Consequently, there are
    (b+1)*(c+1)*(d+1)*... odd factors of N.

    Now, we need to find the smallest number
    N = 2^a * 3^b * 5^c * 7^d * ... so that
    (b+1)*(c+1)*(d+1)*... = 8. It is easy to check that the minimum occurs when b=c=d and the other exponents are 0.

    Therefore the smallest possible value of N is
    3*5*7, or 105.

    ReplyDelete