$\pi (x) = -1 + \pi(\sqrt x) + \sum \mu (d)\lfloor \frac {x}{d}\rfloor$,

Question

Sorry about the title i didn't know what to call this other than "analytic number theory"

I am asked to show that $\pi (x) = -1 + \pi(\sqrt x) + \sum \mu (d)\lfloor \frac {x}{d}\rfloor$, where the sum is over all d for which ever prime factor is less or equal to $\sqrt x $

The furthest right hand part of the equation looks like a mobius inversion but im not sure how to do it over root x and the rest i am completely lost on.

Answer 1

This should be Legendre’s formula for computing $\pi(x)$: $$ \pi(x)=-1+\pi(\sqrt{x})+\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 $$ This is proved there.

Answer 2

I don't believe this is true. Take $x=25$.

$\pi(x)=9$, $\pi(\sqrt{x})=3$.

The relevant $d$s are $2, 3, 5$ together with their square-free multiples, that is $6, 10, 15, 30$. The factor $\lfloor \frac {x}{d}\rfloor$ kills the participation of $15$ and $30$.

For the rest we get $$9=-1+3+(-12-8-5+4+2)$$

which is wrong, right?