Finding the number of $n \leq x$ such that $d^2 |n$ is

73 Views Asked by At

This particular result is part of proving that number of squarefree integers upto $x$ is $x/ \zeta(2) +O \sqrt(2) $.

Actually, I am reading from notes of a senior and it is written that the number of $ n \leq x$ , such that $d^2 | n $ is $\lfloor x /d^2 \rfloor$ = $x/d^2 +O(1) $.

But, I am not able to deduce it.

I am completely aware of Big O notation and I think $\lfloor x \rfloor$ = least integer function.

The identity is clear to me that how $\lfloor x/ d^2 \rfloor = x/d^2 +O(1) $. But how the number is $n \leq x$ such that $d^2 | n$ is not clear.

Can you please explain /deduce that.

1

There are 1 best solutions below

0
On BEST ANSWER

You might find it easier to think of this as asking how many multiples of $d^2$ there are up to $x$? These multiples are $d^2, 2d^2, 3d^3, \ldots$. The multiple $n d^2$ is less than or equal to $x$ when $nd^2 \leq x \iff n \leq x/d^2$. And in particular, the largest multiple will be $n = \lfloor x/d^2 \rfloor$.

This is why there are $\lfloor x/d^2 \rfloor$ multiples of $d^2$ up to $x$.