Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

3の累乗の差と和であらゆる自然数を表現してみる(ついでに、その測り方を考える)

今日の風景

f:id:nisemono_san:20161001204529j:plain

すたみな太郎にて誕生日会でした

はじめに

『算数の文化史』を読んでいたら、「あらゆる自然数は2の累乗の和としてあらわすことができる」ということが紹介されていた。証明はともかくとして、これは直感的にわかるものだ。だが、もう一つ「あらゆる自然数は3の累乗の和と差であらわすことができる」というのがある。これは直感的にはちょっとよくわからない。

例えば、5であるならば、3の累乗のリストは「9、3、1」となる。この場合、「9」から「3」と「1」を引くことで、5の数を表現できる。このように、全ての自然数は3の累乗の和と差で表現できるという。当然、このことは数学的帰納法かなにかで証明するのが正しいのかもしれないけれど、その証明はとりあえず追いておくとして、そのような3の累乗の和と差で、あらゆる自然数を表現するようなプログラムを書いてみるのが、今回の記事の目的となる。

仕様決め

まず、仕様を決めることにする。まず、基本的に3進法の考えかたを持ちいる。要するにどういうことかというと、例えば「12」を現わすときには、3進法では「110」と表現できる。しかし、3進法の場合、「13」の場合、「120」というように表現できる。

そこで、今回は「2」の使用を禁止し、差を表現できるようにする。そのような表現は、寡聞にして見たことがないので、暫定的に、ある位の差を~というように表現しよう。例えば、「11」の場合、「11~1」という表現をするようにする。例えば、10進法の場合、95を表現するなら「10~5」と書けるようにしよう、という表記である。

このような表記をどうして導入するのか、というと、元の問題が文銅を使って重さを測る問題であることと関係している。どういうことかというと、例えば2gの塩か何かを測りたい場合、手元には3gと1gの分銅しかない。その場合、天秤であるならば、2gの塩のほうに、1gの分銅をおいてあげて、もう片方のほうに、3gの分銅をおけば、無事つりあうというわけだ。

さて、このような表記を導入したのちに、位には二つの方式が出てくることになる。つまり、位と位との足し算、位と位との引き算である。通常、位というのは次のような式で表すことができる

{m = 1000n_4 + 100n_3 + 10n_2 + n_1}

{  = 10^{3}n_4 + 10^{2}n_3 + 10^{1}n_2 + 10^{0}n_1}

この式を見ればわかるように、足し算しか出てこないわけなのだが、これに引き算を付加するという記法が先ほどの記法になるわけだ。

というわけで、式を生成する

基本的には、ツリー形式で総当たりにしてある。もちろん、本来なら、自然数という定義に拘るならば、途中で数がマイナスになるならば、それ以降はプラスにならないと考えてそれ以上探索しないとか、あるいは途中のノートで似たようなノードが出る可能性を考えて、テーブルにキャッシュをしこむなどの方法があるのだけれども、そのあたりの面倒なところを考えるとロジックの部分が追いかけにくい部分が出てくると思うので、単純な総当たりにしてある:

class Scale < Struct.new(:even, :weight)
end

class Op < Struct.new(:n, :type)
end

class Spindle
  def initialize g
    @g = g
  end

  def three_table
    result = [1]
    point = 3
    while @g * 3 > point
      result.push(point)
      point = point * 3
    end
    result.reverse
  end

  def calc
    calcp(@g, 0, three_table, [])
  end

  def calcp(origin, prev_g, table, types)
    if table.empty?
      Scale.new(prev_g == origin, types)
    else
      next_table = table.clone
      next_g = next_table.shift
      return [calcp(origin, prev_g, next_table, types.clone.push(Op.new(next_g, 0))),
       calcp(origin, prev_g + next_g, next_table, types.clone.push(Op.new(next_g, 1))),
       calcp(origin, prev_g - next_g, next_table, types.clone.push(Op.new(next_g, 2)))]
              .flatten
              .select { |s| s.even }
    end
  end

  def to_s
    s = calc[0].weight.map do |s|
      if s.type == 0
        "0"
      elsif s.type == 1
        "1"
      elsif s.type == 2
        '~1'
      end
    end
    s.shift if s[0] == "0"
    s.join('')
  end

  def self.decode(s)
    result = 0
    a = s.split('').select{ |x| x != "~" }
    table = [*1..a.size].map { |x| x == 1 ? 1 : 3 ** (x - 1) }
    a = s.split('')

    until a.empty?
      check_minus = a[0..1]
      if check_minus[0] == "~"
        result -= table.pop
        a.shift(2)
      else
        next_num = table.pop
        result += next_num if check_minus[0] == "1"
        a.shift
      end
    end
    result
  end
end

2.upto(20) do |i|
  puts "#{i} => #{Spindle.new(i).to_s}"
end

calcpの再帰部分が正直綺麗ではないことをのぞけば、これで動く筈だ。ちなみにログは次のようになる:

2 => 1~1
3 => 10
4 => 11
5 => 1~1~1
6 => 1~10
7 => 1~11
8 => 10~1
9 => 100
10 => 101
11 => 11~1
12 => 110
13 => 111
14 => 1~1~1~1
15 => 1~1~10
16 => 1~1~11
17 => 1~10~1
18 => 1~100
19 => 1~101
20 => 1~11~1

ちなみに、最後の部分を:

2.upto(100) do |i|
  puts Spindle.decode(Spindle.new(i).to_s)
end

とすれば、元の数に戻せるはずである。これによって、コンピューターによって、3の累乗の和と差によって、あらゆる自然数が表現できることが確かめられたと思う。

この再帰部分てやっていることと言うのは、つまり:

  • 9
    • 0
      • 1
      • -1
      • 0
    • -3
      • 1
      • -1
      • 0
    • 3
      • 1
      • -1
      • 0

といったような、木構造を作り、手当たり次第に検索している。これが、元の数と一緒の計算になるならば、それを残し、結果を出力する。結果のタイプは、「使わない、足す、引く」の三種類となる。今回の仕様の場合、「0, 1, ~1」となるわけだから、Opというオブジェクトのタイプを見ながら、文字列を組みたてる、というのがプログラムの概要となる。当然、手当たり次第なので、数が大きければ大きいほど、計算量が大きくなっていく。6の場合であるならば、3の3乗、つまり27通りで済むが、それ以上になると、3乗ずつ増えていくので、正直非効率である。

さいごに

とはいえ、証明が無いので、例えば101のときに、3の乗数で組み立てられない可能性があることも間違いない。本来ならば証明でやる必要であるけれども、証明については、詳しい人にまかせようと思う。

算数の文化史

算数の文化史

今気がついたけど、もう売ってないのか……