Maths Olympiad Prep

Library /

Number theory Difficulty 6.2 National olympiad Prove it Romania

We say that a natural number is special if it can be written as the sum of two or more consecutive natural numbers. Determine how many natural numbers less than 10001000 are special.

Solution

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

Let the consecutive numbers be a,a+1,,a+k1a, a+1, \ldots, a+k-1 for k2k \geq 2. Their sum is:
S=a+(a+1)++(a+k1)=ka+k(k1)2 S = a + (a+1) + \cdots + (a+k-1) = k a + \frac{k(k-1)}{2}
So n=ka+k(k1)2n = k a + \frac{k(k-1)}{2} for some k2k \geq 2 and a1a \geq 1.

Solving for aa:
ka=nk(k1)2    a=nk(k1)2k ka = n - \frac{k(k-1)}{2} \implies a = \frac{n - \frac{k(k-1)}{2}}{k}
We require a1a \geq 1 and aa integer, so nk(k1)2n - \frac{k(k-1)}{2} must be divisible by kk and nk(k+1)2n \geq \frac{k(k+1)}{2}.

But the key is: Which nn 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 22 (i.e., 1,2,4,8,16,1, 2, 4, 8, 16, \ldots).

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

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

So, the number of special numbers less than 10001000 is 999999 minus the number of powers of 22 less than 10001000.

The powers of 22 less than 10001000 are:
1,2,4,8,16,32,64,128,256,5121, 2, 4, 8, 16, 32, 64, 128, 256, 512

20=12^{0} = 1
21=22^{1} = 2
22=42^{2} = 4
23=82^{3} = 8
24=162^{4} = 16
25=322^{5} = 32
26=642^{6} = 64
27=1282^{7} = 128
28=2562^{8} = 256
29=5122^{9} = 512
210=1024>10002^{10} = 1024 > 1000

So there are 1010 powers of 22 less than 10001000.

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

Answer: There are 989989 special natural numbers less than 10001000.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.