wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Sum of Consecutive numbers
        
(Message started by: BNC on Jan 26^th, 2003, 4:06am)

Title: Sum of Consecutive numbers
Post by BNC on Jan 26^th, 2003, 4:06am

Every number between 1000 and 2000 may be written as the sum of Consecutive numbers, except one.
What is this number?

Title: Re: Sum of Consecutive numbers
Post by Pietro K.C. on Jan 26^th, 2003, 7:11am

I like this one!

[hide]

The sum of N consecutive numbers is odd, if N is even, and it is divisible by N if N is odd. The latter is simple to prove using congruences, and the first is obvious.

Now, a number that is not odd and not divisible by any odd numbers would certainly fill the prescription. What could it be? Why, a power of 2! Hence, 1024 is our number.

[/hide]

// solution hidden by moderator 8:26 PM 1/27/2003

Title: Re: Sum of Consecutive numbers
Post by towr on Jan 26^th, 2003, 7:19am

sum(i, i, n, m) = sum(i, i, 0, m) - sum(i,i,0, n-1) = m*(m+1)/2 - (n-1)*n/2 = (m + n)*(m - n + 1)/2
either m+n or m-n+1 is even, so any number that is the sum of consecutive numbers has to be the product of two numbers, which means that it doesn't hold for any prime number..
So my guess would be it's a prime between 1000 and 2000..

Title: Re: Sum of Consecutive numbers
Post by towr on Jan 26^th, 2003, 8:01am

hmm.. of course any odd number is the sum of two consecutive numbers :p
(2n+1 = n + n+1)

Title: Re: Sum of Consecutive numbers
Post by Chronos on Jan 27^th, 2003, 4:30pm

We already covered a very similar question, in the Finger Gauges puzzle. Reasoning from there will suggest at least one answer to the puzzle, and I think it's safe to say that there aren't any more.

Title: Re: Sum of Consecutive numbers
Post by Icarus on Jan 27^th, 2003, 5:02pm

If n = (2m+1)k, then n= (k-m)+(k-m+1) +...+k+...(k+m).
So any number with an odd factor is the sum of consecutive integers. Pietro has already shown that every sum of consecutive integers has an odd factor.

Hence n is NOT a sum of consecutive integers if and only if n is a power of 2. 1024 is the only power of 2 between 1000 and 2000.

Title: Re: Sum of Consecutive numbers
Post by Chronos on Jan 29^th, 2003, 11:10am

Except that there might conceivably be other numbers which don't work, if negative integers are not allowed. I don't think that this will happen, but it needs to be considered.

Title: Re: Sum of Consecutive numbers
Post by Icarus on Jan 29^th, 2003, 8:07pm

Even if negatives are not allowed, the answer is the same: what positive integers are the sums of two or more consecutive natural numbers?

If n is a power of 2, then by Pietro's post it is impossible.

Let n=k(2m+1) with m>0. The expression I gave in my last post is all positive as long as m < k.

Now,
2m+1 =
m + m+1
m-1 + m+2
m-2 + m+3
. . .
m-k+1 + m+k

Summing these gives
n =k(2m+1) = m-k+1 + m-k+2 +...+ m + ... m+k

Which is all positive as long as m > k. So, n is a sum of consecutive positive integers iff it is a positive integer and not a power of 2.

Modified to remove erroneous first line.

Title: Re: Sum of Consecutive numbers
Post by towr on Jan 30^th, 2003, 12:04am

2 = -1 + 0 + 1 + 2 thus 2 is the sum of consecutive integers :p
And any other number likewise..

n = sum(i, i, -|n-1|, |n-1|) + n
0 is a special case, since any k!=0 will work in sum(i, i, -|k|, |k|) + 0

;D ;D

Title: Re: Sum of Consecutive numbers
Post by Icarus on Jan 30^th, 2003, 5:44pm

Good catch towr!

on 01/26/03 at 07:11:36, Pietro K.C. wrote:

The sum of N consecutive numbers is odd, if N is even...

I read this, checked the obvious case, and accepted it without looking closer until towr posted his counterexample.

The sum of N consecutive numbers is odd if N=2 mod 4
The sum of N consecutive numbers is even if N=0 mod 4.

Obviously Chronos is right: the puzzle requires restriction to non-negative integers. (My apologies for disputing this earlier. I have changed my last post to remove this unfortunate erroneous reply. :-[)

By my previous post, every number not a power of 2 is the sum of consecutive positive integers. So the only possible answer is 1024. However it has not been shown after all that 1024 is not also the sum of consecutive positive integers.

However: (m+1) + (m+2) + ... + (m+k) = km + k(k+1)/2 = k(2m+k+1)/2.

We are given that k>1.

So if k is odd, it is a factor of the sum. If k is even, (2m+k+1) is an odd factor of the sum provided 2m+k+1 != 1. But if we are restricted to positive integers, m > 0, and so 2m+k+1 > 2. Thus every sum of 2 or more positive integers is not a power of 2.

1024 is the unique answer to the (corrected) riddle.