4
$\begingroup$

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)$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ answer is exactlly all numbers such that ${\left \lfloor \sqrt{n} \right \rfloor=2k}$ ? $\endgroup$ – amir bahadory Apr 15 '18 at 14:40
  • $\begingroup$ 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". $\endgroup$ – rtybase Apr 15 '18 at 14:44
  • $\begingroup$ ${\left \lfloor \sqrt{m} \right \rfloor} \le 31$ then answer is 15. $\endgroup$ – amir bahadory Apr 15 '18 at 14:56
  • 1
    $\begingroup$ 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$. $\endgroup$ – rtybase Apr 15 '18 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.