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$.

Or we can just choose $2n$ distinct primes $\{p_i\}_i,\{q_i\}_i,\ i=\overline{1,n}$, and take a positive integer $k$ such that $k\equiv -i\pmod{p_iq_i},\ \forall i\in\overline{1,n}$, which must exist by the Chinese Remainder Theorem. The numbers $k+1,k+2,\ldots,k+n$ will do the trick. A little simpler, huh?

Well, a much simpler solution would be to consider the set of $n$ integers $\{ [(n+1)!]^2 + 2, [(n+1)!]^2 + 3, \ldots , [(n+1)!]^2 + (n+1) \}$.

I have found the same solution as dblues and I wonder isn't it too easy for IMO #5?

Extension: Replace prime with power of any integer.

But then any integer is a power of itself.

I mean perfect power (i.e the exponent is greater than one).

By taking (by CRT) $x_0$ a positive integer solution of the system of congruences $x+k\equiv p_k\pmod{p_k^2}$, $1\leq k \leq n$, and $x = x_0 + \prod_{k=1}^n p_k^2$, we also guarantee $x+k$ is composite for all $k$.

dblues wrote: Well, a much simpler solution would be to consider the set of $n$ integers $\{ [(n+1)!]^2 + 2, [(n+1)!]^2 + 3, \ldots , [(n+1)!]^2 + (n+1) \}$. Not to nitpick, but I think that you should prove that they are all NOT perfect powers of a prime number.

CRT..........

never mind

I will explain dblues's solution . Let's assume that one of the numbers is the power of a prime. Let it be $[(n+1)!]^2+i=p^k$ with $p$ prime and $2\leq i\leq n+1$. From this we get that $i$ divides $p^k$ so $i=p^l$ with $l\geq 1$. So $p\leq i\leq n+1$. Obviously $k=v_p([(n+1)!]^2+i)=\min(v_p([(n+1)!]^2),v_p(i))=v_p(i)=l$ $i=p^l=p^k=[(n+1)!]^2+i$ a contradiction. $v_p(x)$ is the exponent of $p$ in $x$.

How do we get $ (n+1)!^2+i=p^k\Rightarrow i\mid p^k $??

aleph_zero wrote: How do we get $ (n+1)!^2+i=p^k\Rightarrow i\mid p^k $?? Because $i|(n+1)! \implies i|(n+1)!^2+i \implies i|p^k$

My solution Let ${p_1},{p_2},...,{p_{2n}}$ be $2n$ prime intergers Consider the system of equations $x \equiv - 1\left( {\bmod {p_1}} \right)$ $x \equiv - 1\left( {\bmod {p_2}} \right)$ $x \equiv - 2\left( {\bmod {p_3}} \right)$ $x \equiv - 2\left( {\bmod {p_4}} \right)$ $..$. $x \equiv - 1\left( {\bmod {p_{2n - 1}}} \right)$ $x \equiv - 1\left( {\bmod {p_{2n}}} \right)$ By CRT, the system have one $x$ satisfies So, $x + i \vdots {p_{2i - 1}},{p_{2i}}$, $i = \overline {1,n} $ ....

Let us take any $a\in\mathbb{N}$ and consider $n$ consecutive integers $a+1,..., a+n$ . If none of this numbers is an integral power of a prime number, then we are done. Now suppose ${p_1}^{a_1}<...<{p_k}^{a_k}$ are all the numbers (among $a+1,..., a+n$) which are integral powers of prime numbers ( $p_1, ...,p_k$ - prime numbers). I take $N=s*{p_1}^{a_1+1}*...*{p_k}^{a_k+1} $ ( I choose $s\in\mathbb{N}$ so that $N>(a+n)$) and prove that none of $n$ consecutive integers $N!+a+1,..., N!+a+n$ is an integral power of a prime number. There are 2 cases: 1. $a+i$($n\geq i\geq 1$) isn't an integral power of a prime number. $(N!+a+i )\vdots{(a+i)}$, so $N!+a+i$ isn't an integral power of a prime number. 2.$a+i={p_j}^{a_j}$ ( $n\geq i\geq 1$ ) for some $j$, $k\geq i\geq 1$. Suppose $(N!+a+i )=p^t$ for some prime number $p$ and $t\in\mathbb{Z}$. Note that $(N!+a+i )\vdots{(a+i)}$ , so $p={p_j}$ . Also $N!\vdots N\vdots {({p_j}^{a_j+1})}$ and $a+i={p_j}^{a_j}$ so ${p_j}^{a_j+1}$ doesn't divide $N!+a+i$, so ${p_j}^{a_j}\geq N!+a+i$ . Contradiction. So $N!+a+i$ isn't an integral power of a prime number for $n\geq i\geq 1$ .

The problem is essentially asking to find a natural number $m$ such that $$m, m+1, \dots, m+n-1$$are not powers of any prime. Consider the list of primes $\{p_1, p_2, p_3, \dots\}$. Simply pick $m$ such that $m$ satisfies the following congruences. \begin{align*} m \equiv 0 \pmod {p_1p_2} \\ m+1 \equiv 0 \pmod {p_3p_4} \\ \vdots \\ m+n-1 \equiv 0 \pmod {p_{2n-1}p_{2n}} \\ \end{align*} A solution exists by CRT. Further, each number in the sequence $\{m, m+1, \dots, m+n-1\}$ is divisible by the product of $2$ primes, so this $m$ works.

Let $p_1,p_2,p_3,\dots,p_n$ are $N$ prime numbers.By CRT we can find arbitrary large $x$ such that: \begin{align*} x &\equiv p_1-1 \pmod{p_1^2} \\ x &\equiv p_2-2 \pmod{p_2^2} \\ &\phantom\equiv\vdots \\ x &\equiv p_n-n \pmod{p_n^2}. \end{align*}But then $x+i$ is divisible by $p_i$ but not by $p_i^2$.Now take $x$ sufficiently large in that particular residue class $\pmod{p_1p_2\dots p_N}$ so that $x+i\ne p_i$. $\square$

let $\{p_i\}$ and $\{h_i\}$be two sequences of prime numbers and $\{p_i\} \cap \{h_i\}=\emptyset$ Hence we are looking for $x$ the solutions to this system \begin{align*} x \equiv i \pmod{p_i\cdot h_i} \end{align*}for $i =\{1, 2,... ,n\}$ and by the Chinese Remainder Theorem it has a solution

Clearly, the product of two distinct primes cannot be the power of a prime, and if an integer is a multiple of a product of two distinct primes it also cannot be the power of a prime. The problem statement is equivalent to the following system of congruences: \begin{align*} x &\equiv 0 \pmod {p_1p_2} \\ x+1 &\equiv 0 \pmod {p_3p_4} \\ \cdots \\ x+n-1 &\equiv 0 \pmod {p_{2n-1}p_{2n}} \\ \end{align*} which can be rewritten as \begin{align*} x &\equiv 0 \pmod {p_1p_2} \\ x &\equiv -1 \pmod {p_3p_4} \\ \cdots \\ x &\equiv -n+1 \pmod {p_{2n-1}p_{2n+1}} \\ \end{align*}. By CRT this system has a solution $x$, which means those consecutive integers exist, as desired. $\blacksquare$

Choose the first $2n$ prime numbers, and choose $a$ satisfying $$a \equiv{-k} \pmod{p_{2k-1}p_{2k}}$$for all $k$ (Which clearly exists by CRT). Then $a+1, \dots, a+n$ Is a valid set satisfying the desired conditions.

Take $$a=(2n)!-n$$Then $<a+i>_{0\leq I \leq n-1}$ works

Let $p_1,\dots, p_{2i}$ be a sequence of $2i$ distinct primes. By CRT, there exists a $q$ such that \begin{align*} &p_1p_2\mid q+1 \\ \vdots \\ &p_{2i-1}p_{2i} \mid q+i, \end{align*}the claim follows.

By CRT there exists a positive integer $m$ such that $m \equiv -i \pmod {p_{2i-1}p_{2i}}$ for all positive integers $i$, where $p_i$ denotes the $i$th prime. Then the $n$ integers not including $m$ immediately succeeding it work.

By CRT, there exists an integer $x$ such that: $$ \begin{cases} x \equiv -1 \pmod{p_1 p_2} \\ x \equiv -2 \pmod{p_3 p_4} \\ \dots \\ x \equiv -n \pmod{p_{2n-1}p_{2n}}. \end{cases} $$Consider the sequence $x+1, x+2, \dots, x+n$. Each of these integers have two prime factors. Therefore, they cannot be expressed as a power of a single prime.

why is this so ez (I hope this works) For all positive integers $i,$ let $p_i$ be the $i$th positive prime, so for example, $p_1=2$ and $p_2=3.$ Also, define $\nu_p(q)$ to be the exponent of the largest power of $p$ dividing $q$ for all positive integers $q$ and all primes $p.$ Note that the elements of $\{p_1^2,p_2^2,\dots,p_n^2\}$ are pairwise relatively prime. Thus, by CRT, there exists infinitely many positive integers $m$ such that the following system holds: \begin{align*} m&\equiv p_1\pmod{p_1^2}\\ m+1&\equiv p_2\pmod{p_2^2}\\ m+2&\equiv p_3\pmod{p_3^2}\\ &\vdots \\ m+n-1&\equiv p_n\pmod{p_n^2}.\\ \end{align*}Since there are infinitely many positive integer values of $m$ that satisfies this, there must exist a positive $m_1$ that satisfies this such that the following series of inequalities all hold: \begin{align*} m_1&>p_1\\ m_1+1&>p_2\\ m_1+2&>p_3\\ &\vdots \\ m_1+n-1&>p_n.\\ \end{align*}Assume for the sake of contradiction that there exists an integer $0\leq k\leq n-1$ such that $m_1+k$ is a perfect power of a prime. Then, since $m_1+k\equiv p_{k+1}\pmod{p_{k+1}^2},$ $\nu_{p_{k+1}}(m_1+k)=1,$ so $m_1+1$ is a perfect power of $p_{k+1},$ and furthermore, $m_1+k=p_{k+1}>p_{k+1},$ a contradiction. Thus, there does not exist an integer $0\leq k\leq n-1$ such that $m_1+k$ is a perfect power of a prime, and thus $\{m_1,m_1+1,m_1+2,\dots, m_1+n-1\}$ is a set of $n$ consecutive positive integers such that none of them are perfect powers of a prime, as desired. $\Box$

The numbers $k!+2, k!+3, \dots, k! + \lfloor \frac k2 \rfloor$ work for large $k$.