TAOCPの演習問題713-42にこういうのがある.
「問題42. [M21]
e1 > ... >
er ≥ 0について,
n = 2
e1 + ... + 2
er
なら, 和 ∑
k=0n-1ν
kを,
冪
e1, ...,
erを使って表せ.」
ここでν
kは
kを二進法で表わした時の1の数であり, 横方向の和といったりする.
ν0=0; ν1=1; ν2=1; ν3=2; ν4=1; ν5=2; ν6=2; ν7=3; ν8=1; ν9=2; ...
従って問題は
nが与えれた時,
n-1までの各整数にあった1の総和
nusumを計算するものである.
n=10とすれば, 上のνの値を使い
nusum 10 = 0+1+1+2+1+2+2+3+1+2=15
しかし途中のνを全部計算して求めるのはしんどいから, 10を二進法で1010と表わし, 10 = 8 + 2 = 2
3 + 2
1. その
e1=3,
e2=1から
nusumを得たいという問題である.
私はこの解答にある
J.-P. Allouche, J. Shallitの本
Automatic Sequences (2003)にあるというフラクタルの図が見たかったが, その本が簡単に見られそうもなかったので, PostScriptで描いてみることにした. そこで解答は次のようだ.
「解答.
rについての帰納法により,
e12
e1-1+
(
e2+2)2
e2-1 + ... +
(
er+2
r-2)2
er-1.
D. E. Knuth,
Proc. IFIP Congress (1971),
1, 19--27. この和のフラクタル模様はAlloucheとShallitの本の図3.1と3.2に示してある.]
また
Sn'(1)も考察せよ. ただし
Sn(
z) = ∑
k=0n-1zνk = (1+
z)
e1+
z(1+
z)
e2+...
+
zr-1(1+
z)
er.」
つまり
e1=3,
e2=1だったから
3*2
3-1 + (1+2)*2
1-1 = 3*2
2 + 3*2
0
= 12 + 3 = 15なわけだ.
もう少し計算してみる. 下の表は左端が
n. 次がnusum. 各行のnusumは
1行上のnusumに1行上のν
nを足したものになっている. その次のかっこ
内は
e1...
er. さらにその右は上の
式による計算とその和を示す.
n | nusum | νn | es |
1 | 0 | 1 | (0) | 0.2-1 | 0 |
2 | 1 | 1 | (1) | 1.20 | 1 |
3 | 2 | 2 | (1 0) | 1.20 + 2.2-1 | 2 |
4 | 4 | 1 | (2) | 2.21 | 4 |
5 | 5 | 2 | (2 0) | 2.21 + 2.2-1 | 5 |
6 | 7 | 2 | (2 1) | 2.21 + 3.20 | 7 |
7 | 9 | 3 | (2 1 0) | 2.21 + 3.20 + 4.2-1 | 9 |
8 | 12 | 1 | (3) | 3.22 | 12 |
9 | 13 | 2 | (3 0) | 3.22 + 2.2-1 | 13 |
10 | 15 | | (3 1) | 3.22 + 3.20 | 15 |
さてこれで
rによる帰納法が出来るであろうか.
偶数の
nからそれより1大きい
n'に進むとき,
eの列は
最後に
r+1項目として0が追加される. だから
nusum
n+1 =
e12
e1-1+
(
e2+2)2
e2-1 + ... +
(
er+2
r-2)2
er-1
+(
er+1+2(
r+1)-2)2
er
+1-1
.
er+1=0とすると
nusum
n+1 =
e12
e1-1+
(
e2+2)2
e2-1 + ... +
(
er+2
r-2)2
er-1
+2
r.2
-1
=nusum
n+
r = nusum
n+ν
n = nusum
n'.
一方
n=7から8へのように繰上がりがあるときはどうするか.
31から32の計算をしてみると,
eは(4 3 2 1 0) から(5)になる.
このときのnusumは
4.2
3+5.2
2+6.2
1+7.2
0+8.2
-1
これを次のように計算してみる.
3(23+22+21+20+2-1)
+(23+22+21+20+2-1)
+(22+21+20+2-1)
+(21+20+2-1)
+(20+2-1)
+(2-1)
=
3(24-2-1)
+(24-2-1)
+(23-2-1)
+(22-2-1)
+(21-2-1)
+(20-2-1)
=
3(24-2-1)
+(25-20)
-5(2-1)
=
3*15.5+31-2.5
=75
nusum 32は(5)だから, 5.2
4 = 80. さっきの75にν31=5を足して
80になる.
一般的には上の(4 3 2 1 0)が(
r-1
r-2 ... 0)なので
r
について同様の計算をしなければならない. しかしもう出来そうになったから
フラクタル図の方へ急ごう.
nusumの式をPostScriptで書くことになる.
/es {4 dict begin /s exch def /m exch def /n exch def
/l s length def
n 0 eq{s}{n 2 mod 0 eq{n 2 idiv m 1 add s es}
{n 2 idiv m 1 add m s aload pop l 1 add array astore es}
ifelse}ifelse end} def
/nusum {4 dict begin /n exch def
/ee n 0 [] es def /sum 0 def
0 1 ee length 1 sub{/i exch def /e ee i get def
/sum e i 2 mul add 2 e 1 sub exp mul sum add def} for
sum end} def
0.33 setlinewidth
0 1 560{/x exch def
x 0 moveto 0 x nusum 4 div rlineto stroke} for
最初の手続きesは
nの冪の列を返す. n 0 [] esのように呼ぶ.
10 0 [] es => [3 1]
手続きnusumが総和の計算である. 32 nusum => 80.0, 560 nusum => 2480.0
n=0から560までを描いたのが下の図だ. フラクタルと言われればそう見えなくもないが.
横軸の目盛は100ごと, 縦軸の目盛は500ごとである.