150405(2)

Ruby


Zeckendorf number representation

12までの整数Nの二進表記は以下のとおりである。
0

1

10

11

100

101

110

111

1000

1001

1010

1011

1100

12までの整数Nのゼッケンドルフの表現は

 0 = 0

 1 = 1

 2 = 2

 3 = 3

 4 = 3 + 1

 5 = 5

 6 = 5 + 1

 7 = 5 + 2 

 8 = 8

 9 = 8 + 1

10 = 8 + 2

11 = 8 + 3

12 = 8 + 3 + 1

であるが、これを二進表記のように書くと以下のとおりになる。

0

1

10

100

101

1000

1001

1010

10000

10001

10010

10100

10101

このような表現を出力するコードを書いてみた。
オンライン整数列大辞典の
A014417（http://oeis.org/A014417/list）
と比較し、答え合わせしてみる。

def representation(n)

  f_ary = []

  a, b = 1, 2

  while a <= n

    f_ary << a

    a, b = b, a + b

  end

  s = f_ary.size

  r_ary = Array.new(s, 0)

  m = n

  i = s - 1

  while m > 0

    while f_ary[i] > m

      i -= 1

    end

    r_ary[i] = 1

    m -= f_ary[i]

    # 連続してはいけない

    i -= 2

  end

  r_ary.join.reverse.to_i

end

ary = []

for n in (0..33)

  ary << representation(n)

end

# OEIS A014417のデータ

ary0 =

[0,1,10,100,101,1000,1001,1010,10000,10001,10010,

 10100,10101,100000,100001,100010,100100,100101,

 101000,101001,101010,1000000,1000001,1000010,

 1000100,1000101,1001000,1001001,1001010,1010000,

 1010001,1010010,1010100,1010101]

# 一致の確認

p ary == ary0

このコードを書いた後、以下のコードをネットで見つけた。
（http://rosettacode.org/wiki/Zeckendorf_number_representation#Ruby）

def zeckendorf
  return to_enum(__method__) unless block_given?
  x = 0
  loop do
    bin = x.to_s(2)
    yield bin unless bin.include?("11")
    x += 1
  end
end

zeckendorf.take(21).each_with_index{|x,i| puts "%3d: %8s"% [i, x]}