# Understand the problem

Prove that the positive integers $$n$$ that cannot be written as a sum of $$r$$ consecutive positive integers, with $$r>1$$ ,are of the form $$n=2^l$$ for some $$l\ge 0$$.

##### Source of the problem

I.S.I. (Indian Statistical Institute) B.Stat/B.Math Entrance Examination 2019. Subjective Problem no. 1.

Number Theory

8.5 out of 10

##### Suggested Book

Elementary Number Theory by David M. Burton

Do you really need a hint? Try it first!

Claim: Any positive integer $$n$$ can be written as $$n=2^k\cdot m$$ , where $$k\ge0$$ and $$m$$ is an odd positive integer.

To prove this claim use the fact : $$n=2^k\cdot p_1^{k_1}\cdot p_2^{k_2}\cdots p_i^{k_i}$$, where $$k$$ and all $$k_i$$ are non-negetive integers and all $$p_i$$ are odd primes.

The sum of (any) $$r$$ consecutive positive integers is given by,

$$(q+1)+(q+2)+(q+3)+\cdots+(q+r)$$

= $$q\cdot r+(1+2+3+\cdots+r)$$

= $$q\cdot r+\frac{r(r+1)}{2}$$.

Equating this sum to $$n$$ we get,

$$2^k\cdot m = q\cdot r+\frac{r(r+1)}{2}$$

Or, $$2^{k+1}\cdot m = 2q\cdot r+r(r+1)$$

Or, $$2^l\cdot m = r(2q+r+1)$$ , where $$l=k+1\ge1$$.

In particular if we take $$n=2^l$$ then $$m$$ is equal to 1.

Since both $$r$$ and $$(2q+r+1)$$ are greater than 1, so they can’t be equal to $$m$$ in this case. Again one of $$r, (2q+r+1)$$ is odd integer which implies the product $$r(2q+r+1)$$ can’t be equal to $$2^l$$.

$$\Rightarrow 2^l \neq r(2q+r+1)$$

$$\Rightarrow 2^l$$ can’t be expressed as the sum of $$r$$ consecutive positive integers with $$r>1$$ and $$l\ge 1$$.

Now, $$n=2^0=1$$ also can’t be written in the same manner when $$l=0$$. Therefore the positive integers $$n$$ that cannot be written as a sum of $$r$$ consecutive positive integers, with $$r>1$$ , are of the form $$n=2^l$$ for some $$l\ge 0$$.

To show that any number other than of the form $$2^l$$ is sum of consecutive integers:
Observe that for $$n=2^l.m$$, where $$m$$ is an odd number greater than 1, there are two cases:
1. $$m < 2^l$$
Select $$r$$ and $$q$$ such that $$r = m$$ and $$2q+r+1 = 2^l$$.

2. $$m > 2^l$$
Select $$r$$ and $$q$$ such that $$2q+r+1 = m$$ and $$r = 2^l$$.

(QED).

# Connected Program at Cheenta # I.S.I. & C.M.I. Entrance Program

Indian Statistical Institute and Chennai Mathematical Institute offer challenging bachelor’s program for gifted students. These courses are B.Stat and B.Math program in I.S.I., B.Sc. Math in C.M.I.

The entrances to these programs are far more challenging than usual engineering entrances. Cheenta offers an intense, problem-driven program for these two entrances.

# Similar Problem

## How to solve an Olympiad Problem (Number Theory)?

Suppose you are given a Number Theory Olympiad Problem. You have no idea how to proceed. Totally stuck! What to do? This post will help you to atleast start with something. You have something to proceed. But as we share in our classes, how to proceed towards any...

## How are Bezout’s Theorem and Inverse related? – Number Theory

The inverse of a number (modulo some specific integer) is inherently related to GCD (Greatest Common Divisor). Euclidean Algorithm and Bezout’s Theorem forms the bridge between these ideas. We explore these beautiful ideas.

## How to use Invariance in Combinatorics – ISI Entrance Problem

Invariance is a fundamental phenomenon in mathematics. In this combinatorics problem from ISI Entrance, we discuss how to use invariance.

## The best exponent for an inequality

Understand the problemLet be positive real numbers such that .Find with proof that is the minimal value for which the following inequality holds:Albania IMO TST 2013 Inequalities Medium Inequalities by BJ Venkatachala Start with hintsDo you really need a hint?...

## A functional inequation

Understand the problemFind all functions such thatholds for all . Benelux MO 2013 Functional Equations Easy Functional Equations by BJ Venkatachala Start with hintsDo you really need a hint? Try it first!Note that the RHS does not contain $latex y$. Thus it should...

## Mathematical Circles Inequality Problem

A beautiful inequality problem from Mathematical Circles Russian Experience . we provide sequential hints . key idea is to use arithmetic mean , geometric mean inequality.

## RMO 2019

Regional Math Olympiad (RMO) 2019 is the second level Math Olympiad Program in India involving Number Theory, Geometry, Algebra and Combinatorics.

## Application of eigenvalue in degree 3 polynomial: ISI MMA 2018 Question 14

This is a cute and interesting problem based on application of eigen values in 3 degree polynomial .Here we are finding the determinant value .

## To find Trace of a given Matrix : ISI MMA 2018 Question 13

These is a cute and interesting sum where the trace of a given matrices needs to be found using a very simple but effective method

## Costa Rica NMO 2010, Final Round, Problem 4 – Number Theory

The problem is a beautiful application of the techniques in Diophantine Equation from Costa Rica Math Olympiad 2010.