0
$\begingroup$

For a fixed $n$ find the number of $m$'s for which $\lfloor{\sqrt m}\rfloor \mid m$, for all natural numbers $m\le n$. I have been trying to write it as $m=\lfloor{\sqrt m}\rfloor \cdot k$, where $k$ is a natural number. Putting it in the ussual floor inequalities doesn't help me much.

$\endgroup$
  • $\begingroup$ If you only need to find how many $n$ there are, then noting that this holds for square $n$ would seem to suffice. $\endgroup$ – Milo Brandt Mar 27 '15 at 22:33
  • $\begingroup$ @Meelo sry, I didnt write something, so I will correct it now $\endgroup$ – HeatTheIce Mar 27 '15 at 22:35
  • $\begingroup$ @Meelo: I can think of some other examples. $\endgroup$ – Ross Millikan Mar 27 '15 at 22:40
  • $\begingroup$ For exaplme: let n=100. Now we have to find all $m\le 100$ so that $\lfloor{\sqrt m}\rfloor $ divides $m$ $\endgroup$ – HeatTheIce Mar 27 '15 at 22:42
  • 1
    $\begingroup$ I think what you want is this OEIS. Take a look. $\endgroup$ – mathlove Mar 27 '15 at 22:43
1
$\begingroup$

First note that $m$ can take all the perfect square values. Assume that $m$ is npt a perfect square. So there exist a unique $t$ such that

$t^2<m<(t+1)^2$

assume that

$m=t^2+k$ where $k\in{\mathbb{N}}$ and $k<2t+1$

so $\lfloor\sqrt{m}\rfloor=t$

now $\lfloor\sqrt{m}\rfloor|m$

so $t|t^2+k$

so $t|k$.

But $k<2t+1$

$k=t$ or $k=2t$

Hence there are two such possible $m$ between two perfect squares i.e. $t^2+t$ and $t^2+2t$ where $t^2<m<(t+1)^2$.

Now if $n=a^2$ then obviously there are $a$ perfect square $m$ and $2(a-1)$ non perfect square.

Hence there are $3a-2$ such $m$ for $n=a^2$

now $n$ is not a perfect square. We can uniquely find $a$ such that

$a^2<n<(a+1)^2$ or in other words $\lfloor{\sqrt{n}}\rfloor=a$

case-$1$

$a^2<n<a^2+a$

In this case again there would be $3a-2$ possible cases by the same logic.

case-$2$

$a^2+a\le{n<a^2+2a}$

In this case, by simple counting, there would be $3a-1$ possibilities

case-$3$

$a^2+2a\le{n}<(a+1)^2$

In this case there would be $3a$ possible $m$.

$\endgroup$
2
$\begingroup$

In many cases, writing out some of the actual solutions may help you to see the pattern. I think this is one of those cases.

Consider the numbers for which $\lfloor \sqrt{m} \rfloor = 4$, say. These are the numbers 16 through 24. There are exactly three numbers in this range divisible by $4$: $16, 20, 24$.

Next, consider the numbers for which $\lfloor \sqrt{m} \rfloor = 5$. These are the numbers 25 through 35. Again, there are exactly three numbers in this range divisible by $5$: $25, 30, 35$.

You might observe, then, that for any $m$, there are always three integers evenly divisible by $m$ in the range $[m^2, (m+1)^2-1]$: $m^2$, $m^2+m$, and $m^2+2m$.

Therefore, let $p = \lfloor \sqrt{n} \rfloor$. The answer is $3p$ for $n = p^2 + 2p$; it is $3p-1$ for $n$ in the range $[p^2+p, p^2+2p-1]$; and it is $3p-2$ for $n$ in the range $[p^2, p^2+p-1]$.

$\endgroup$
  • 3
    $\begingroup$ Perhaps closer to $3 \sqrt{n}$ than to $3n$ but even that is not exact. $\endgroup$ – Henry Mar 27 '15 at 22:46
  • $\begingroup$ Yup. Sorry, I misread the question slightly. I think I've fixed the answer. $\endgroup$ – Brian Tung Mar 27 '15 at 22:50

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.