75th NMO

Let $n$ be a natural number. We want to count the number of $n<1000$ that can be written as the sum of two or more consecutive natural numbers.

Let the consecutive numbers be $a,a+1,\dots ,a+k-1$ for $k\ge 2$. Their sum is: $$S=a+(a+1)+\cdots +(a+k-1)=ka+\frac{k(k-1)}{2}$$ So $n=ka+\frac{k(k-1)}{2}$ for some $k\ge 2$ and $a\ge 1$.

Solving for $a$: $$ka=n-\frac{k(k-1)}{2}⟹a=\frac{n-\frac{k(k-1)}{2}}{k}$$ We require $a\ge 1$ and $a$ integer, so $n-\frac{k(k-1)}{2}$ must be divisible by $k$ and $n\ge \frac{k(k+1)}{2}$.

But the key is: Which $n$ cannot be written in this way?

It is a well-known result that the numbers that cannot be written as the sum of two or more consecutive natural numbers are the powers of $2$ (i.e., $1,2,4,8,16,\dots$).

Proof: Let $n$ be a natural number. $n$ can be written as the sum of $k$ consecutive natural numbers if and only if there exists $k\ge 2$ such that $n-\frac{k(k-1)}{2}$ is divisible by $k$ and $n\ge \frac{k(k+1)}{2}$.

But the only numbers that cannot be written in this way are the powers of $2$.

So, the number of special numbers less than $1000$ is $999$ minus the number of powers of $2$ less than $1000$.

The powers of $2$ less than $1000$ are: $1,2,4,8,16,32,64,128,256,512$

$2^0=1$ $2^1=2$ $2^2=4$ $2^3=8$ $2^4=16$ $2^5=32$ $2^6=64$ $2^7=128$ $2^8=256$ $2^9=512$ $2^{10}=1024>1000$

So there are $10$ powers of $2$ less than $1000$.

Therefore, the answer is: $$999-10=989$$

Answer: There are $989$ special natural numbers less than $1000$.