OMC217(E)

　$2^{k}$ を約数として持つ $1$ 以上 $n$ 以下の整数の個数を $C_{n,k}$ で表すことにすると， $$\sum_{k = 1} ^ {n} f(k) = \sum_{k = 0}^{\infty} 2^{k}C_{n,k}$$ となる．ここで，$C_{n,k} = \bigg \lfloor {\cfrac{n}{2^{k}}} \bigg \rfloor$ であるから，正の整数 $x,y$ に対して $x\% y$ で $x$ を $y$ で割ったあまりを表すことにすると， $$2^{k}C_{n,k} = n - n\% 2^{k}$$ である．今，$2^{1000} \le n \lt 2^{1001} - 1$ の場合は，$C_{n,k} \gt 0$ となる $k$ の範囲は $0 \leq k \leq 1000$ であるので， $$g(n) = -1000n + \sum_{k = 0}^{1000} (n - n \% 2^{k}) = n - \sum_{k = 0}^{1000} n \% 2^{k}$$ と分かる．
　ここで，$n$ の $2$ 進数表記を $b_{1000}b_{999} \cdots b_{0}$ とする．このとき，$n\%2^0 = 0$ であり，$k\ge1$ のときには $$n\%2^{k} = \sum_{i = 0}^{k - 1}2^{i}b_i$$ となるため， $$\sum_{k = 0}^{1000} n\% 2^{k} = \sum_{k = 0}^{1000}2^{k}(1000-k)b_{k}$$ を得る．これより，$b_{1000} = 1$ であることに気をつければ， $$g(n) = n - \sum_{k = 0}^{1000} \ n ％ 2^{k} = 2^{1000} - \sum_{k = 0}^{999}2^{k}(999 - k)b_{k}$$ が分かる．ここで，$\displaystyle\sum_{k = 0}^{999}2^{k}(999 - k)b_{k}$ の各項の $b_k$ の係数は，$k$ に対して ($k = 999$ を除き) 広義単調増加である．また， $$\sum_{k = 0}^{4}2^{k}(999 - k) \lt 2^{5}(999-5),\quad \sum_{k = 0}^{1}2^{k}(999 - k) \lt 2^{2}(999-2)$$ がそれぞれ成り立つので，$g(n)$ のとり得る $37$ 番目に大きい値は $$2^{1000} - (2^5(999-5) + 2^2(999-2)) = 2^{1000} - 35796$$ であり，これを $997$ で割ったあまりはフェルマーの小定理により $\bf112$ と分かる．

補足.　最後の議論と同様に考えることで，$n - 2^{1000}$ が十分に小さい範囲では $g(n)$ は狭義単調減少であることがわかる．