「問題42. [M21] e1 > ... > er ≥ 0について, n = 2e1 + ... + 2er なら, 和 ∑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 = 23 + 21. そのe1=3, e2=1からnusumを得たいという問題である.
私はこの解答にある J.-P. Allouche, J. Shallitの本 Automatic Sequences (2003)にあるというフラクタルの図が見たかったが, その本が簡単に見られそうもなかったので, PostScriptで描いてみることにした. そこで解答は次のようだ.
「解答. rについての帰納法により,
e12e1-1+ (e2+2)2e2-1 + ... + (er+2r-2)2er-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*23-1 + (1+2)*21-1 = 3*22 + 3*20 = 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 = e12e1-1+ (e2+2)2e2-1 + ... + (er+2r-2)2er-1 +(er+1+2(r+1)-2)2er +1-1 .
er+1=0とすると
nusum n+1 = e12e1-1+ (e2+2)2e2-1 + ... + (er+2r-2)2er-1 +2r.2-1
=nusum n+r = nusum n+νn = nusum n'.
一方n=7から8へのように繰上がりがあるときはどうするか.
31から32の計算をしてみると, eは(4 3 2 1 0) から(5)になる.
このときのnusumは
4.23+5.22+6.21+7.20+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 =75nusum 32は(5)だから, 5.24 = 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ごとである.
0 件のコメント:
コメントを投稿