Not a power of 2 implies Niceness

(This is a proof for part of a problem given out as part of Justin Lanier’s smooc. For my fellow smoocsketeers, spoilers below.)

From the problem set:

Let’s call a number n “nice” if it can be expressed as a sum of two or more consecutive positive integers.
For example, the expressions 5 = 2+3 and 6 = 1+2+3 show that 5 and 6 are nice numbers.
Which numbers are nice? Justify your answer.

We claim that a positive integer is nice if and only if it is not a power of 2. John Burk has an excellent post explaining why powers of 2 cannot be nice here. We prove here that if a positive integer is not a power  of 2, then it must be nice.

Proof: Let n be a positive integer that is not a power of 2. This means that n = 2^k\cdot m, where k is some nonnegative integer and m is an odd integer greater than 1. Note that m/2 cannot be equal to 2^k since m/2 is not even an integer.

Case 1: m/2 > 2^k.

Then n is nice since we can make n by adding up the 2^{k+1} consecutive positive integers which are centered at m/2. In other words,

(m/2+1/2-2^k) + (m/2+1/2-(2^k-1)) + \cdots +(m/2-1/2)+(m/2+1/2)+\cdots +(m/2-1/2+2^k)= n.

Case 2: m/2 < 2^k.

Then n is again nice since we can add up the m consecutive positive integers centered at 2^k. In other words,

(2^k-(m/2-1/2)) + \cdots + 2^k+ \cdots (2^k+(m/2-1/2)) = n.

QED.

Here’s the fun part to think back on. HOW did we use the fact that we had an odd factor? Well, in both cases we needed m/2 to not be an integer.

How did we use the fact that we factored n into it’s “even” part 2^k and its odd factor. Did we ever use the fact that m was the largest odd factor of n? NO.

From the problem set:

Some numbers are “very nice”, in the sense that they are nice in more than one way.
For example, 15 is very nice because 15 = 1+2+3+4+5 = 4+5+6 = 7+8.
Which numbers are very nice? Explain.

We claim now that numbers which have more than one odd factor greater than one are “very nice.” We prove this by modifying the previous proof.

Let n be a positive integer that is not a power of 2. This means that n = ab for some integer a that is either 1 or even and some odd integer b > 1.

Case 1: b/2 > a.

Then we construct a sum as in Case 1 of the previous proof. This sum has 2a terms, centered at b/2.

Same deal with Case 2: b/2 < a. This sum has b terms, centered at a.

Now, if n has more than one odd factor > 1, that’s like saying there’s more than one choice for b. It remains only to show that each choice of b yields a different sum.

Say we wanted to show that the sum formed by using b and the sum formed by using some other b’ are different. If they both fall into Case 1 the two sums have a different number of terms since the corresponding a = n/b and a’ = n/b’ will be different, resulting in sums of length 2a versus 2a’. If they both fall into Case 2, the two sums again have a different number of terms since they have b and b’ terms, and we assumed b was not equal to b’. If one falls into Case 1 and the other into Case 2, the two sums yet again have a different number of terms, this time since one sum has an odd number of terms and the other has an even number of terms.

Thus we have shown not only that the “very nice” numbers are those with more than one odd factor greater than one, but that the number of ways to express any positive integer as the sum of consecutive positive integers is at least equal to the number of odd factors > 1 of that integer.

For more thoughts on very nice numbers, see this.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: