Hatena::ブログ(Diary)

あどけない話

2009-04-08

チョウゲンボウとホシムクドリから賢人鳥を導出する

すべての鳥は、チョウゲンボウ(K)とホシムクドリ(S)から導き出される。そこで、賢人鳥(Y)を K と S から導出してみる。

チョウゲンボウ(K)

K の定義は以下の通り。

Kxy = x

ホシムクドリ(S)

S の定義は以下の通り。

Sxyz = xz(yz)

自己鳥(I)

I の定義は以下の通り。

Ix = x

I は SKK と表現できる。

SKKx = Kx(Kx) = x

ルリツグミ(B)

B の定義は以下の通り。

Bxyz = x(yz)

B は S(KS)K と表現できる。

S(KS)Kxyz = KSx(Kx)yz = S(Kx)yz = Kxz(yz) = x(yz)

ウグイス(W)

W の定義は以下の通り。

Wxy = xyy

W は SS(KI) と表現できる。

SS(KI)xy = Sx(KIx)y = xy(KIxy) = xy(Iy) = xyy

ヒバリ(L)

L の定義は以下の通り。

Lxy = x(yy)

L は BWB と表現できる。

BWBxy = W(Bx)y = Bxyy = x(yy)

賢人鳥(Y)

Y の定義は以下の通り。

Yx = x(Yx)

Y は SLL と表現できる。

SLLx = Lx(Lx) = x(Lx(Lx)) = x(SLLx)

2008-11-28

7の倍数

先日、7の倍数の見分け方を習ったので、忘れないように書いておきます。

  • 任意の数字が、10a + b と表現できるとき、a - 2b が 0 (mod 7) となる場合に限り、その数は7の倍数である。

いくつか、例を示します。

21 → 2 - 2 × 1 = 0
35 → 3 - 2 × 5 = -7 → 0
133 → 13 - 2 * 3 = 7 → 0 
182 → 18 - 2 * 2 = 14 → 1 - 2 × 4 = -7 → 0

和田先生の解析

10a + b = 0 (mod 7)

が成り立つとする。

まず両辺を 5 倍する。(右辺は0のままであることに注意)

50a + 5b = 0 (mod 7)

変形して、

a + 49a + 7b - 2b = 0 (mod 7)

mod 7 の世界だから

a - 2b = 0 (mod 7)

なお、7 の倍数以外の数字が、0 (mod 7) とならないのは自明です。

2008-07-16

3 NOT problem

和田先生が紹介されていた3 NOT problemを解こうといろいろ考えましたが、結局できませんでした。orz

答えが分らないと、気になって次の仕事に進めないので、検索して答えを見つけました。

Haskell でアルゴリズムを書いておきます。

import Data.Bits

input = map triple [0..7]
    where
      triple :: Int -> (Bool,Bool,Bool)
      triple n = (testBit n 2,testBit n 1,testBit n 0)

output = map (\(x,y,z) -> (not x, not y, not z)) input

threeNot (x,y,z) = let aa =  y && z
                       ab =  x && z
                       ac =  x && y
                       ad =  y || z
                       ba =  x && aa
                       bc =  x || aa
                       ca = bc && ad
                       da = not ca
                       ea =  z && da
                       eb =  y && da
                       ec = ba || da
                       fa =  y || ea
                       fb =  x || ea
                       fc =  x || eb
                       ga = fa && da
                       fd =  x || ga
                       gb = fb && da
                       gc = fc && da
                       gd = fd && ec
                       ha = not gd
                       ia = ha || ga
                       ib = ha || gb
                       ic = ha || gc
                       ja = ia && da
                       jb = ib && da
                       jc = ic && da
                       ka = aa || ja
                       kb = ab || jb
                       kc = ac || jc
                       x' = ka && ia
                       y' = kb && ib
                       z' = kc && ic
                   in (x',y',z')

実行するとこんな感じ。

> input
[(False,False,False),(False,False,True),(False,True,False),(False,True,True),(True,False,False),(True,False,True),(True,True,False),(True,True,True)]
> map threeNot input
[(True,True,True),(True,True,False),(True,False,True),(True,False,False),(False,True,True),(False,True,False),(False,False,True),(False,False,False)]
> (map threeNot input) == output
True

2008-01-21

余り

昔、あるプログラムのソースを読んでいて、ハッシュの大きさとして 128 が使われていました。「2 の累乗を使うとは何事か!」と思い、二度とその人の書いたコードは読まなくなりました。

2 の累乗で割って余りを取ると、ほとんど計算しないことは明らかですね。上のビットをマスクして、全部 0 にしているだけですから。たとえば、0x01020304 を 256 で割った余りは 0x04 です。

一方、「2 の累乗 - 1」で割って余りを取る計算も、実はほとんど計算になってないのを知っている人は、あまりいないでしょう。たとえば、0x01020304 を 255 で割った余りは、0x0a とすぐ計算できない人がほとんどでしょうね。

この問題は、実は「3で割り切れるか」という日常的によく使う計算と本質的には同じことです。

3で割り切れるか

以下、10進数の話です。

2 で割り切れるか判断するときは、下一桁が偶数か奇数かで判断します。当たり前ですね。

5 で割り切れるか判断するときも、下一桁が 0 あるいは 5 か、それ以外かで判断します。ええ、当たり前です。

3 で割り切れるか判断するときは、どうしますか? 最近の若い人は、数学が苦手らしいので、知らない人もいるかもしれませんが、次のようにやります。それぞれの桁を足した数が、3 で割り切れるか確かめるのです。

たとえば 123 だと、1 + 2 + 3 = 6 ですから、3 で割り切れます。256 は 2 + 5 + 6 = 13 ですから、割り切れません。13 が 3 で割り切れるか分らなければ、さらに 1 + 3 = 4 を計算し、割り切れないことを確かめましょう。

実は、これは 9 で割り切れるかという問題のサブセットになっています。各桁を足すと、9で割った余りになるのです。余りが 9 であれば、9 で割り切れ、それ以外では割り切れないと分ります。

たとえば、234 は、2 + 3 + 4 = 9 なので、9 で割り切れます。456 は、4 + 5 + 6 = 15 で、さらに 1 + 5 = 6 なので、9 では割り切れません。

9 で割り切れる部分は、3 でも割り切れるはずです。ですから、9 で割った余りの部分だけを見れば、3 で割り切れるか分る訳です。

9 で割ることが特殊であるのは、9 が進数である 10 から 1 を引いた数だからです。

2^n - 1 で割った余り

2^n - 1 で割った余りを計算する方法を考えましょう。分りやすくするために、n = 8 とし、2^n - 1 = 255 で話を進めていきます。

256 を x と置くと、任意のバイト列は、以下のように表現できます。

F(x) = c0 × x^0 + c1 × x^1 + c2 × x^2 + c3 × x^3 ....

F は適当に付けた名前なので、気にしないで下さい。

抽象化されるとよく分らない人のために、例として 0x01020304 を挙げておきます。

0x01020304 = 0x01 × 256^3 + 0x02 × 256^2 + 0x03 × 256^1 + 0x04 × 256^0
           = 0x01 × x^3 + 0x02 × x^2 + 0x04 × x + 0x04

さて、「剰余の定理」を覚えていますか?

P(x) を (x - a) で割ったときの商が Q(x)、余りが R だっとしましょう。つまりこうです。

P(x) = (x - a) × Q(x) + R

R を簡単に計算するには、x に a を代入すればよいことは明らかです。

P(a) = (a - a) × Q(x) + R = R

F(x) を x - 1 で割った余りを取るにはどうしますか? そう、x = 1 を代入すればいいですね。

F(x) = c0 × x^0 + c1 × x^1 + c2 × x^2 + c3 × x^3 ....
F(1) = c0 × 1^0 + c1 × 1^1 + c2 × 1^2 + c3 × 1^3 ....
     = c0 + c1 + c2 + c3 ....

我々が考えている例では、x は256 でした。(x - 1) は、255 です。つまり、ある数値を 255 で割って余りを取るには、それぞれのバイトを足すだけです。

だから、0x01020304 を 255 で割った余りは、0x01 + 0x02 + 0x03 + 0x04 = 0x0a のように、簡単に計算できる訳です。

一般解

進数の数や桁数は任意ですよ!

2007-12-18

博士の愛した数式

博士の愛した数式は、この世で最も美しいオイラーの公式でした。

e^{i¥pi} + 1 = 0

小川洋子さんは、この式を情緒的に表現しています。

果ての果てまで循環する数と、決して正体を見せない虚ろな数が、簡潔な軌道を描き、一点に着地する。どこにも円は登場しないのに、予期せぬ宇宙からπが e の元に舞い下り、恥ずかしがり屋の i と握手をする。彼らは身を寄せ合い、じっと息をひそめているのだが 一人の人間が1つだけ足し算をした途端、何の前触れもなく世界が転換する。すべてが0に抱き留められる。

博士の愛した数式 (新潮文庫)

博士の愛した数式 (新潮文庫)

この公式は、三角関数を使えば自明です。しかし、虚数平面で直感的に理解する方が、より豊かになれるでしょう。オイラーも「優れた数学者とは、この公式の意味が分かるもののことだ」という感じの言葉を残しているようです。

"e" を π 乗することは理解できても、i 乗することは理解できない人がほどんどでしょう。

残念ながら、"i" は虚数という訳語が与えられ、実際には存在しない数字のような先入観を多くの人は与えられています。

でも、考えてみて下さい。"0" は存在する数字でしょうか? マイナスは存在する数字でしょうか?

"0" やマイナスが、x軸という線分を左方向に広げてくれるように、"i" は世界を二次元(y軸方向)に広げてくれるのです。

もし、博士のようにオイラーの公式を愛したいなら、ぜひ「物理数学の直観的方法」という本を読みましょう。(学生のころ読んでいれば、テストでもっとよい点がとれたこと間違いなし。)

物理数学の直観的方法

物理数学の直観的方法