3
$\begingroup$

Legendre's formula counts the number of positive integers less than or equal to a number $x$ which are not divisible by any of the first $a$ primes: $$\begin{align} &\phi(x,a)=\lfloor x \rfloor-\sum_{p_i\le a}\left\lfloor \dfrac{ x }{(p_i)}\right\rfloor+\sum_{p_i<p_j\le a}\left\lfloor\dfrac{ x}{(p_ip_j)}\right\rfloor-\sum_{p_i<p_j<p_k\le a}\left\lfloor \dfrac{x}{(p_ip_jp_k)}\right\rfloor+\dots \end{align}$$ then $\pi(x)=\phi\bigl(x,\pi (\sqrt{x})\bigr)+\pi (\sqrt{x})-1$ as given here.

My question is, why does $\bigl\lfloor\phi(x,\lfloor\sqrt{x}\rfloor)+\sqrt{x}-1\bigr\rfloor$ also equal $\pi(x)?$

$\endgroup$
  • $\begingroup$ I don't have time to think about this carefully, hence a comment, not an answer: Any number $\le x$ which is not divisible by any prime $\le\sqrt{x}$ is a prime number. So roughly speaking, $\phi\bigl(x,\lfloor\sqrt{x}\rfloor\bigr)$ counts the primes $\le x$. However, it misses the primes $\le \sqrt{x}$, which are after all divisible by themselves. So those have to be added back. It only remains to clear up any off-by-one errors, I think … $\endgroup$ – Harald Hanche-Olsen Aug 31 '14 at 15:43
1
$\begingroup$

Note: In your sums, you must have $i\leqslant a$ etc. instead of $p_i \leqslant a$ to consider the first $a$ primes, and not the primes $\leqslant a$.

Whenever $a \geqslant \pi(\sqrt{x})$, the numbers $\leqslant x$ not divisible by any of the first $a$ primes are the primes between $p_a$ (exclusive) and $x$ (inclusive), and $1$. So then you have

$$\phi(x,a) = \pi(x) - a + 1.$$

Since $\lfloor \sqrt{x}\rfloor \geqslant \pi(\sqrt{x})$, the identity follows for $a = \lfloor\sqrt{x}\rfloor$.

$\endgroup$
1
$\begingroup$

$\phi(x,\pi(\sqrt{x}))$ is the number of positive integers $\le x$ which are not divisible by any prime $\le\sqrt{x}$. In other words, it is a count of the primes which are $\le x$ but $>\sqrt{x}$. Except that it also counts 1 (which is not considered a prime. So to get $\pi(x)$ we need to add the number of primes $\le\sqrt{x}$ which is just $\pi(\sqrt{x})$ and subtract 1.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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