For a positive integer $n$, let $r(n)$ denote the sum of the remainders when $n$ is divided by $1,2,…,n$ respectively. Prove that $r(k)=r(k-1)$ for infinitely many positive integers $k$.
($1981$ Kürschák Competition)
My idea is, let $f(n,k)$ denotes remainder $n$ divided by $k$. Then it's easy to see that if $k\mid n$, $f(n,k)+k-1=f(n-1,k)$ and else, $f(n,k)=1+f(n-1,k)$. Then the condition becomes for $q<k$,
$\sum_{i=1}^{k}f(k,i)=\sum_{i=1}^{k-1}f(k-1,i)=\sum_{q\nmid k}f(k-1,q)+\sum_{q\mid k}f(k-1,q)=\sum_{q\nmid k}(f(k,q)-1)+\sum_{q\mid k}(f(k,q)+q-1)=\sum_{i=1}^{k-1}f(k,i)+\sum_{q\mid k}q-(n-1)\implies\sum_{q\mid k}q=k-1…(*)$
Now how to prove there is infinitely many positive integer $k$ satisfies $(*)$?. Anyone can help me?
Best Answer
Hint: For all $i$,$$r(2^i-1)=r(2^i)$$