2
$\begingroup$

A natural question to ask is for what $n$ does $\pi(n) \mid n$ where $\pi(n)$ is the prime counting function. It can be shown with a discrete variant of the intermediate value theorem that such an $n$ exists for any $k=n/\pi(n)$. (Intuition: $f(n)=n-k \pi(k)$ can only increase by $1$ and decrease by $k-1$. Since $f(2) < 0$ for $k >3$ and $f(n)>0$ for large $n$, there must be a zero).

Computations suggest that all solutions to $n-k\pi(n)=0$ are grouped at some $n_k$ in an interval of around $\sqrt{n_k}$ width. But more surprisingly to me, for any pair of solutions $a_k$ and $a_{k+1}$, with the former being in the $k$ group and the latter in the $k+1$ group, the ratio $a_{k+1}/a_k$ seems to be about $e$.

My conjecture: If $a_k-k \pi(a_k)=0$ then $a_{k+1}/a_{k} \to e$. In other words, the solutions of $f(n)=n-k\pi(k)$ grow exponentially as $e^k$.

I am at a loss why this is the case. My guess is the gaps between primes $[n!, n!+n]$ comes into play, giving us Stiring's formula and hence our $e$ factor, but I really have no clue.

Can someone either (1) provide a proof or disproof of this conjecture or (2) give an extremely plausible method of attack? I would also appreciate suggestions in the comments for ideas/theorems/techniques to investigate to help me make my own crack at the problem.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

This appears to be due to the distribution of the primes.

Here's a heuristic.

By the Prime Number Theorem, $\pi(x) \approx \frac{x}{\log x}$, so that $$ \frac{x}{\frac{x}{\log x}} \approx \log x$$ and so to increase the value of $\frac{x}{\frac{x}{\log x}}$ by one, we need to increase $x$ by a factor of $e$.

$\endgroup$
2
  • $\begingroup$ Ah, this should have been obvious. So the presence of $e$ really goes back to the mystery of the prime number theorem. $\endgroup$
    – abnry
    Commented Nov 9, 2016 at 1:41
  • $\begingroup$ You're welcome! Cheers! $\endgroup$ Commented Nov 9, 2016 at 2:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .