数列の問題

方針 $j$ を固定して内側の和 $T_j=\sum _{i=1}^{n-1}\left[\frac{ij}{n}\right]$ を求める。$i$ と $n-i$ を組にするのが鍵である。

ガウス記号の性質 整数 $j$ と実数 $x$ について
$$[x]+[j-x]=\{\begin{array}{ll}j& (x\text{ が整数のとき})\\ j-1& (x\text{ が整数でないとき})\end{array}$$
が成り立つ。実際、$x$ が整数なら両方とも整数のまま足して $j$。整数でないなら $x=[x]+t$ $(0<t<1)$ と書けて $j-x=(j-[x]-1)+(1-t)$、$0<1-t<1$ より $[j-x]=j-[x]-1$ となる。

$T_j$ の計算 $i$ が $1$ から $n-1$ まで動くとき $n-i$ も $1$ から $n-1$ まで動くので
$$2T_j=\sum _{i=1}^{n-1}\left(\left[\frac{ij}{n}\right]+\left[\frac{(n-i)j}{n}\right]\right)=\sum _{i=1}^{n-1}\left(\left[\frac{ij}{n}\right]+\left[j-\frac{ij}{n}\right]\right).$$
$d=\gcd (n,j)$ とし、$n=d{n}^{\prime }$, $j=d{j}^{\prime }$（$n^{\prime }$ と $j^{\prime }$ は互いに素）と書くと、$\frac{ij}{n}=\frac{i{j}^{\prime }}{n^{\prime }}$ が整数になるのは $i$ が $n^{\prime }$ の倍数のときで、$1\leqq i\leqq n-1$ の範囲では $i=n^{\prime },2n^{\prime },\dots ,(d-1)n^{\prime }$ の $d-1$ 個である。よって上の性質から
$$2T_j=(n-1)(j-1)+(d-1),T_j=\frac{(n-1)(j-1)+\gcd (n,j)-1}{2}.$$

$j$ についての和
$$2S=(n-1)\sum _{j=1}^{n-1}(j-1)+\sum _{j=1}^{n-1}\gcd (n,j)-(n-1).$$
ここで $\sum _{j=1}^{n-1}(j-1)=\frac{(n-2)(n-1)}{2}$。

次に $G=\sum _{j=1}^{n-1}\gcd (2^m,j)$ を求める。$1\leqq j\leqq 2^m-1$ の $j$ を、$j$ を割り切る $2$ の最大の累乗 $2^t$ $(0\leqq t\leqq m-1)$ で分類すると、$\gcd (2^m,j)=2^t$ であり、そのような $j$ は $2^t\times (\text{奇数})$ で $2^m$ 未満のもの、すなわち $2^{m-t-1}$ 個ある。よって各 $t$ について寄与は $2^t\cdot 2^{m-t-1}=2^{m-1}$ で、
$$G=m\cdot 2^{m-1}=\frac{mn}{2}.$$

したがって
$$2S=\frac{(n-1{)}^2(n-2)}{2}+\frac{mn}{2}-(n-1),4S=(n-1{)}^2(n-2)-2(n-1)+mn.$$
$(n-1{)}^2(n-2)-2(n-1)=(n-1)\{(n-1)(n-2)-2\}=(n-1)(n^2-3n)=n(n-1)(n-3)$ なので
$$S=\frac{n\{(n-1)(n-3)+m\}}{4}=2^{m-2}\left\{(2^m-1)(2^m-3)+m\right\}.$$

確認 $m=2$（$n=4$）のとき、$j=1,2,3$ について $T_1=0,T_2=0+1+1=2,T_3=0+1+2=3$ で $S=5$。式は $2^0(3\cdot 1+2)=5$。$m=3$（$n=8$）のとき式は $2\cdot (7\cdot 5+3)=76$ で、$T_j$ の式から $0+4+7+12+14+18+21=76$ と一致する。

$\sum \sum \frac{ij}{n}=\frac{1}{n}{\left(\frac{n(n-1)}{2}\right)}^2=\frac{n(n-1{)}^2}{4}$。これを整数部分 $[\frac{ij}{n}]$ と小数部分 $\frac{r_{ij}}{n}$（$r_{ij}$ は $ij$ を $n$ で割った余り）に分ける。\n\n$i$ を固定し $d=\gcd (i,n)=2^k$ とする。$j=0,1,\dots ,n-1$ に対し $ij\mathrm{mod}n$ は $0,d,2d,\dots ,n-d$ をそれぞれちょうど $d$ 回とる。$j=0$ を除くと余りの和は変わらないので、余りの総和は $d\cdot d\cdot \frac{(n/d)(n/d-1)}{2}=\frac{n(n-d)}{2}$。よって小数部分の和は $\frac{n-d}{2}\cdot \frac{1}{1}\cdot \frac{1}{1}$、すなわち $\frac{n-d}{2}$。\n\n$i=1,\dots ,n-1$ のうち $\gcd (i,n)=2^k$ ($k=0,\dots ,m-1$) となるものは $2^{m-k-1}$ 個で、$d$ の総和は ${\sum }_{k=0}^{m-1}{2}^{m-k-1}\cdot 2^k=m\cdot 2^{m-1}=\frac{mn}{2}$。\n\n小数部分の総和は $\frac{1}{2}\left(n(n-1)-\frac{mn}{2}\right)$。\n\n$S=\frac{n(n-1{)}^2}{4}-\frac{n(n-1)}{2}+\frac{mn}{4}=\frac{n\{(n-1)(n-3)+m\}}{4}$。\n\n$n=2^m$ を代入して $S=2^{m-2}\{(2^m-1)(2^m-3)+m\}$。\n\n検算: $m=1$ ($n=2$) では $S=0$、式は $2^{-1}(1\cdot (-1)+1)=0$。$m=2$ ($n=4$) では積 $1,2,3,2,4,6,3,6,9$ を 4 で割った整数部分の和が $0+0+0+0+1+1+0+1+2=5$、式は $1\cdot (3\cdot 1+2)=5$。一致する。