# Find the cardinality of the set $A_p$ defined as the following : [duplicate]

For any prime number $p$, $A_p$=the set of integers $d\in \{1,2,3,\dots, n\}$ such that the power of $p$ in the prime factorization of $d$ is odd. Then \begin{align*} A_p= & \lfloor\dfrac{n}{p}\rfloor-\lfloor\dfrac{n}{p^2}\rfloor+\lfloor\dfrac{n}{p^3}\rfloor-\lfloor\dfrac{n}{p^4}\rfloor+\dots \end{align*}

Any one can give me any idea how can I show this ?

Update:
I have gone through $1p,2p,3p,\dots, kp\leq n<(k+1)p\implies \lfloor \dfrac{n}{p}\rfloor=k$, but I can not understand after this step.

• @xarles the link you have shared is not helpful for me – NET Aug 20 '18 at 15:21
• It should be. Put it another way: what is the cardinality of the set of integers $d \in \{1, \ldots, n\}$ such that the power of $p$ in the prime factorization of $d$ is exactly $k$? Or, to start, is $\geqslant k$? – metamorphy Aug 20 '18 at 15:25
• You count first the number of elements divisible by $p$: this is $\lfloor \frac np \rfloor$, you said well. Now, you don't want the elements divisible by $p^2$, so you take out $\lfloor \frac n{p^2} \rfloor$. But now you took away the ones divisible by $p^3$, that you want... etcetera. – xarles Aug 20 '18 at 15:28