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 formulaMathworldPlanetmathPlanetmath


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)++(a+k), where a is non-negative and k>0, then


    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 factorizationMathworldPlanetmath 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 a0, 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 mp, or m-p0. Set


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




    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 DerivationPlanetmathPlanetmath
Classification msc 11A25