2014年5月31日土曜日

横方向の和の和

昨日のブログではさぼったnusum (2r-1) から nusum 2rを計算してみた.

前回のような表を書くと

nnusumνnes
2r-1nusum 2r-1r(r-1 r-2 r-3 ... 0)
2rnusum 2r1(r)


羃の列が(r-1 r-2 r-3 ... 0)のnusum (2r-1) の式は

nusum (2r-1) = (r-1)2r-2 + (r-2+2)2r-3 + (r-3+4)2r-4 + ... + (0+2r-2)2-1

で, これにrを足したものが

nusum 2r = r.2r-1

になればよい.

nusum (2r-1)
={各項の係数の中を計算する}
(r-1)2r-2+r2r-3+(r+1)2r-4+...+(r+(r-2))2-1
={降順の羃の列で同じ係数を持つものをならべる}
(r-1)2r-2+(r-1)2r-3+(r-1)2r-4+...+(r-1)2-1  {1行目}
             +2r-3+2r-4+...+2-1                    {2行目}
                    +2r-4+...+2-1                    {3行目}
                          +2r-5+...+2-1              {4行目}
                          +...
                          +2-1                          {r行目}
={各行を2p+2p-1+... +2q=2p+1-2q で置き換える}
(r-1)(2r-1-2-1)
+2r-2-2-1
+2r-3-2-1
+...
+20-2-1
={1行目を展開し2行目以下の第1項を足し合せる 2行目以下のr-1個の2-1を足す}
(r-1)2r-1-(r-1)2-1+(2r-1-20) -(r-1)2-1
={いろいろ消えて}
r2r-1-2r-1-(r-1)+2r-1-1
=r2r-1-r.

rを足せばnusum 2rになる.

存外簡単であった.

2014年5月30日金曜日

横方向の和の和

TAOCPの演習問題713-42にこういうのがある.

「問題42. [M21] e1 > ... > er ≥ 0について, n = 2e1 + ... + 2er なら, 和 ∑k=0n-1νkを, 冪e1, ..., erを使って表せ.」

ここでνkkを二進法で表わした時の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. さらにその右は上の 式による計算とその和を示す.

nnusumνnes
101(0)0.2-10
211(1)1.201
322(1 0)1.20 + 2.2-12
441(2)2.214
552(2 0)2.21 + 2.2-15
672(2 1)2.21 + 3.207
793(2 1 0)2.21 + 3.20 + 4.2-19
8121(3)3.2212
9132(3 0)3.22 + 2.2-113
1015(3 1)3.22 + 3.2015

さてこれで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 nn = 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
=75
nusum 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ごとである.