2
$\begingroup$

How would I go about proving this? I came across this when I was searching for interesting prime generating function. Or alternatively, could you kindly direct me to a source containing a complete proof for the following formula?

$$p_n=1+\sum^{2^n}_{m=1}\left\lfloor\left\lfloor\frac{n}{1+\pi(m)}\right\rfloor^{\frac{1}{n}}\right\rfloor.$$

Here $\pi(m)$ is the prime counting function.

$\endgroup$
1
  • $\begingroup$ $p_n = \sum_{k=n}^\infty k \ 1_{\pi(k) = n} 1_{\pi(k-1) = n-1} $ and for $m \ge 1, n\ge 1$ : $1_{m=n} = \lfloor \frac{n}{m} \rfloor \lfloor \frac{m}{n} \rfloor$ thus $p_n = \sum_{k=n}^\infty k \lfloor \frac{n}{\pi(k)} \rfloor \lfloor \frac{\pi(k)}{n} \rfloor \lfloor\frac{n-1}{\pi(k-1)} \rfloor \lfloor \frac{\pi(k-1)}{n-1} \rfloor$. Do you see how to adapt it to your formula ? $\endgroup$
    – reuns
    Commented Dec 19, 2017 at 23:14

1 Answer 1

2
+50
$\begingroup$

Lemma: For any $x \geqslant 0$ and $n \in \mathbb{N}_+$, $\bigl[[x]^{\frac{1}{n}}\bigr] = [x^{\frac{1}{n}}]$.

Proof: It is easy to see that $\bigl[[x]^{\frac{1}{n}}\bigr] \leqslant [x^{\frac{1}{n}}]$. Now, suppose $a = [x^{\frac{1}{n}}] \in \mathbb{N}$, then$$ x = (x^{\frac{1}{n}})^n \geqslant a^n \Longrightarrow [x] \geqslant a^n \Longrightarrow [x]^{\frac{1}{n}} \geqslant a \Longrightarrow \bigl[[x]^{\frac{1}{n}}\bigr] \geqslant a = [x^{\frac{1}{n}}]. $$ Thus, $\bigl[[x]^{\frac{1}{n}}\bigr] = [x^{\frac{1}{n}}]$.

Now back to the question. By the lemma,$$ \sum_{m = 1}^{2^n} \left[ \left[ \frac{n}{1 + π(m)} \right]^{\frac{1}{n}} \right] = \sum_{m = 1}^{2^n} \left[ \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \right]. $$ Note that $n < 2^n$ for any $n \geqslant 1$, thus for any $1 \leqslant m \leqslant 2^n$,$$ 0 < \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \leqslant n^{\frac{1}{n}} < 2 \Longrightarrow \left[ \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \right] = 0 \text{ or } 1. $$ By Bertrand's postulate, $p_n \leqslant 2^n$ for all $n \geqslant 1$, thus $π(m) \leqslant n - 1$ for $1 \leqslant m \leqslant p_n - 1$ and $π(m) \geqslant n$ for $p_n \leqslant m \leqslant 2^n$, which implies\begin{align*} \sum_{m = 1}^{2^n} \left[ \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \right] &= \sum_{\substack{1 \leqslant m \leqslant 2^n\\π(m) \leqslant n - 1}} \left[ \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \right] + \sum_{\substack{1 \leqslant m \leqslant 2^n\\π(m) \geqslant n}} \left[ \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \right]\\ &= \sum_{\substack{1 \leqslant m \leqslant 2^n\\π(m) \leqslant n - 1}} 1 + \sum_{\substack{1 \leqslant m \leqslant 2^n\\π(m) \geqslant n}} 0 = \sum_{m = 1}^{p_n - 1} 1 + \sum_{m = p_n}^{2^n} 0 = p_n - 1. \end{align*} Therefore,$$ 1 + \sum_{m = 1}^{2^n} \left[ \left[ \frac{n}{1 + π(m)} \right]^{\frac{1}{n}} \right] = 1 + \sum_{m = 1}^{2^n} \left[ \left( \frac{n}{1 + π(m)} \right)^{\frac{1}{n}} \right] = p_n. $$

$\endgroup$
4
  • $\begingroup$ I'm very sorry. It's supposed to be $2^n$; I've corrected my question. $\endgroup$ Commented Jun 10, 2018 at 3:12
  • $\begingroup$ @Kugelblitz I've posted the proof for the corrected identity :) $\endgroup$ Commented Jun 10, 2018 at 3:39
  • $\begingroup$ Thank you so very much. I'll give you the bounty when I'm allowed to. $\endgroup$ Commented Jun 10, 2018 at 3:43
  • $\begingroup$ Also, why is $(x^{\frac{1}{n}})^n=[x]$? $\endgroup$ Commented Jun 10, 2018 at 3:46

You must log in to answer this question.

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