7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What does it mean to have an exact formula that holds only infinitely often, as opposed to, well, all the time? $\endgroup$
    – Yemon Choi
    Aug 20, 2013 at 16:45
  • $\begingroup$ 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! $\endgroup$ Aug 20, 2013 at 17:33
  • $\begingroup$ Yes of course, now it is correct.thanks for noting this! $\endgroup$ Aug 21, 2013 at 7:50

3 Answers 3

17
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$ Aug 20, 2013 at 17:25
10
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$ Aug 21, 2013 at 21:27
  • $\begingroup$ $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)$. $\endgroup$ Aug 21, 2013 at 23:02
  • $\begingroup$ 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. $\endgroup$ Aug 22, 2013 at 11:25
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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)$ ? $\endgroup$ Aug 21, 2013 at 8:01
  • $\begingroup$ According to both maple and wolfram the limit at infinity violates RH? Do you really mean infinity? $\endgroup$
    – user25199
    Aug 21, 2013 at 8:09
  • $\begingroup$ @KonstantinosGaitanas I edited the question with explanation, hopefully it is better now. $\endgroup$
    – joro
    Aug 21, 2013 at 8:18
  • $\begingroup$ @Carl I suppose $n > 3000$ is enough, Maple couldn't solve the inequality and I didn't even try. $\endgroup$
    – joro
    Aug 21, 2013 at 8:20
  • $\begingroup$ 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! $\endgroup$ Aug 21, 2013 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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