## You are here

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

## Primary tabs

# 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. $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. $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.

∎

## Mathematics Subject Classification

11A25*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections