今日の風景

f:id:nisemono_san:20160913072039j:plain

破壊される予定の壁です。破壊されない壁などなく、皆さんもまた破壊ですか？

はじめにーーPRIMEGAMEとは何か

コンウェイという人は本当に色々な、気の狂ったようなことを考えていて、その中で最も有名なものの一つにライフゲームがある。しかし、ライフゲームだけではなく、計算機で遊ぶということには、彼の右に出るものは殆どいなく、例えば、任意の分数表が素数のリストを作り出すことができるということを発明したのも、彼であり、それはプライムゲーム(PRIMEGAME)と呼ばれている。

PRIMEGAMEの骨格はこうだ。以下の分数表に対して、2を先頭から掛けていく。もし、ある分数の掛けあわせた結果が整数になった場合、その整数を分数表の先頭から掛けていく。これを繰り返していくと、奇妙なことに、2の乗で表すことのできる整数の指数は、全て整数になっているという。

説明が下手なのは、このブログの得意技であるので、実際にコードを見てもらうほうが早いだろう:

PRIMEGAME = [Rational(17, 91),
             Rational(78, 85),
             Rational(19, 51),
             Rational(23, 38),
             Rational(29, 33),
             Rational(77, 29),
             Rational(95, 23),
             Rational(77, 19),
             Rational(1, 17),
             Rational(11, 13),
             Rational(13, 11),
             Rational(15, 2),
             Rational(1, 7),
             Rational(55, 1)]

class Rational
  def int?
    self.to_i == self
  end
end

class PrimeGame
  def initialize n
    @i = n
  end

  def until_integer
    result = @i
    PRIMEGAME.each do |e|
      result = @i
      result *= e
      return result.to_i if result.int?
    end
  end

  def exponent? n
    m = 0
    while n > 1
      return false if n % 2 == 1
      n /= 2
      m += 1
    end
    puts "2 * #{m} = "
    true
  end

  def times n
    n.times do |i|
      @i = until_integer
      puts(@i) if exponent?(@i)
    end
  end
end

prime = PrimeGame.new 2
prime.times 1000000

これを動かしてみると、下のような出力が得られる:

...

2 * 43 = 
8796093022208
2 * 47 = 
140737488355328
2 * 53 = 
9007199254740992
2 * 59 = 
576460752303423488
2 * 61 = 
2305843009213693952
2 * 67 = 
147573952589676412928
2 * 71 = 
2361183241434822606848
2 * 73 = 
9444732965739290427392
2 * 79 = 
604462909807314587353088
2 * 83 = 
9671406556917033397649408
2 * 89 = 
618970019642690137449562112
...

確かに指数によって素数が出てくるのか不思議な結果だと思う。そこで、借りに、この分数表をいわばプログラミング言語であると見なし(実際、本書の中ではFACTRANという呼び名がついている)、分数表を使って足し算と掛け算を実現する方法を解説し、なぜ素数リストを作ることができるのか考察してみるのが、この記事の目的となる。

余談

RubyのRational(つまり分数クラス)から、その分数が整数になるかどうかを取得する方法がわからなかったため、聞いてみたところ、このような解答を頂きました。助言してくださった方々、ありがとうございました。

FACTRANのルール

とりあえず、不正確ではあるものの、ここで利用するFACTRANの定義を行なっておこう。

ルールは以下の通りだ。インプットされる整数に対して、分数表の先頭から、その分数を掛けていく。もし、何らかの分数で掛けたとしても、整数の場合、その整数を採用し、また分数表の最初から掛けていく。もし、最後まで分数表に整数が現われなかった場合、その整数が最終出力として採用される。先のRubyのコードに書いてある分数表は、最後が55/1のため、必ず整数となり、無限ループになる。

単純なカウンターを作る

こういうのを理解するためには、まず単純なループから作ってみるのが一番いいだろう。ということで、本書に習い、一つの分数でできだ分数表、{ 5/6 }を用意し、この最初の数を648とし、このループを廻してみると、375で止まることがわかる。ここで何が起きているかを紙に書きだしてみると:

  645 * 5 / 6 
= 540 * 5 / 6
= 450 * 5 / 6
= 375

となる。なぜこうなるのか、といえば、5/6が5 / (3 * 2)として表記できるわけで、さらに言うと、648は、2^3 * 3^4だからだ。5/6で割ったとき、2と3の指数はそれぞれマイナスされ、そのかわり、5の指数が増える。実際:

  (2 ^ 3) * (3 ^ 4) * 5 / 6
= (2 ^ 2) * (3 ^ 3) * 5 * 5 / 6
= (2 ^ 1) * (3 ^ 2) * (5 ^ 2) / 6

となり、2の指数がなくなってしまった時点で、5/6は分数となってしまって、そこでストップしてしまうことになる。

足し算をする

さて、これらの指数を疑似的にカウンダーだと考えてみよう。今度は(2 ^ 1) * (3 ^ 2) = 2 * 9 = 18に対して、10 / 3を掛け続け、整数でなくなるまでにしてみよう。この場合:

  18 * 10 / 3
= 60 * 10 / 3
= 200

となる。この時、200を因数分解してみれば、(5 * 5) * (2 * 2 * 2)となり、2の指数は、最初の指数を足しあわせたものと一致する。ちなみに、5に関しては、10が2 * 5であるため、5の指数がストックされる形となっている。

これらは分数で行なっているから不思議に思うものの、これを素朴なコードに直してみれば、やっていることは次のコードとたいして変わらなかったりする。

a = 1
b = 2
c = 0
while b > 0
  b -= 1
  a += 1
  c += 1
end

puts a + c

もちろん、先の分数による計算も実装できる。

class Rational
  def integer?
    self.to_i == self
  end
end

a = 3
b = 4

aa = (2 ** a) * (3 ** b)

while (aa * 10/3r).integer?
  aa = aa * 10/3r
end

aa = aa / (5 ** b)
count = 0
until aa == 1
  aa = aa / 2
  count += 1
end

puts count

掛け算の実装(不完全な方法)

同様に分数の掛け算も実装することが可能である。愚直にループだけで掛け算を実装することを考えた場合、次のように実装することが可能である:

r2 = 0
r3 = b = 9
r7 = 6

while r7 > 0
  while r3 > 0
    r2 += 1
    r3 -= 1
  end
  r3 = b
  r7 -= 1
end

puts r2

変数名から推測できるかもしれないが、素朴な方法としては、1/7と10/3と3/5で実装することが可能だ。足し算の実装のさいに、5の指数をスタックしておいたのだけれども、これを3/5でさしもどすための伏線である。

ただし、この方法は不完全である。なぜなら、愚直にループしたい回数ならびに、そのループのさいにカウントしたい回数、例えばこの場合で言うならば、7の指数がループ回数で、3の指数がループ内でカウントされる回数と見なすことができるわけなんだけども、頭から分数を割っていって、整数が出てきたら、最初からやりなおすというルールの場合、考えても見ればわかるように、7の指数は最初に消化されてしまうので、このままだと動かない。

とはいえ、基本的な発想はわかったので、取りあえずこのバージョンのものを書いてみよう。

class Rational
  def integer?
    self.to_i == self
  end
end

r2 = 0
r3 = n = 11
r7 = 23

aa = (3 ** r3) * (7 ** r7)
puts aa
while (aa * 1/7r).integer?
  aa *= 1/7r
  while (aa * 10/3r).integer?
    aa *= 10/3r
  end
  while ( aa * 3/5r ).integer?
    aa *= 3/5r
  end
end

aa = aa / (3 ** n)

count = 0
while aa > 1
  aa = aa / 2
  count += 1
end

puts count

ちなみに、2で割る前に、元の3の乗で割っているのは、ループ抜けるさいの3/5で上がった指数が残っているからである。それはともかくとして、上のコードを見てみればわかるように、問題は「1/7のループに入るまえ」と「入ったあと」を区別するような制御が必要になる。

掛け算を改良する

そこで、何らかの方法で掛け算におけるループをフラグとして持たせ、もしループに入っている状態であるならば、「1/7を採用しない」とする方法を考えるといい。そこで、分数表の「1/7」に、別の素数をフラグとして持たせることによって、その組みあわせでなかったとするならば、既にループの中に入っていると認定し、そのままループするようにすればいいのではないだろうか。

……と書いていても、恐らく理解できない。というより書いている本人がそもそも理解ができないので、具体的にその分数表を出すと次のようになる:

13/77, 170/39, 13/17, 19/13,
69/95, 19/23, 11/19

さて、これらをいきなり見せられても、どまどうと思うので、この分数表を因数分解したものを見せる。

13/(7 * 11)
(2 * 5 * 17) / (3 * 13)
13/17
19/13
(3 * 23) / (5 * 19)
19/23
11/19

ここで重要なのは、先も伸べたように、単純なカウンターを作ったときの例を考えてみればわかるように、5/6というのは、ある数を因数分解した際に、2と3が入っていないといけなかった。それを応用して、11が入っている場合にはループに入っていないと見做し、11と7の指数を下げ、13のフラグを立てる。

そしてその後、3の指数があるならば、それをカウントし続ける。3のカウントが無くなれば、延々とループの回数をカウントしている2と、3の回数を計算している5が出てくる。3のループは脱出したわけだから、一度13のフラグは削除し、今度は3の指数を元に戻し、次のループに供えるためのループが出てくる。最後に、まだループが続く可能性を考慮し、11を掛ける。もし、これでまだ7の指数が残っているならば、最初の分数表に引っかかる筈だ。

概要はわかった。問題は、これがちゃんと動くかだ。コードに書きなおすと、次のようになる。

class Rational
  def integer?
    self.to_i == self
  end
end

RATIONAL_LIST = [
  13/77r,
  170/39r,
  13/17r,
  19/13r,
  69/95r,
  19/23r,
  11/19r
]

r2  = 0
r3  = b = 11
r5  = 0
r7  = 13
n = ((3 ** r3) * (7 ** r7) * 11) * 1/1r

loop_flag = true
while loop_flag
  RATIONAL_LIST.each do |x|
    if (n * x).integer?
      n *= x
      loop_flag = true
      break
    end
    loop_flag = false
  end
end

n = n / 11
n = n / (3 ** b)

count = 0
while n > 1
  n = n / 2
  count += 1
end

puts count

当然、最後にフラグとして利用した11と3は残ってしまうため、あらかじめ割っておく。このようにして、分数表によって、足し算と掛け算が実装できるようになる。

まとめ

ざっくりと、分数表を使った足し算と掛け算の方法について解説をしてみた。今回の元の本になっているものでは、フィボナッチ数を算出するための分数表や、あるいは円周率の桁を出すための分数表が載っている。今回の説明がとてもいいとは、自分でも思っていないので、興味のある人は、下の本を読んで理解を深めるといいと思う。