# When Is the Remainder Less Than The Quotient

I was given the problem:

Let $f(n)$ be the number of times $a$ is $n$-well for $1\le a \le n$. An integer, $a$, is $n$-well if $$\left\lfloor\frac{n}{\left\lfloor \frac{n}{a}\right\rfloor}\right\rfloor=a$$ Compute $$\sum_{n=1}^{9999}f(n)$$

What I did was say that $n=qa+r$ where $0\le r < a$. Then the $n$-well equation simplifies down to $$\left\lfloor\frac{qa+r}{\left\lfloor \frac{qa+r}{a}\right\rfloor}\right\rfloor=\left\lfloor\frac{qa+r}{q}\right\rfloor=a$$ which is clearly the case when $r<q$. So I am wondering how I would go about finding when the remainder is less than the "quotient". The goal would be to get a closed form for $f$, or at least find a pattern in its outputs for integer inputs.

• Considering all the cases when you get a particular value of the quotient may help. – Siddharth Joshi Feb 20 '16 at 18:26

## 1 Answer

Notice that for a given $n$ the only $n$ - well numbers are $\left [ {n\over 1} \right ], \left [ {n\over 2} \right ], ..., \left[ {n\over n} \right ]$ which can be deduced by finding the number of $n$ - well number for a given coefficient. These numbers may not be all distinct and therefore we need to find the distinct ones among these numbers and then add them in order to compute $f(n)$.