切り捨て総和の公式 - RPGツクールと数学のブログ

過去ブログの転載です。

$\displaystyle \sum_{k=1}^{n} \left\lfloor \frac{pk+r}{q} \right\rfloor$ を求めます。ただし、 $\displaystyle \frac{pk+r}{q}$ は正の数のみという条件が要ります。マイナス入ったら変形してこの形にします。

$\displaystyle \left\lfloor \cdot \right\rfloor$ は床関数です。中身が正の数なので、この場合は小数点以下切り捨てと同義です。要するに有理数の切り捨てしていったものを足していったらどうなるの、という式です。

何でこんなものを求めるのかというと、ベズー方程式（一次の不定方程式）の解の個数を計算したくて、その途中計算で必要になったためです。床関数とか天井関数とか使っていると、案外色んな所で登場する総和の式なので、公式にしてしまっておけば何かと便利だろうということでございます。

結論から言えば、この総和の式は閉じた式で表わすことが出来ません。何でしょうね。特別な場合を除いて、どうがんばってもシグマが残ってしまいます。未完成なのか仕方ないのか判断が付かないのですけど、多分初等関数では表現できないでしょう。

そこで、まあ、これなら計算しやすくなるだろう、という形にまで変形することを試みます。

まず、導入として $\displaystyle n$ が $\displaystyle q$ の倍数だったときのことを考えてみます。

$\displaystyle \sum_{k=1}^{30}\frac{4k+3}{5}$ を例にして、愚直に足し算していってみましょう。

1＋2＋3＋3＋4
＋5＋6＋7＋7＋8
＋9＋10＋11＋11＋12
＋13＋14＋15＋15＋16
＋17＋18＋19＋19＋20
＋21＋22＋23＋23＋24

分母が5なので5個ずつ足して縦に並べてみてます。
当然ですけど、 $\displaystyle n$ が $\displaystyle q$ の倍数だときちんとこのように $\displaystyle q$ 個ずつ並べることができます。

すると、最初の(1＋2＋3＋3＋4)というのを土台にして、これらすべてに4を足したものが次の(5＋6＋7＋7＋8)になっているのが確認できますね。その次の(9＋10＋11＋11＋12)も同じくその前のに4ずつ足したものになっています。分子のパターンが $\displaystyle k$ を5で割った余りで変化するため、このように周期性が出るのです。

最初の項を $\displaystyle (m, l)=(1, 1)$ として、上の並べた数の $\displaystyle m$ 行 $\displaystyle l$ 列目は $\displaystyle 4(m-1)+\left\lfloor \frac{4l+3}{5} \right\rfloor$ と表現できることが分かります。

一般に、 $\displaystyle p(m-1)+ \left\lfloor \frac{pl+r}{q} \right\rfloor$ と表現出来ることが分かりますね。

従って、 $\displaystyle n$ が $\displaystyle q$ の倍数なら $\displaystyle \sum_{k=1}^{n}\frac{pk+r}{q}$ は
$\displaystyle =\sum_{m=1}^{\frac{n}{q}} \sum_{l=1}^{q} \left( p(m-1)+ \left\lfloor \frac{pl+r}{q} \right\rfloor \right)$
と変形することが可能になります。
これを何やかんやして計算していけば、
$\displaystyle =\frac{n}{q} \left( \frac{p}{2} (n-q)+ \sum_{k=1}^{q} \left\lfloor \frac{pk+r}{q} \right\rfloor \right)$
まで計算することが出来ます。
後は残ってるシグマについて考察すればOKですね。

$\displaystyle \sum_{k=1}^{q}\left\lfloor \frac{pk+r}{q} \right\rfloor$ を求めましょう。今度は足し算の項数と分母の値が同じ場合です。ほとんどこれが求めたいものの核心です。難しいですね。これはちょっとややこしいことになります。

例えば切り捨ての無い形である $\displaystyle \sum_{k=1}^{7} \frac{11k}{7}$ について考えてみます。これは書き下すと $\displaystyle =\frac{11}{7}+\frac{22}{7}+\frac{33}{7}+\frac{44}{7}+\frac{55}{7}+\frac{66}{7}+\frac{77}{7}$ になりますね。
また、切り捨てがない場合は普通に総和の公式を使って
$\displaystyle \sum_{k=1}^{7}\frac{11k}{7}=\frac{11}{7}\times7\times\frac{8}{2}=44$ とすぐ求められます。

切り捨ての総和は、ここから小数部分の総和を引き算してやれば得られます。 $\displaystyle \frac{11k}{7}$ の小数部分だけに着目して総和を計算してみましょう。

11／7＝1＋4／7
22／7＝3＋1／7
33／7＝4＋5／7
44／7＝6＋2／7
55／7＝7＋6／7
66／7＝9＋3／7
77／7＝11＋0／7
よく見ると、小数部分が全部違いますね。

分母の個数と足し算の個数がどちらも7個で、分子を並べ替えると0～6すべてが揃います。不思議なことのようですが、これは必ず成り立ちます。
$\displaystyle p, q$ が互いに素なとき、 $\displaystyle pk \mod q(0 \le k \lt q)$ はすべて異なります。もし同じ値のものがあったら矛盾するから、として示すことが出来ます。
一方で $\displaystyle \frac{11k}{7}$ の小数部分は $\displaystyle \frac{11k \mod 7}{7}$ ですから、
$\displaystyle 0 \le k \lt 7$ の範囲だと $\displaystyle (11k \mod 7)$ がすべて異なるため、小数部分がすべて異なると言えるのです。

すべて異なるのであれば、並べ替えれば必ず0＋1＋2＋3＋4＋5＋6＝21と計算出来るので、すべて足し算しなくても小数部分は $\displaystyle \frac{21}{7}=3$ と計算することが可能です。

一般に $\displaystyle p, q$ が互いに素であれば、 $\displaystyle 0 \le k \lt q$ の範囲における $\displaystyle \frac{pk}{q}$ の小数部分の総和は $\displaystyle \frac{q-1}{2}$ となるので
$\displaystyle \sum_{k=1}^{q} \left\lfloor \frac{pk}{q} \right\rfloor = \left( \sum_{k=1}^{q} \frac{pk}{q} \right)-q\frac{q-1}{2}=\frac{1}{2} (pq+p-q+1)$ が得られます。

ただしこれは $\displaystyle p, q$ が互いに素じゃないと成り立たないので、一般の場合についても考える必要があります。

単に $\displaystyle \sum_{k=1}^{q}\left\lfloor\frac{pk}{q}\right\rfloor$ だったら約分すれば済む話ではあるのですが、求めたいのは $\displaystyle \sum_{k=1}^{q}\left\lfloor\frac{pk+r}{q}\right\rfloor$ なので、 $\displaystyle r$ のせいで約分出来ないことがあるためです。

$\displaystyle \sum_{k=1}^{8}\left\lfloor \frac{6k+1}{8}\right\rfloor$ について考えてみましょう。
$\displaystyle \sum_{k=1}^{8}\frac{6k+1}{8}=\frac{7}{8}+\frac{13}{8}+\frac{19}{8}+\frac{25}{8}+\frac{31}{8}+\frac{37}{8}+\frac{43}{8}+\frac{49}{8}$ ですが、
それぞれの小数部分の総和は $\displaystyle \frac{7}{8}+\frac{5}{8}+\frac{3}{8}+\frac{1}{8}+\frac{7}{8}+\frac{5}{8}+\frac{3}{8}+\frac{1}{8}$ となります。

小数部分の分子は7, 5, 3, 1が2回繰り返されているようですね。これは0＋1＋2＋3を2倍してそれぞれに1足して1＋3＋5＋7とし、2回足されていることから2倍して小数部分の分子の総和が得られます。

$\displaystyle \sum_{k=1}^{8}\frac{6k+1}{8}=\sum_{k=1}^{8}\left(\frac{6k}{8}+\frac{1}{8}\right)=\sum_{k=1}^{8}\left(\frac{3k}{4}+\frac{1}{8}\right)$

と変形できるので、約分した $\displaystyle \frac{3k}{4}$ を2周期分足すから2回繰り返され、約分前はその2倍ですから、分子の間隔が2ずつになって0＋2＋4＋6となります。

この2周期というのは6と8の最大公約数 $\displaystyle \gcd(6, 8)=2$ から来ていますね。 $\displaystyle \frac{1}{8}$ を足した分がずれになって、1＋3＋5＋7となっています。

ずれの方は、この場合は単に1ずつ足せばOKですけれど、実際は小数部分の分子は分母である8以上にはなりませんので、8で割った余りのみが足されます。

でも、どんな風に足したって最大公約数が2の場合は、並べ替えれば0＋2＋4＋6 か 1＋3＋5＋7 の2通りしかありませんので、
$\displaystyle (0+2+4+6)+4\times(1 \mod 2)$ と考えてやれば良いことになります。

従って以上を一般化して、 $\displaystyle \alpha =\frac{q}{\gcd(p, q)}$ のとき（ $\displaystyle \alpha$ は1周期分の足し算個数です）

$\displaystyle \frac{pk+r}{q}$ の各小数部分の総和は、
$\displaystyle (0+1+2+\cdots+(\alpha-1))\times \gcd(p, q)+\alpha \times (r \mod \gcd(p, q))$
と表され、これを変形していくと、
$\displaystyle =\frac{q-\gcd(p, q)}{2}+(r \mod \gcd(p, q))$
となります。ねーややこしいでしょ。自分でももうよくわかんないよ。

この小数部分の式を利用して、
$\displaystyle \sum_{k=1}^{q}\left\lfloor\frac{pk+r}{q}\right\rfloor=\frac{1}{2} (pq+p-q+2r+\gcd(p, q))-(r \mod \gcd(p, q))$
を作ることが出来ます。
$\displaystyle p, q$ が互いに素だったら $\displaystyle \gcd(p, q)=1$ を代入してやればいいので、さらに $\displaystyle r=0$ としてやれば $\displaystyle \sum_{k=1}^{q} \left\lfloor \frac{pk}{q} \right\rfloor$ と同じ式になりますね。

$\displaystyle \sum_{k=1}^{n}\left\lfloor\frac{pk+r}{q}\right\rfloor=\frac{n}{q} \left\{ \frac{p}{2} (n-q)+\sum_{k=1}^{q}\left\lfloor\frac{pk+r}{q}\right\rfloor\right\}$
でしたから、ここの右辺のシグマの式に代入してやれば、
$\displaystyle =\frac{n}{2q} (pn+p-q+2r+\gcd(p, q)-2(r \mod \gcd(p, q)))$
が得られます。これが $\displaystyle n$ が $\displaystyle q$ の倍数のときの答えです。
$\displaystyle q$ の倍数になっていれば、多少長いけど閉じた式で表わすことが可能です。

問題なのは $\displaystyle n$ が $\displaystyle q$ の倍数でないときになります。
↓さっきこんな足し算の式を提示しましたけれど、

1＋2＋3＋3＋4
＋5＋6＋7＋7＋8
＋9＋10＋11＋11＋12
＋13＋14＋15＋15＋16
＋17＋18＋19＋19＋20
＋21＋22＋23＋23＋24

$\displaystyle n$ が $\displaystyle q$ の倍数でないときはきれいに並びません。そのため、きれいに並ぶところだけを切り取って、残りを別途足し算するということになります。

$\displaystyle \sum_{k=1}^{n}\left\lfloor\frac{pk+r}{q}\right\rfloor$
$\displaystyle =\sum_{k=1}^{q\left\lfloor\frac{n}{q}\right\rfloor}\left\lfloor\frac{pk+r}{q}\right\rfloor+\sum_{k=q\left\lfloor\frac{n}{q}\right\rfloor+1}^{n}\left\lfloor\frac{pk+r}{q}\right\rfloor$
こんな風に分けてやれば、第一項は上限が $\displaystyle q$ の倍数ですからさっき作った公式から
$\displaystyle \sum_{k=1}^{q\left\lfloor\frac{n}{q}\right\rfloor}\left\lfloor\frac{pk+r}{q}\right\rfloor=\frac{1}{2}\left\lfloor\frac{n}{q}\right\rfloor\left(pq\left\lfloor\frac{n}{q}\right\rfloor+p-q+2r+\gcd(p, q)-2(r \mod \gcd(p, q))\right)$
となりますので、第二項について考えます。

範囲の下限を1からにするために $\displaystyle u=k-q\left\lfloor\frac{n}{q}\right\rfloor$ と変数変換すると、
$\displaystyle n-q\left\lfloor\frac{n}{q}\right\rfloor=n \mod q$ になることを利用して、
$\displaystyle \sum_{u=1}^{n \mod q} \left\lfloor \frac{p(u+q\left\lfloor\frac{n}{q}\right\rfloor)+r}{q} \right\rfloor$
$\displaystyle =p\left\lfloor\frac{n}{q}\right\rfloor (n \mod q)+\sum_{u=1}^{n \mod q}\left\lfloor\frac{pu+r}{q}\right\rfloor$
となります。

最後に残った $\displaystyle \sum_{u=1}^{n \mod q}\left\lfloor\frac{pu+r}{q}\right\rfloor$ ですが、これはどうしようもないと思います。
さっき $\displaystyle pk \mod q(0 \le k \lt q)$ はすべて異なるから、何が来たって並べ替えれば、きれいに $\displaystyle 0+1+2+\cdots+(q-1)$ になる、ということでしたけれど、このシグマを求めるためには任意の場所で区切ったときの $\displaystyle pk \mod q$ の総和が必要です。

しかし、どうもそれは閉じた式で表わすことが出来ないらしくて、これ以上シグマを外すことは不可能だろうということになりました。もし閉じた式で表わすことが出来るのでしたらとっても嬉しいことになるのですけど、現状よくわかんないので、ここで計算はおしまいです。 $\displaystyle n \mod q$ って多分すごい小さい値になるだろうから、まあ、いいんじゃないかなぁ……

この部分だけ順番に足し算していくことになりますが、 $\displaystyle q$ がでかいときは大変そうです。

以上から、一般の $\displaystyle p, q, r, n$ （全部非負整数）において、

$\displaystyle \sum_{k=1}^{n}\left\lfloor\frac{pk+r}{q}\right\rfloor$
$\displaystyle =\frac{1}{2}\left\lfloor\frac{n}{q}\right\rfloor \left( pq\left\lfloor\frac{n}{q}\right\rfloor+p-q+2r+\gcd(p, q)-2(r \mod \gcd(p, q))\right)$
$\displaystyle +p\left\lfloor\frac{n}{q}\right\rfloor(n \mod q)+\sum_{u=1}^{n \mod q}\left\lfloor\frac{pu+r}{q}\right\rfloor$