$\pi(n)$ is the number of primes that are not bigger than $n$. For $n=2,3,4,6,8,33,\dots$ we have $\pi(n)|n$. Does exist infinitely many integers $n$ that $\pi(n)|n$?
Problem
Source: Iran 2002
Tags: function, calculus, integration, inequalities, number theory unsolved, number theory
12.04.2004 10:30
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<sub>n</sub>+n)>n or, in other "words", p<sub>n+1</sub><=p<sub>n</sub>+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?
17.04.2004 17:29
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.
17.04.2004 19:58
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?
17.04.2004 19:59
I found it in one of my materials and I just love it.
17.04.2004 20:17
Excellent!
23.04.2004 15:44
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.
20.12.2008 08:27
The following is almost the same idea as the above solution (post #3). But I feel it is more revealing (easier to visualize).
21.12.2008 19:52
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 ? :
22.12.2008 09:50
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.
22.12.2008 11:00
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
16.10.2013 19: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$.
23.10.2024 15:19
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$.
23.10.2024 15:50
Clean and Conceptual
23.10.2024 16:17
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.
24.11.2024 16:46
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.