2015年4月5日日曜日

150405(3)

Ruby


Generalization of the Zeckendorf representation

a.b>0とし､数列{Xn}を次の線形漸化式で定義する｡
Xn+1 = a Xn + b Xn-1, X0 = 0, X1 = 1
このとき、次の定理が成り立つ。
（定理）
任意の正の整数は次のように唯一通りに表される。
N = ∑αiXi
但し､各αは整数で､0≦α1≦a-1, 0≦αi≦a (i≠1) αn≠0 
αi = aのとき､0≦αi-1≦b-1 
さらに､この表現は最小表現である｡
（http://oacis.lib.kaiyodai.ac.jp/dspace/bitstream/123456789/335/1/AN00161244-51-1.pdf）

この表現を二進表記のように出力するコードを書いてみた。
言うまでもなく、150405(2)分の一般化である。

def representation(n, a, b)
  f_ary = []
  c, d = 1, a
  while c <= n
    f_ary << c
    c, d = d, b * c + a * d
  end
  s = f_ary.size
  r_ary = Array.new(s, 0)
  k = a + 1
  m = n
  i = s - 1
  while m > 0
    if m == a * f_ary[i]
      r_ary[i] = a
      m = 0
    else
      j = m / f_ary[i]
      k = (k == a)? [b - 1, j].min : [a, j].min
      r_ary[i] = k
      m -= k * f_ary[i]
      i -= 1
    end
  end
  r_ary.join.reverse.to_i
end

A0, B0 = 1, 1
ary0 = []
for n in (0..33)
  ary0 << representation(n, A0, B0)
end
p ary0

A1, B1 = 2, 1
ary1 = []
for n in (0..33)
  ary1 << representation(n, A1, B1)
end
p ary1

A2, B2 = 1, 2
ary2 = []
for n in (0..33)
  ary2 << representation(n, A2, B2)
end
p ary2

A3, B3 = 2, 2
ary3 = []
for n in (0..33)
  ary3 << representation(n, A3, B3)
end
p ary3

A4, B4 = 2, 3
ary4 = []
for n in (0..33)
  ary4 << representation(n, A4, B4)
end
p ary4

出力結果
[0, 10, 100, 1000, 1010, 10000, 10010, 10100, 100000, 100010, 100100, 101000, 10
1010, 1000000, 1000010, 1000100, 1001000, 1001010, 1010000, 1010010, 1010100, 10
000000, 10000010, 10000100, 10001000, 10001010, 10010000, 10010010, 10010100, 10
100000, 10100010, 10100100, 10101000, 10101010]
[0, 1, 10, 11, 20, 100, 101, 110, 111, 120, 200, 201, 1000, 1001, 1010, 1011, 10
20, 1100, 1101, 1110, 1111, 1120, 1200, 1201, 2000, 2001, 2010, 2011, 2020, 1000
0, 10001, 10010, 10011, 10020]
[0, 10, 11, 100, 110, 1000, 1010, 1011, 1100, 1110, 1111, 10000, 10010, 10011, 1
0100, 10110, 11000, 11010, 11011, 11100, 11110, 100000, 100010, 100011, 100100,
100110, 101000, 101010, 101011, 101100, 101110, 101111, 110000, 110010]
[0, 1, 10, 11, 20, 21, 100, 101, 110, 111, 120, 121, 200, 201, 210, 211, 1000, 1
001, 1010, 1011, 1020, 1021, 1100, 1101, 1110, 1111, 1120, 1121, 1200, 1201, 121
0, 1211, 2000, 2001]
[0, 1, 10, 11, 20, 21, 22, 100, 101, 110, 111, 120, 121, 122, 200, 201, 210, 211
, 220, 221, 1000, 1001, 1010, 1011, 1020, 1021, 1022, 1100, 1101, 1110, 1111, 11
20, 1121, 1122]

これらはそれぞれ次のことを表している。
(f_ary = [1, 1, 2, 3, 5, …]となることに注意)
 0 = 0
 1 = 1*1
 2 = 1*2
 3 = 1*3
 4 = 1*3 + 1*1
 5 = 1*5
 6 = 1*5 + 1*1
 7 = 1*5 + 1*2
 8 = 1*8
 9 = 1*8 + 1*1
10 = 1*8 + 1*2
11 = 1*8 + 1*3
12 = 1*8 + 1*3 + 1*1 
…
33 = 1*21 + 1*8 + 1*3 + 1*1

 0 = 0                  　　 ← ペル数(Pell number)による表現
 1 = 1*1
 2 = 1*2
 3 = 1*2 + 1*1
 4 = 2*2
 5 = 1*5
 6 = 1*5 + 1*1
 7 = 1*5 + 1*2
 8 = 1*5 + 1*2 + 1*1
 9 = 1*5 + 2*2
10 = 2*5
11 = 2*5 + 1*1
12 = 1*12
…
33 = 1*29 + 2*2

 0 = 0
 1 = 1*1
 2 = 1*
 3 = 1*3
 4 = 1*3 + 1*1
 5 = 1*5
 6 = 1*5 + 1*1
 7 = 1*5 +
 8 = 1*5 + 1*3
 9 = 1*5 + 1*3 + 1*1
10 = 1*5 +
11 = 1*11
12 = 1*11 + 1*1
…
33 = 1*21 + 1*11 + 1*1

(f_ary = [1, 1, 3, 5, …]となることに注意)
 0 = 0
 1 = 1*1
 2 = 1*1 + 1*1
 3 = 1*3
 4 = 1*3 + 1*1
 5 = 1*5
 6 = 1*5 + 1*1
 7 = 1*5 + 1*1 + 1*1
 8 = 1*5 + 1*3
 9 = 1*5 + 1*3 + 1*1
10 = 1*5 + 1*3 + 1*1 + 1*1
11 = 1*11
12 = 1*11 + 1*1 
…
33 = 1*21 + 1*11 + 1*1

 0 = 0
 1 = 1*1
 2 = 1*2
 3 = 1*2 + 1*1
 4 = 2*2
 5 = 2*2 + 1*1
 6 = 2*2 + 2*1
 7 = 1*7
 8 = 1*7 + 1*1
 9 = 1*7 + 1*2
10 = 1*7 + 1*2+ 1*1
11 = 1*7 + 2*2
12 =  1*7 + 2*2 +2*1
…
33 = 1*20 + 1*7 + 2*2 + 2*1
投稿者 時刻:

0 件のコメント:

コメントを投稿

注: コメントを投稿できるのは、このブログのメンバーだけです。

登録: コメントの投稿 (Atom)