Problem 2. For a positive integer n, let R(n) be the sum of the remainders when n isdivided by 1, 2, . . . , n. For example, R(4) = 0 0 1 0 = 1, R(7) = 0 1 1 3 2 1 0 = 8.Find all positive integers n such that R(n) = n − 1.

1. Remainders in a Formula

For any divisor $k$, the remainder when $n$ is divided by $k$ is written as
$n \bmod k = n - k\,\left\lfloor \frac{n}{k} \right\rfloor$ where $\lfloor x \rfloor$ is the greatest integer \le x.

Hence the required sum is

$R(n)=\sum_{k=1}^{n} \bigl(n-k\,\lfloor n/k \rfloor\bigr).$

2. Useful Observation – The “Large k” Block

When $k > \frac{n}{2}$ we always have $\left\lfloor \frac{n}{k} \right\rfloor = 1,$ because $k$ fits into $n$ only once. Therefore for those $k$ values the remainder is simply $n \bmod k = n-k.$

If we set $m=\left\lfloor \frac{n}{2} \right\rfloor,$ then the indices $k=m+1,\,m+2,\dots, n$ (there are roughly $\frac{n}{2}$ of them) produce remainders forming a neat pattern $0,1,2,\dots$.

3. A Quick Lower–Bound from That Block

Even without computing any of the other remainders, we get

$\boxed{R(n)\;\ge\; \text{Sum of }(n-k)\text{ for }k>n/2}.$

For an even $n=2q$ that sum is

$\frac{q(q-1)}{2}.$

For an odd $n=2q+1$ that sum is

$\frac{q(q+1)}{2}.$

4. Compare with the Target $n-1$

We need $R(n)=n-1.$

So it is enough to show that our lower bound already beats $n-1$ for large enough $n$.

• Even $n=2q$: We want $\frac{q(q-1)}{2}\;\ge\;2q.$ Cancelling $q>0$ gives $q-1\ge4\;\Rightarrow\;q\ge5\;(n\ge10).$
• Odd $n=2q+1$: We want $\frac{q(q+1)}{2}\;\ge\;2q+1 \;\Longrightarrow\; q^2-3q-2\ge0 \;\Rightarrow\; q\ge4\;(n\ge9).$

Thus $\boxed{R(n)\;>\;n-1 \text{ for every } n\ge9}.$

5. Finish by Checking the Small Cases

Manually add remainders for $n=1$ to $8$:

Only $n=1$ and $n=5$ satisfy $R(n)=n-1$.

Key Ideas to Remember

1. Using $n \bmod k = n - k\,\lfloor n/k \rfloor$ links remainders to the floor function.
2. Splitting the sum into a convenient region (here, $k>n/2$) often gives a usable bound without full calculation.
3. Verifying a finite set of small cases finalises the result when inequalities handle the large cases.

Imagine Sharing Candies

Think of the number $n$ as n chocolates that you want to share with 1 friend, 2 friends, 3 friends … up to n friends (each different time).

• When you share with 1 friend, nothing is left over.
• With 2 friends, maybe 0 or 1 chocolate is left.
• Those "left-over" chocolates after every sharing are called remainders.

You are asked to add all those left-overs together. The problem wants to know for which special numbers $n$ does that total of leftovers equal exactly $n-1$ chocolates.

So the task is:
“Find all chocolate counts $n$ so that the sum of leftovers is $n-1$.”

Playing with small numbers by hand already shows:

• $n=1$ works (total leftover $=0$)
• $n=5$ works (total leftover $=4$)

The big question: Are there any others? The solution shows those two are the only ones!

Step-by-Step Solution

1. Write $R(n)$ using the floor function

   R(n) &= \sum_{k=1}^{n} \bigl(n-k\,\lfloor n/k \rfloor\bigr) \\ &= n^2 - \sum_{k=1}^{n} k\,\lfloor n/k \rfloor.\tag{1} \end{aligned}$$

2. Need to satisfy

   $R(n)=n-1\quad\Longrightarrow\quad \sum_{k=1}^{n} k\,\lfloor n/k \rfloor = n^2-n+1.$

   Direct evaluation is hard, so we build an inequality.

3. Focus on indices $k>n/2$. For these $k$ we have $\lfloor n/k \rfloor=1$, so

   $R(n) \ge \sum_{k=\lfloor n/2\rfloor+1}^{n} (n-k).$

4. Compute that tail sum

   • Even $n=2q$: $R(n) \ge \sum_{r=0}^{q-1} r = \frac{q(q-1)}{2}.$

   • Odd $n=2q+1$: $R(n) \ge \sum_{r=0}^{q} r = \frac{q(q+1)}{2}.$

5. Compare with the target $n-1$

   • Even case: Require $\frac{q(q-1)}{2} \ge 2q \;\Longrightarrow\; q\ge5 \;(n\ge10).$

   • Odd case: Require $\frac{q(q+1)}{2} \ge 2q+1 \;\Longrightarrow\; q\ge4 \;(n\ge9).$

   Hence for all $n\ge9$ we already have $R(n)\ge n$, so $R(n)=n-1$ is impossible.

6. Exhaustively test the small values $1\le n\le8$

   $n$	Remainders (list)	$R(n)$	$n-1$
   1	0	0	0 ✔
   2	0,0	0	1 ✘
   3	0,1,0	1	2 ✘
   4	0,0,1,0	1	3 ✘
   5	0,1,2,1,0	4	4 ✔
   6	0,0,0,2,1,0	3	5 ✘
   7	0,1,1,3,2,1,0	8	6 ✘
   8	0,0,2,0,3,2,1,0	8	7 ✘

7. Conclude

   $\boxed{\text{The only positive integers satisfying } R(n)=n-1 \text{ are } n=1 \text{ and } n=5.}$