PlanetMath: all positive integers are polite numbers except powers of two

To prove this theorem, it is necessary first to prove that most positive integers can be represented in this way and then to prove that there is no such representation for the powers of two.

Lemma 2. Any singly even number $n \equiv 2 \mod 4$ is the sum of four consecutive integers.

We rewrite

. The relevant four consecutive integers are

and

. We verify that

. Note that for

the consecutive integers are

, 0, 1 and 2, with the first of these being a negative number.

Given

, we rewrite

. Then

and

are the consecutive integers, verified with

Given

, we rewrite

. Then

and

are the consecutive integers, verified with

Lemma 5. All composite multiples of an odd prime

are the sum of

consecutive integers.

If $n = (m + 1) + (m + 2) + \ldots + (m + p)$ then clearly $n = mp + 1 + 2 + \ldots + p$ . Ignoring

and

for a moment, we can pair up each addend from 1 to

with another number in the range so the two of them add up to

, etc. Since

is even, no number is left out in this pairing up. Thus we have $\displaystyle \left( \frac{p - 1}{2} \right)p$ . Putting the last

back in we have $\displaystyle \left( \frac{p - 1}{2} + 1 \right)p = \left( \frac{p^2 - p}{2} + p \right) = \left( \frac{p^2 + p}{2} \right).$ This means that the

th triangular number is divisible by

. Putting

back in, it is now clear that since $\displaystyle n = mp + \left( \frac{p^2 + p}{2} \right)$ ,

is is divisible by

. The smallest multiple of

thus representable with a run of consecutive nonnegative integers is the

th triangular number, which is the sum of the integers from 0 to

Lemma 6. Any run of

consecutive integers, with

an odd prime, will add up to a multiple of

Breaking up the single run of

consecutive integers into

runs of

consecutive integers, it is clear by the previous lemma that each of those

runs add up to a multiple of

. Adding up

multiples of

gives yet another multiple of

With $n = (m + 1) + (m + 2) + \ldots + (m + 2^a)$ , the

s clearly add up to

. What of the

th triangular number? We can pair up almost all the numbers 1 to

so that they add up to

, etc. These add up to $(2^a - 2)2^a = 2^{2a} - 2^{a + 1}$ . But since

is even and

odd, there is a number left out, specifically $\frac{2^a}{2} = 2^{a - 1}$ . So we have $n = 2^a m + (2^{2a} - 2^{a + 1}) + 2^{a - 1}$ . All three addends are divisible by $2^{a - 1}$ but only the first two are divisible by

Proof. Lemma 1 took care of proving that all odd numbers are polite. Lemma 2 took care of proving all singly even numbers are polite, with the important exception of 2, the first power of two. At this point it remains to prove whether or not all doubly even numbers are polite, but there seems no simple way to kill all the birds with one stone. So from here we'll try to prove politeness for kinds of numbers that overlap partially with those covered by the first two lemmas. Lemma 3 proves the politeness of multiples of 3 by giving the solution as a sum of three consecutive integers. Then Lemma 4 proves the politeness of multiples of 5 by giving the solution as a sum of five consecutive integers. Obviously it is impractical to try to prove this for every single odd prime, so it is far more efficient to generalize this to all odd primes without any loss of comprehesion. Thus Lemma 5 makes this generalization, and from this follows Lemma 6, which shows that any run of

consecutive integers adds up to a multiple of

Now we have covered the politeness of: all odd numbers, all singly even numbers except 2, and some of the doubly even numbers, namely those divisible by odd primes. So now it remains to prove or disprove the politeness of powers of two. The solution for a power of two must not be a run of consecutive integers with an odd prime, since $2^a \nmid p$ . By Lemma 7, a run of consecutive integers that add up to a multiple of must be $2^{a + 1}$ long. To determine the smallest number such a run of nonnegative integers would add up to, we plug into the second equation for given by Lemma 7, obtaining $n = (2^{2a} - 2^{a + 1}) + 2^{a - 1}$ . This means that , even when . Furthermore, there is now way to reduce the expression we have obtained for to a single power of two, meaning that must be divisible by some odd prime. This proves that there is no run of consecutive nonnegative integers that will add up to a power of two other than 1. It has already been proven that all other positive integers do have such a representation. $\qedsymbol$

Just a few quick examples: The even number 30 can be represented as the sum of four consecutive integers (6 + 7 + 8 + 9), and since it is a multiple of 3 and 5, it can be represented as the sum of three or four consecutive integers: 9 + 10 + 11 = 4 + 5 + 6 + 7 + 8. The odd number 31 can be represented as 15 + 16. We can represent multiples of 32 as the sum of 64 consecutive positive integers; the smallest number representable thus is 2080, which leaves a remainder of 32 when divided by 64, showing that it is divisible by 32, but also by the odd primes 5 and 13.