# another proof that a number is polite iff it is positive and not a positive power of $2$

In this entry we give another proof that an integer is polite iff it is neither non-positive nor a positive power of $2$. The proof utilizes the formula

 $a+(a+1)+\cdots+b=\frac{(a+b)(b-a+1)}{2}.$
###### Proof.

By definition, an integer $n$ is polite if it a sum of consecutive non-negative integers, $n$ itself must be non-negative. Furthermore $n$ can not be $0$ since a sum of at least two consecutive non-negative integers must be positive. So we may assume that $n$ is positive.

There are two cases:

1. 1.

$n$ is a power of $2$:

Suppose that $n$ is polite, say $n=a+(a+1)+\cdots+(a+k)$, where $a$ is non-negative and $k>0$, then

 $n=\frac{(2a+k)(k+1)}{2}$

This means that $(2a+k)(k+1)=2n$ is a power of $2$, or $2a+k$ and $k+1$ are both powers of $2$ by the unique factorization of positive integers. Since $k>0$, $k+1>1$, so that if $k+1$ were a power of $2$, $k$ must be odd, which implies that $2a+k$ is odd too. Since $2a+k$ is a power of $2$, this forces $2a+k=1$. As $k>0$ and $a\geq 0$, there is only one solution: $k=1$ and $a=0$, or $n=1$, showing that $1$ is the only power of $2$ that is polite.

2. 2.

$n$ is not a power of $2$:

Let $p$ be the smallest odd prime dividing $n$. Write $n=mp$. So $m\geq p$, or $m-p\geq 0$. Set

 $a:=\frac{2m+1-p}{2}.$

Since $2m+1-p$ is the sum of $2m$ and $1-p$, both even numbers, $a$ is an integer. Since $2m+1-p=(m-p)+(m+1)\geq m+1>0$, $a$ is positive. Solving for $m$ we get

 $m=\frac{2a+p-1}{2}.$

Then

 $a+(a+1)+\cdots+(a+p-1)=\frac{(2a+p-1)p}{2}=mp=n,$

showing that $n$ is polite.

Title another proof that a number is polite iff it is positive and not a positive power of $2$ AnotherProofThatANumberIsPoliteIffItIsPositiveAndNotAPositivePowerOf2 2013-03-22 18:10:05 2013-03-22 18:10:05 CWoo (3771) CWoo (3771) 5 CWoo (3771) Derivation msc 11A25