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)+\mathrm{\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)+\mathrm{\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\ge 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\ge p$, or $m-p\ge 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)\ge m+1>0$, $a$ is positive. Solving for $m$ we get

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

   Then

   $$a+(a+1)+\mathrm{\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$
Canonical name	AnotherProofThatANumberIsPoliteIffItIsPositiveAndNotAPositivePowerOf2
Date of creation	2013-03-22 18:10:05
Last modified on	2013-03-22 18:10:05
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	5
Author	CWoo (3771)
Entry type	Derivation
Classification	msc 11A25