# How many $m$ such that : $\sum\limits_{k=1}^m \left\lfloor\frac{m}{k}\right\rfloor$ be even?

Find how many $m \le 1000$ such that : $$\sum\limits_{k=1}^m \left\lfloor \frac{m}{k}\right\rfloor$$

be even ( $\lfloor x\rfloor$ is the largest integer smaller than $x$.)

I think that one case is $\sum\limits_{k=1}^m \left\lfloor \frac{m}{k}\right\rfloor$ is even if for every integer $k$ ( $1 \le k \le m$) $\left\lfloor\frac{m}{k}\right\rfloor$ be even or the number of odd number be even in $\sum\limits_{k=1}^m \left\lfloor\frac{m}{k}\right\rfloor$. $\big($ $\sum\limits_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor=\sum\limits_{i=1}^n d(i)$ where $d(\ )$ is the divisor function $\big)$

Hint, further to the comments $$\sum\limits_{k=1}^{m} \left \lfloor \frac{m}{k} \right \rfloor=\sum\limits_{k=1}^{m}d(k) \tag{1}$$

• $m=1 \Rightarrow \sum\limits_{k=1}^{1} \left \lfloor \frac{1}{k} \right \rfloor=\sum\limits_{k=1}^{1}d(k)=\color{blue}{1}$, i.e. $\color{red}{\{1\}}$ is the only perfect square or $\color{blue}{\left \lfloor \sqrt{1} \right \rfloor=1}$ in total.
• $m=2 \Rightarrow \sum\limits_{k=1}^{2} \left \lfloor \frac{2}{k} \right \rfloor=\sum\limits_{k=1}^{2}d(k)=1+2=\color{blue}{3}$, i.e. $\color{red}{\{1\}}$ is the only perfect square or $\color{blue}{\left \lfloor \sqrt{2} \right \rfloor=1}$ in total.
• $m=3 \Rightarrow \sum\limits_{k=1}^{3} \left \lfloor \frac{3}{k} \right \rfloor=\sum\limits_{k=1}^{3}d(k)=1+2+2=\color{blue}{5}$, i.e. $\color{red}{\{1\}}$ is the only perfect square or $\color{blue}{\left \lfloor \sqrt{3} \right \rfloor=1}$ in total.
• $m=4 \Rightarrow \sum\limits_{k=1}^{4} \left \lfloor \frac{4}{k} \right \rfloor=\sum\limits_{k=1}^{4}d(k)=1+2+2+3=\color{blue}{8}$, i.e. $\color{red}{\{1, 4\}}$ are the only perfect squares or $\color{blue}{\left \lfloor \sqrt{4} \right \rfloor=2}$ in total.
• $m=5 \Rightarrow \sum\limits_{k=1}^{5} \left \lfloor \frac{5}{k} \right \rfloor=\sum\limits_{k=1}^{5}d(k)=1+2+2+3+2=\color{blue}{10}$, i.e. $\color{red}{\{1, 4\}}$ are the only perfect squares or $\color{blue}{\left \lfloor \sqrt{5} \right \rfloor=2}$ in total.

Is the pattern visible now? It should be easy to show it by induction.

• answer is exactlly all numbers such that ${\left \lfloor \sqrt{n} \right \rfloor=2k}$ ? – amir bahadory Apr 15 '18 at 14:40
• Yes! Or $\sum\limits_{k=1}^{m} \left \lfloor \frac{m}{k} \right \rfloor$ is even $\iff \left \lfloor \sqrt{m} \right \rfloor$ is even. This should help you to answer "how many $m \leq 1000$ ... are even". – rtybase Apr 15 '18 at 14:44
• ${\left \lfloor \sqrt{m} \right \rfloor} \le 31$ then answer is 15. – amir bahadory Apr 15 '18 at 14:56
• You will have to go through all $m \in \{1,2,3,...,1000\}$ or try to reveal another pattern, like $m \in \{4,5,...,8\}$, $m \in \{16,17,...,24\}$, $m \in \{36,17,...,48\}$ ... all give even $\left \lfloor \sqrt{m} \right \rfloor$. – rtybase Apr 15 '18 at 15:18