Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
add comment

3 Answers

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
add comment

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
add comment

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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.