２進数表現を１０進数表現に読み替える関数の積分

大学のときに友人から出された挑戦状(?)である。当時、区分求積で上下に挟んで解いた覚えがある。そもそも収束するかどうか怪しい関数だったのでわりと厳密に扱ったので苦労した気がする。最近ふとしたことで思い出したのでまた解いてみようと思う。同じやり方をやってもつまらないので今回は厳密性を落として直感的にやってみる。
そもそもそういう関数かというと口で表現してもよく分からないので具体的に書いてみると
f(1) = 1
f(2) = 10
f(3) = 11
f(4) = 100
f(10) = 1010
である。単なる２進数ではないかと思われるが、関数の中身も右辺も両方とも１０進数である。グラフに描けといわれるとつらいがおそらくかなりガタガタな形になるのではないかと思われる(証明はしてないがおそらく全区間で不連続)。で、この関数を０から１まで定積分するわけである。
$\int_0^1 dx f(x)$
さて、実際やるに当たって収束性とかいろいろ調べなきゃいけないのだが今回は収束するという前提でやっていく。区分求積で下半分のみ議論する。そうすると以下になる。
$\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1} f( \frac{k}{n} )$
おなじみの式ですね。さて、今回このままでは議論しにくいので、n→2^nとします。
$\lim_{n\to\infty}\frac{1}{2^n}\sum_{k=0}^{2^n-1} f( \frac{k}{2^n} )$
ここで極限の中身をｎの数列とする
$S_n \equiv \frac{1}{2^n}\sum_{k=0}^{2^n-1} f( \frac{k}{2^n} )$
この数列Snに関して解いていく。方針としては、漸化式に持っていくためにn+1を代入し、Snの式に持ち込む。
$S_{n+1} = \frac{1}{2^{(n+1)}}\sum_{k=0}^{2^{(n+1)}-1} f( \frac{k}{2^{(n+1)}} )$
まずは和分を半分に分ける。
$S_{n+1} = \frac{1}{2^{(n+1)}}\{ \sum_{k=0}^{2^n-1} f( \frac{k}{2^{(n+1)}} ) + \sum_{k=2^n}^{2^{(n+1)}-1} f( \frac{k}{2^{(n+1)}} ) \}$
しばらく右辺第2項だけ議論する。
$\sum_{k=2^n}^{2^{(n+1)}-1} f( \frac{k}{2^{(n+1)}} )$
$=\sum_{k=0}^{2^n-1} f( \frac{k+2^n}{2^{(n+1)}} )$
$=\sum_{k=0}^{2^n-1} f( \frac{k}{2^{(n+1)}} + \frac{1}{2} )$
ここで、k/(2^(n+1)と1/2は、両方とも2進数として表現してもビットが被らないため、関数を分離することができる(厳密な証明は省略・・・ていうか私には無理orz)
$=\sum_{k=0}^{2^n-1}( f( \frac{k}{2^{(n+1)}} ) + f( \frac{1}{2} ) )$
$=\sum_{k=0}^{2^n-1}( f( \frac{k}{2^{(n+1)}} ) + \frac{1}{10} )$
ここで元のSnの式に戻すと
$S_{n+1} = \frac{1}{2^{(n+1)}}\{ \sum_{k=0}^{2^n-1} f( \frac{k}{2^{(n+1)}} ) + \sum_{k=0}^{2^n-1}( f( \frac{k}{2^{(n+1)}} ) + \frac{1}{10} ) \}$
$S_{n+1} = \frac{1}{2^{(n+1)}}\{ 2\sum_{k=0}^{2^n-1} f( \frac{k}{2^{(n+1)}} ) + \sum_{k=0}^{2^n-1}\frac{1}{10} \}$
ここでもう一つ公式を適用。例のごとく証明は省略（ぉ
$f(2^n\cdot x) = 10^n f(x)$
元の値を2倍すれば2進数として一桁上がるので、10進数に戻した場合の10倍になるという意味です（謎）
$S_{n+1} = \frac{1}{2^{(n+1)}}\{ 2\sum_{k=0}^{2^n-1} \frac{1}{10}f( \frac{k}{2^n} ) + \frac{2^n}{10} \}$
$= \frac{1}{10}\{\frac{1}{2^n} \sum_{k=0}^{2^n-1} f( \frac{k}{2^n} )\} + \frac{1}{20}$
$= \frac{1}{10}S_n + \frac{1}{20}$
というわけで見事よくある漸化式の形に表せました。ちなみに初項はS1=1/20なので解いてみると(詳細は略)
$S_n = (-\frac{1}{18})(\frac{1}{10})^n + \frac{1}{18}$
となり、極限を取ると答えは18となりました。

さて、数式を使って解いたのでなんとなく難しそうに見えますが、具体的にばらして書くともっと直感的に出せたりします。
$S_1 = \frac{1}{2}( 0.0 + 0.1 )$
$S_2 = \frac{1}{4}( 0.00 + 0.01 + 0.10 + 0.11 )$
$S_3 = \frac{1}{8}( 0.000 + 0.001 + 0.010 + 0.011 + 0.100 + 0.101 + 0.110 + 0.111 )$
とりあえず、S3について見てみます。足し算部分を縦に並べてみると
0.000
0.001
0.010
0.011
0.100
0.101
0.110
0.111
各桁を見てみると０と１が４回ずつ出てきています。なのでこれは0.111 * 4と出来ます。この４が前の分数とキャンセルされて単純に1/2倍という形になります。同様にすれば他のｎについても簡単にできます。
$S_1 = \frac{1}{2} \cdot 0.1$
$S_2 = \frac{1}{2} \cdot 0.11$
$S_3 = \frac{1}{2} \cdot 0.111$
$S_4 = \frac{1}{2} \cdot 0.1111$
こうすれば極限は目に見えて分かってきます。
$S_{\infty} = \frac{1}{2} \cdot 0.1111111 \dots$
$= \frac{1}{2} \cdot \frac{1}{9}$
$= \frac{1}{18}$
というわけで、直感的ではありますが簡単に出すことが出来ました。

さて、直感的でよければもっと拡張できます。欲張ってｎ進数表現を１０進数表現に読み替える関数の積分をやってみましょう。但し、ｎは10より小さい必要があります。16進数とかabcが出てきても10進数では意味不明です（＾＾；
まずは区分求積の式を立ち上げると
$\lim_{n\to\infty}\frac{1}{d^n}\sum_{k=0}^{d^n-1} f( \frac{k}{d^n} )$
となります。ｄは進数です。さて、具体的に展開すると・・・
$S_1 = \frac{1}{d}( 0.0 + 0.1 + 0.2 + \dots 0.(d-1) )$
$S_2 = \frac{1}{d^2}( 0.00 + 0.01 + \dots 0.(d-1)0 + 0.(d-1)1 + \dots 0.(d-1)(d-1) )$
なんだか汚いのでもっと具体的に３進数でためしに書いてみると
$S_1 = \frac{1}{3}( 0.0 + 0.1 + 0.2 )$
$S_2 = \frac{1}{9}( 0.00 + 0.01 + 0.02 + 0.10 + 0.11 + 0.12 + 0.20 + 0.21 + 0.22 )$
さて同様にして足し算部分を縦に書くと
0.00
0.01
0.02
0.10
0.11
0.12
0.20
0.21
0.22
やはり０と１と２が3回ずつ出てきます。よって
$S_1 = \frac{1}{3}(0.1 + 0.2)$
$S_2 = \frac{1}{3}(0.11 + 0.22)$
$S_3 = \frac{1}{3}(0.111 + 0.222)$
$S_4 = \frac{1}{3}(0.1111 + 0.2222)$
というわけで、3進数の場合は、
$\frac{1}{3}(\frac{1}{9}+\frac{2}{9}) = \frac{1}{9}$
になります。
拡張すると、
$S_1 = \frac{1}{d}(0.1 + 0.2 + \dots + 0.(d-1))$
$S_2 = \frac{1}{d}(0.11 + 0.22 + \dots + 0.(d-1)(d-1))$
$S_3 = \frac{1}{d}(0.111 + 0.222 + \dots + 0.(d-1)(d-1)(d-1))$
よって
$\frac{1}{d}(\frac{1}{9}+\frac{2}{9}+\frac{3}{9}+ \dots +\frac{d-1}{9})$
$=\frac{1}{d}\cdot\frac{1}{9}\frac{d(d-1)}{2}$
$=\frac{d-1}{18}$

さて、理論上はｎ進数表現をｍ進数表現に(ry　も考えられるが疲れたので別の人に譲ります。お疲れ様でしたorz