Math Is Fun Forum

Hate Number Theory

Member

Registered: 2015-12-22

Posts: 11

Another number theory problem :(

2. a) Which positive integers can be represented as the sum of two or more consecutive positive integers? For instance, 1 and 2 cannot be represented this way, because the smallest thesum of two or more consecutive positive integers can be is 1 + 2 = 3. Thus 3 can be represented this way. So can 5050, because as Gauss showed as a boy, 1 + 2 + 3 + · · · +99 + 100 = 5050.
You must prove that every positive integer you include in your list can be represented as a sum of consecutive positive integers and every other positive integer cannot be so represented.
b) Which integers can be represented as the sum of two or more consecutive integers? Again, proof required.

I found that every single integer can be represented except numbers that are 2^n. I have used patterns to find this. I need help proving that either every integer that is 2^n cannot be represented as the sum of two or more consecutive positive integers.

zetafunc

Moderator

Registered: 2014-05-21

Posts: 2,436

Website

Re: Another number theory problem :(

What happens if you try to write 2^n as a sum of an odd number of consecutive numbers?

What happens if you try to write 2^n as a sum of an even number of consecutive numbers?

If you can answer these two questions, then you're done.

Hate Number Theory

Member

Registered: 2015-12-22

Posts: 11

Re: Another number theory problem :(

Can somebody please help me on this problem?

zetafunc

Moderator

Registered: 2014-05-21

Posts: 2,436

Website

Re: Another number theory problem :(

Suppose that 2^n can be written as an odd number of consecutive integers. Then trivially you can write such a sum as a product of its average and the number of integers you used. But it isn't hard to show that the average of an odd number of consecutive integers is an integer -- therefore, you have a product of an integer (which may be odd or even), and an integer which is definitely odd. Thus, 2^n has an odd factor, which is a contradiction (for n non-zero, of course).

The other case is done similarly.

Hate Number Theory

Member

Registered: 2015-12-22

Posts: 11

Re: Another number theory problem :(

Never mind

phanthanhtom

Member

Registered: 2012-06-22

Posts: 290

Re: Another number theory problem :(

Perhaps a more straightforward way to present the problem is:

Suppose an integer n can be written as the sum of x+1 consecutive positive integers: a, a+1, a+2, ..., a+x.

Case 1: x is even (x+1 is odd)

Suppose x = 2k then n = a + (a+1) + ... + (a+2k) = (a+k)(2k+1) (you can prove this formula) and of course a+k >= k+1. This means that a number n can be written as the sum of an odd number of consecutive positive integers if and only if it has an odd factor (a factor of the form 2k+1) and when you divide n by that odd factor, the quotient is at least half of the odd factor plus 0.5 (i.e. >= (2k+1)/2+0.5 = k+1). That odd factor must obviously be at least 3 (since x >= 2, k >= 1)

Case 2: x is odd (x+1 is even) (x >= 3)

Suppose x = 2k - 1 (k>=2) then n = a + (a+1) + ... + (a+2k-1) = k(2a + 2k - 1) (you can prove this formula as well) and you must have 2a + 2k - 1 >= 2 + 2k - 1 = 2k + 1. In this case, n still need  to have an odd factor (2a + 2k - 1), but when you divide n by that odd factor, the quotient is at most half of the odd factor minus 0.5 (k = (2k+1)/2 - 0.5 <= (2a + 2k - 1)/2 - 0.5). That odd factor is 2a + 2k - 1 >= 2k + 1 >= 5. (the case for that odd factor is 3 would be a small, trivial addition, since then a+k = 2 and the only solution would then be x = 6, which can be represented in another way: 1 + 2 + 3).

When you combine the cases above, n can be written as a sum of consecutive positive integers if and only if it has an odd factor other than 1. Therefore the only positive integers incapable of being written as such a sum are the powers of 2 (which have no odd factor other than 1).