PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (192)
Orphanage
Unclass'd
Unproven (496)
Corrections (20)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: Very high
[parent] another proof that a number is polite iff it is positive and not a positive power of $2$ (Derivation)

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

$\displaystyle 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

    $\displaystyle 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

    $\displaystyle 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
    $\displaystyle m=\frac{2a+p-1}{2}.$
    Then
    $\displaystyle a+(a+1)+\cdots + (a+p-1) = \frac{(2a+p-1)p}{2}=mp=n,$
    showing that $ n$ is polite.

$ \qedsymbol$



"another proof that a number is polite iff it is positive and not a positive power of $2$" is owned by CWoo.
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: even numbers, prime, solution, forces, implies, odd, consecutive, sum, positive, iff, integer, proof

This is version 2 of another proof that a number is polite iff it is positive and not a positive power of $2$, born on 2008-06-30, modified 2008-06-30.
Object id is 10729, canonical name is AnotherProofThatANumberIsPoliteIffItIsNeverNonPositiveNorAPositivePowerOf2.
Accessed 128 times total.

Classification:
AMS MSC: 11A25 (Number theory :: Elementary number theory :: Arithmetic functions; related numbers; inversion formulas)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)