1989 IMO Problems/Problem 5

Problem

Prove that for each positive integer $n$ there exist $n$ consecutive positive integers none of which is an integral power of a prime number.

Solution

There are at most $1+\sqrt[2]{n}+\sqrt[3]{n}+\sqrt[4]{n}+...+\sqrt[\left\lfloor \log_2(n)\right\rfloor]{n} \leq 1+ \sqrt n log_2(n)$ 'true' powers $m^k , k\geq 2$ in the set $\{1,2,...,n\}$ . So when $p(n)$ gives the amount of 'true' powers $\leq n$ we get that $\lim_{n \to \infty} \frac{p(n)}{n} = 0$ .

Since also $\lim_{n \to \infty} \frac{\pi(n)}{n} = 0$ , we get that $\lim_{n \to \infty} \frac{p(n)+\pi(n)}{n} = 0$ . Now assume that there is no 'gap' of lenght at least $k$ into the set of 'true' powers and the primes. Then this would give that $\frac{p(n)+\pi(n)}{n} \geq \frac{1}{k}$ for all $n$ in contrary to the above (at east this proves a bit more).

Edit: to elementarize the $\lim_{n \to \infty} \frac{\pi(n)}{n} = 0$ part: Look $\mod (k+1)!$ . Then all numbers in the residue classes $2,3,4,...,k+1$ are not primes (except the smallest representants sometimes). So when there wouldn't exist a gap of length $k$ , there has to be a 'true' power in each of these gaps of the prime numbers, so at least one power each $(k+1)!$ numbers, again contradicting $\lim_{n \to \infty} \frac{p(n)}{n} = 0$ .

This solution was posted and copyrighted by ZetaX. The original thread for this problem can be found here: [1]

1989 IMO (Problems) • Resources
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 6
All IMO Problems and Solutions

Page

Toolbox

Search

1989 IMO Problems/Problem 5

Problem

Solution

See Also