Take the 2-minute tour ×

A famous inequality that has been proved by J.B. Rosser and L. Schoenfeld says that

$\frac{n}{\ln n-1/2}$ < $\pi(n)$<$\frac{n}{\ln n-3/2} , n\ge 67$.

Using this inequality we can prove that when $\pi(n)$ divides $n$ (and this happens infinitely often) then

$\pi(n)=\frac{n}{[\ln n-1/2]}$ (for $n\ge 67$)

(By $[\ln n-1/2]$ we denote the integer part of $\ln n-1/2$).

This is an exact formula for $\pi(n)$ that occurs infinitely often.

The question is: Do we have any knowledge about when $\pi(n)$ divides $n$ or anything in this direction?

Thank you for viewing.

share|improve this question
What does it mean to have an exact formula that holds only infinitely often, as opposed to, well, all the time? –  Yemon Choi Aug 20 '13 at 16:45
The formula does not hold for every $n\ge 67$ but when $\pi(n)$ divides n and also $n\ge 67$. I intended just to give an easy and precise formula (without using ALL the previous primes nor the sigma notation) that occurs infinitely often. thanks for the responce though! –  Konstantinos Gaitanas Aug 20 '13 at 17:33
Yes of course, now it is correct.thanks for noting this! –  Konstantinos Gaitanas Aug 21 '13 at 7:50

3 Answers 3

Golomb, "On the ratio of $N$ to $\pi(N)$", proves that $N/\pi(N)$ takes every integer value greater than $1$. In particular, this happens infinitely often. The proof is completely elementary, using only that $\pi(N) = o(N)$ and $\pi(N+1)-\pi(N)$ is $0$ or $1$.

Recipe for finding this: Write a line of Mathematica code to find all such $N$ under $200$. Plug the sequence into Sloane's encylcopedia to find A057809. Stumble around the "related sequence" links until I find A038626, which cites Golomb.

share|improve this answer
Thanks a lot for the help and for the link,the article was very helpfull and accurate!But I suppose there does not exist a sufficient condition for $\pi(n)$ divides $n$? I was hopping for something more precise, to predict when this happens for example –  Konstantinos Gaitanas Aug 20 '13 at 17:25

Just to emphasize, $t/\lfloor \ln t-1/2 \rfloor$ is not, in any ordinary sense, as good an approximation to $\pi(t)$ as $t/(\ln t-1)$, let alone as good as $\int_e^t dx/\ln x$. It is simply, like a stopped clock, an approximation which is occasionally exactly right.

I'll define $R(u)$ to mean the closest integer to $u$, so your proposed approximation is $t/R(\ln t -1)$. Set $Li(t) = \int_e^t \frac{dx}{\ln x}$ (where the lower bound of the integral is set is irrelevant.) Then $\pi(t) - Li(t)$ is eventually smaller than $t/(\ln t)^N$ for any $N$. Integrating by parts shows that $$Li(t) = \frac{t}{\ln t} + \frac{t}{(\ln t)^2} + \frac{2 t}{(\ln t)^3} + \frac{3! t}{(\ln t)^3} + \frac{4! t}{(\ln t)^4} + \cdots $$ where $\cdots$ is meant in the sense of asymtotic series: If you stop the sum at the $N$-th term, the error will be bounded by a multiple of the $(N+1)$-st term. We have $$\frac{t}{\ln t - 1} = \frac{t}{\ln t} \frac{1}{1-1/\ln t} = \frac{t}{\ln t} + \frac{t}{(\ln t)^2} + \frac{t}{(\ln t)^3} + \frac{t}{(\ln t)^4} + \cdots$$ So $t/(\ln t -1)$ is pretty good, matching the first two terms of the asymptotic series. By comparison, $t/R(\ln t -1) = t/(\ln t - 1 + \theta)$, where $\theta$ oscillates between $\pm 1/2$. So $t/R(\ln t -1) = t/\ln t + (1-\theta) t/(\ln t)^2+\cdots$, only matching the first term of the series.

To emphasize the difference, the following figure plots $$Li(t)- \pi(t) \ \mbox{(green)} \quad \frac{t}{\ln t -1} - \pi(t) \ \mbox{(blue)} \quad \frac{t}{R(\ln t -1)} - \pi(t) \ \mbox{(red)}$$ for $t$ between $10^4$ and $10^6$.

enter image description here

You can see that green is a little bit better than blue and both are in general far better than red, although red is occasionally exactly right.

share|improve this answer
Yes,of course if $\pi(n)$ does not divide $n$ then $\frac{n}{[lnn-1/2]}$ is i think too far from the truth. It is the $exactly right$ as you mentioned the main reason that this looked good to me,even if it behaves like a clock. But in your analysis why are you using $R(lnt-1)$ and not $R(lnt-1/2)$? Very crystal mathematical analysis!Thank you for helping! –  Konstantinos Gaitanas Aug 21 '13 at 21:27
$R(u)$ is the nearest integer to $u$, so $R(u) = \lfloor u+1/2 \rfloor$. I'm writing it that way to emphasize that, on average, the quantity you are discussing is acting like $t/(\ln t -1)$. –  David Speyer Aug 21 '13 at 23:02
Yes that seems brighter now. It seemed strange to me why you were using $R(lnnt-1)$ but by the definition of $R(u)$ this is indeed correct. –  Konstantinos Gaitanas Aug 22 '13 at 11:25

I think Riemann Hypothesis is related to the size of the fractional part of your formula.

RH implies: $$ \pi(x) > li(x) -\sqrt{x}\log{x}/(8 \pi) \text{ if } 2657 \le x \qquad (1)$$

Suppose your formula holds and write $$ \lfloor \log{n} -\frac12 \rfloor = \log{n} -\frac12 - \alpha \qquad (2) $$ where $\alpha$ is the fractional of $\log{n} -\frac12$

Suppose $ 0 < \alpha \le \frac12$. By your formula $\pi(n)=n/(\log{n} -\frac12 - \alpha)$ and in (1):

$$ x/(\log{x} -\frac12 - \alpha) > li(x) -\sqrt{x}\log{x}/(8 \pi) \qquad (3)$$

According to both Maple and Wolfram alpha the limit at infinity of (3) violates RH, so RH implies $\alpha > \frac12$ whenever your formula holds and $n$ is large enough. (Probably (3) violates RH for $n> 3000$ , not sure).

OEIS A057809 Numbers n such that pi(n) divides n has 296 entries, the larges of which is $75370126416$.

$\alpha \le \frac12$ happens only 14 times ending at $a(n)=1092$.

share|improve this answer
This looks very interesting but i need some help.which limit is the one that you computed? (1) is just an inequality. You mean the right hand of (1) divided by $\pi(x)$ ? –  Konstantinos Gaitanas Aug 21 '13 at 8:01
According to both maple and wolfram the limit at infinity violates RH? Do you really mean infinity? –  Carl Aug 21 '13 at 8:09
@KonstantinosGaitanas I edited the question with explanation, hopefully it is better now. –  joro Aug 21 '13 at 8:18
@Carl I suppose $n > 3000$ is enough, Maple couldn't solve the inequality and I didn't even try. –  joro Aug 21 '13 at 8:20
Yes it seems to be related with Riemann Hypothesis but i can't see how this could be applied to the first mentioned problem. Thank you for the edit with the explanation.Thumbs up! –  Konstantinos Gaitanas Aug 21 '13 at 15:37

Your Answer


