√の整数部分の和(床関数と数え上げ)

方針

解答

⓪ 発想 — どう考え始めるか。 $[\sqrt{k}]$ は、$k$ が平方数に達するたびに1増える階段だ。$k$ の順に足すのではなく、同じ値をとる $k$ の群れごとに「値×個数」で足す。

$[\sqrt{k}]=m$ になるのは $m^2\le k<(m+1{)}^2$ のときで、個数は $(m+1{)}^2-m^2=2m+1$ 個。

ただし $k=100$ でちょうど $m=10$ の群れが始まった直後に切れる — 端の群れだけ1個で別扱いする。

① 値ごとに個数を数える。 $m=1,\dots ,9$ では $[\sqrt{k}]=m$ となる $k$ が $2m+1$ 個($m^2$ から $(m+1{)}^2-1$ まで)。$k=100=10^2$ だけ $[\sqrt{100}]=10$ で $1$ 個。

② 和を作る。 $$\sum _{k=1}^{100}[\sqrt{k}]=\sum _{m=1}^{9}m\cdot (2m+1)+10\cdot 1.$$ ③ 計算する。 $\sum _{m=1}^9(2m^2+m)=2\sum _{m=1}^9{m}^2+\sum _{m=1}^{9}m=2\cdot 285+45=570+45=615$。よって $$\sum _{k=1}^{100}[\sqrt{k}]=615+10=625.$$

まとめ $[\sqrt{k}]=m$ の $k$ は $2m+1$ 個。値×個数を足して $615+10=625$。整数部分(床関数)と数え上げの融合。$\sum m^2=\frac{9\cdot 10\cdot 19}{6}=285$ を用いた。

発展 — 一歩先へ。 上限を一般の $N$ にすると ${\sum }_{k\le N}[\sqrt{k}]={\sum }_{m^2\le N}(N-m^2+1)$ で、およそ $N\sqrt{N}-\frac{(\sqrt{N}{)}^3}{3}\approx \frac{2}{3}{N}^{3/2}$ — 「$\sqrt{k}$ の和の親戚」として成長のオーダーまで読める。この「階段の和=長方形領域の格子点」の見方は、約数の個数の和など、ガウス記号がらみの数え上げの万能工具になる。

別解

数える向きを交換する(端の場合分けが消える)。 $[\sqrt{k}]$ の正体は「$k$ 以下の平方数の個数」:

$$[\sqrt{k}]=\#\{m\ge 1:m^2\le k\}$$

だから和は、条件 $m^2\le k\le 100$ を満たす組 $(m,k)$ の総数。$k$ ごとでなく $m$ ごとに数え直すと、$m$ を固定したとき $k$ は $m^2$ から $100$ までの $101-m^2$ 個:

$$\sum _{k=1}^{100}[\sqrt{k}]=\sum _{m=1}^{10}(101-m^2)=1010-385=625$$

本解で必要だった「$m=10$ の群れは1個だけ」という端の別扱いが、この向きでは式が勝手に処理してくれる($m=10$ で $101-100=1$)。群れで数えるか、向きを交換するか — 二重数えの表を縦に読むか横に読むかの選択だ。