Here's an argument which makes me think the answer is "yes": Assume there is an N s.t. for all n>=N \pi(n) doesn't divide n. We reach such an n and then we start increasing n with step 1. We can see that if \pi(n+\pi(n))=\pi(n) then when we increase n to n+\pi(n) we will eventually reach a number which is 0(mod \pi(n)), so the answer to the initial quastion would be "yes" in this case. We have assumed that the answer is "no", so there must be an N s.t. \pi(n+\pi(n))>\pi(n) for all n>=N. This can be translated to \pi(p_n+n)>n or, in other "words", p_n+1<=p_n+n for all sufficiently large n (n>=N, for example). This doesn't yield an obvious contradiction, but it looks too strong. If it were true, we would have known about it. This isn't a proof, but it seems a good enough argument to show us what we should prove. I'm not convinced, however. What are your opinions?

The following is not my solution, but it surely is memorable: We prove that for any m>=2 we can find n such that mpi(n)=n. Take m>1. Since pi(mk)/mk has limit 0 when k tends to infinity, there is a maximal k such that pi(mk)/mk>=1/m ( k=1 verifies this inequality). If we have equality, we are done. Otherwise, pi(mk)>k. Since k is maximal, we have pi(mk+m)/(mk+m)<1/m and thus k>=pi(km+m)>=pi(km)>k, false.

This is just beautiful! I did struggle on this problem for a day or so, and the proof was 3-lines long! Where did you find this?

I found it in one of my materials and I just love it.

Excellent!

Not solution , just a small remark : We can replace the function $ \pi\left(n\right)$ by any function $ f: \mathbb{N}\to\mathbb{Z}^{+}$ which is increasing and satisfies $ f\left(n\right)=O\left(n\right)$ when $ n$ tends to infinity. For example, $ f\left(n\right)=c$ for a constant positive integer $ c$ satisfies the requirement of the problem.

The following is almost the same idea as the above solution (post #3). But I feel it is more revealing (easier to visualize).

Akashnil wrote: To visualize this: consider the graph of $ f(x)$ and $ g(x) = x$ ($ g: \mathbb N\to \mathbb N$). At some point $ f$ is above $ g$ and after some interval it is below $ g$. together with $ f$ non-decreasing, $ f$ and $ g$ must intersect in that interval. Excuse me, $ f(x)$ and $ g(x) = x$ ($ g: \mathbb N\to \mathbb N$) are not continuous functions. so they may not intersect. or even if continuous,may not intersect at an integral point. am i right ? :

Notice that if you consider the function $ h(x) = f(x) - x$ because $ f$ is non-decreasing we have the inequality \[ h(x + 1) - h(x)\geq - 1 \] So when $ g(a) > 0$ , $ g(b < 0)$ then there will be a $ c\in[a,b]$ s.t. $ g(c) = 0$ which proves the lemma.

ith_power wrote: Excuse me, $ f(x)$ and $ g(x) = x$ ($ g: \mathbb N\to \mathbb N$) are not continuous functions. so they may not intersect. or even if continuous,may not intersect at an integral point. am i right ? : Note that what I said was "To visualize this" . It wasn't a rigorous proof. The functions aren't continuous, they aren't even defined on the reals. If you think of their graphs as dots on integral points their will be a slanted wall of dots of $ g(x)$ and $ f(x)$ begins above it and it can't jump below the wall because it is increasing. To prove the lemma rigorously see post #10

Today I was trying this problem and observed some stuffs writting a "Haskell programme". Now, let $f(x)=x-k\pi(x)$ where $k>2$ some natural number. So $f(2)<0$. Now $f(x+1)=f(x)+1$ whenever $x+1$ is prime otherwise $f(x+1)=f(x)+1-k$ and so $f(x+1)-f(x)+1$ but also $f(x)\sim x(1-\frac{k}{log x}) >0$ so after some stage we must have that $f(x)>0$ so if there doesn't exist a $x$ with $f(x)=0$ then exist some $x$ so that $f(x)<0$ and $f(x+1)>0$ and so $f(x+1)-f(x)>2$. So that's the contradiction. So for any $k$ we get some $x$ so that $f(x)=0$ and so there must be infinitely many $x$ so that $\pi(x)|x$.

pluricomplex wrote: Not solution , just a small remark : We can replace the function $ \pi\left(n\right)$ by any function $ f: \mathbb{N}\to\mathbb{Z}^{+}$ which is increasing and satisfies $ f\left(n\right)=O\left(n\right)$ when $ n$ tends to infinity. For example, $ f\left(n\right)=c$ for a constant positive integer $ c$ satisfies the requirement of the problem. Not big $O$, it should be small $o$.

Clean and Conceptual

Cool NT+ Analysis Problem It suffice to show the below claim: Claim: For every $m \ge 2$, we can find $n \ge 2$ such that: $m \pi(n) = n$. Proof: Let $m > 1$. Consider $f(k) = \frac{\pi(mk)}{mk}$. Notice that: $\lim_{k \to \infty} f(k) \to 0$. Thus, let $c$ denote the maximum value of $k$ such that: $\frac{\pi(mc)}{mc} \ge \frac{1}{m}$ (we can find such maximum value due to the limit $\lim_{k \to \infty} f(k) \to 0$). If $\pi(mc) = c$ then we are done. Else $\pi(mc) > c$: Notice that: $$\frac{\pi(mc+m)}{mc+m} < \frac{1}{m}$$due to the maximality of $k$ to be $c$, which implies: $$c \ge \pi(mc+m) \ge \pi(mc) > c$$which results to a contradiction. Thus, we have $\pi(mc) = c$, and the claim is true.

We prove that for any positive integer $k\ge 2$, there exists a positive integer $n$ satisfying $$f(n)=k\pi(n)-n.$$ Choose a number $n$ so that $f(n)<<0$ (which is possible by the Prime Number Theorem). As we decrease $n$, we have $$f(n-1)=f(n)+1$$or $$f(n-1)=f(n)-(k-1).$$But we always have $f(2)\ge 0$, so $f(n)$ will not stay negative forever as $n$ decreases. Therefore, $f(n)$ will eventually make the cross from $<0$ to $\ge 0$ as $n$ decreases. But $f(n)$ can never jump up by more than $1$ number, so there exists a value $n$ for which $f(n)=0$, done.