jasperE3 wrote: Let $S$ be the set of all squarefree numbers and $n$ be a natural number. Prove that $$\sum_{k\in S}\left\lfloor\sqrt{\frac nk}\right\rfloor=n.$$ Every positive integer $x$ can be written in a unique fashion as $x=sd^2$ where $s \in S$ and $d\geq 1$. Hence $\{1,...,n\}=\cup_{s \in S}\{sd^2 | d^2 \leq \frac{n}{s} \}$ and the result follows.

We will prove $\sum_{k\in S}\left\lfloor\sqrt{\frac nk}\right\rfloor=n$ by induction over $n$. For $n=1$ and $n=2$, $\sum_{k\in S}\left\lfloor\sqrt{\frac 1k}\right\rfloor=\left\lfloor\sqrt{\frac 11}\right\rfloor=1$ and $\sum_{k\in S}\left\lfloor\sqrt{\frac 2k}\right\rfloor=\left\lfloor\sqrt{\frac 21}\right\rfloor+\left\lfloor\sqrt{\frac 22}\right\rfloor=2$. Assume $\sum_{k\in S}\left\lfloor\sqrt{\frac nk}\right\rfloor=n$ for $n=m$. Let's prove $\sum_{k\in S}\left\lfloor\sqrt{\frac {m+1}k}\right\rfloor=m+1$. Let $m+1=r\cdot t^2$ where $r$ is a squarefree number and $t$ is a positive integer. We will prove $\left\lfloor\sqrt{\frac {m+1}k}\right\rfloor=\left\lfloor\sqrt{\frac mk}\right\rfloor$ for all squarefree numbers except $r$ and $\left\lfloor\sqrt{\frac {m+1}r}\right\rfloor=\left\lfloor\sqrt{\frac mr}\right\rfloor+1$. This will complete the proof. Lemma 1: $\left\lfloor\sqrt{u+\varepsilon}\right\rfloor=\left\lfloor\sqrt{u}\right\rfloor$ for every positive integer $u$ and for every real number $\varepsilon$ where $0\leq \varepsilon<1$. Proof: Let's say $x^2\leq u\leq x^2+2x$, $x$ is an integer. Then $u+\varepsilon \leq x^2+2x+\varepsilon<(x+1)^2$. Hence, $\left\lfloor\sqrt{u}\right\rfloor=x=\left\lfloor\sqrt{u+\varepsilon}\right\rfloor$. Lemma 2: For every positive integer $u$, $\left\lfloor\sqrt{u+1}\right\rfloor=\left\lfloor\sqrt{u}\right\rfloor+1\Leftrightarrow u+1$ is a perfect square. Proof: Let's say $x^2\leq u\leq x^2+2x$, $x$ is an integer. Then, $\left\lfloor\sqrt{u}\right\rfloor=x$. Hence, $\left\lfloor\sqrt{u+1}\right\rfloor=x+1$ iff $u+1\ge (x+1)^2$ iff $u\ge x^2+2x$ iff $u=x^2+2x$ iff $u+1$ is a perfect square. We know that $\left\lfloor\sqrt{\frac {m+1}k}\right\rfloor=\{\left\lfloor\sqrt{\frac mk}\right\rfloor,\left\lfloor\sqrt{\frac mk}\right\rfloor+1\}$ Let $m=ak+b$ where $0\leq b\leq k-1$ for a fixed $k$. $\left\lfloor\sqrt{\frac{m+1}k}\right\rfloor=\left\lfloor\sqrt{\frac mk}\right\rfloor+1=\left\lfloor\sqrt{\frac {ak+b}k}\right\rfloor+1=\left\lfloor\sqrt{a+\frac bk}\right\rfloor+1=\left\lfloor\sqrt{a}\right\rfloor+1\Leftrightarrow \left\lfloor\sqrt{\frac {ak+b+1}k}\right\rfloor=\left\lfloor\sqrt{a}\right\rfloor+1\Leftrightarrow$ $ \left\lfloor\sqrt{a+\frac{b+1}k}\right\rfloor=\left\lfloor\sqrt{a}\right\rfloor+1\Leftrightarrow b+1=k\land a+1$ is a perfect square by Lemma 1, Lemma 2 and the fact that $b+1\leq k$. $b+1=k\Leftrightarrow k|m+1$ (We have $m=ak+b$). Then, $b+1=k\land a+1$ is a perfect square $\Leftrightarrow m+1=k(a+1)$ where $k\in S$ and $a+1$ is a perfect square. We have $m+1=r\cdot t^2$. Hence, $m+1=k(a+1)$ where $k\in S$ and $a+1$ is a perfect square $\Leftrightarrow k=r \land a+1=t^2$. Thus, $\left\lfloor\sqrt{\frac {m+1}k}\right\rfloor=\left\lfloor\sqrt{\frac mk}\right\rfloor$ for all squarefree numbers except $r$ and $\left\lfloor\sqrt{\frac {m+1}r}\right\rfloor=\left\lfloor\sqrt{\frac mr}\right\rfloor+1$. Hence completes the proof.