Problem 1413

The first half of the problem is quite easy to prove. If $n=2^{m}$, then on the one hand,
$$\sum_{k=1}^{2 n-1} k=\frac{(2 n-1) \times 2 n}{2}=\left(2^{m+1}-1\right) \cdot 2^{m}$$

is divisible by $2^{m}=n$. On the other hand, if $r \leqslant 2 n-2$, then
$$\sum_{k=1}^{r} k=\frac{r(r+1)}{2}$$

is not divisible by $2^{m}$, because one of $r$ and $r+1$ is odd, and the other does not exceed $(2 n-2)+1=2^{m+1}-1$, and thus is not divisible by $2^{m+1}$. Combining these two aspects, we know that $f\left(2^{m}\right)=2^{m+1}-1$.

Now suppose $n$ is not a power of 2, i.e., $n=2^{m} a$, where $m \geqslant 0, a>1$ is an odd number. We will prove that there exists a positive integer $r<2 n-1$ such that $2^{m+1} \mid r$ and $a \mid (r+1)$, so that
$$\sum_{k=1}^{r} k=\frac{r(r+1)}{2}$$

is divisible by $2^{m} a=n$, and thus $f(n)<2 n-1$.
To prove the above claim, we consider
$$x \equiv 0\left(\bmod 2^{m+1}\right), x \equiv -1(\bmod a)$$

Since $\left(2^{m+1}, a\right)=1$, by the Chinese Remainder Theorem, the system of congruences (1) must have a solution $x_{0}$, and all solutions are $x \equiv x_{0}\left(\bmod 2^{m+1} a\right)$, i.e., $x \equiv x_{0}(\bmod 2 n)$. Therefore, we can determine an $r$ that satisfies (1) and $0<r \leqslant 2 n$. Furthermore, by the second congruence in (1), we know that $r \neq 2 n$. And by the first congruence, we see that $r \neq 2 n-1$, so in fact $r<2 n-1$. This proves the existence of an $r$ that meets the requirements.