読者です 読者をやめる 読者になる 読者になる

猫尾製作所

あまりアテにしないでね

階乗進法

数学 代数学 プログラミング Ruby

0 以上 N! 未満の自然数 n (つまり 0 <= n < N!) に対して階乗進法というものを定めます。これは 1!, 2!, 3!, …, (N-1)! のそれぞれの定数倍の和で自然数 n を表現するというアイディアです。

式で書くと次のようになります。

(☆)
 n = \sum_{k=1}^{N-1} a_k \cdot k!
 (0 \leq a_k \leq k)

2行目の制限も含めて具体的に解説いたします。

例えば、85 を 階乗進法で表すとしましょう。

4! = 24, 5! = 120 なので、4! < 85 < 5! となるのですが、85 を 1!, 2!, 3!, 4! のそれぞれ定数倍の和で表現してみましょう。

 85 = 3 * 4! + 13
 13 = 2 * 3! +  1
  1 = 0 * 2! +  1
  1 = 1 * 1!

よって 85 = 3 * 4! + 2 * 3! + 0 * 2! + 1 * 1! という『階乗進法』での表現ができます。

そして、☆式の2行目の制限によって表現の一意性を保証しています。この制限によって 1!, 2!, 3!, …, (N-1)! を用いて表せる表現を N! 通りに制限しているからです。しかし、一意性を証明するためには一対一対応も示さなければなりません。

しかし、 a_k \cdot k! (k+1)! を超えることがないので、上位の桁  a_{k+1} \cdot (k+1)! に影響を与えることはありません。また、下位の桁からも影響は受けません。これは全ての桁にいえるのですから、このことより一意性は示されます。

もう少し具体例を。

256 = 2 * 5! + 16
 16 = 0 * 4! + 16
 16 = 2 * 3! +  4
  4 = 2 * 2! +  0
  0 = 0 * 1!

よって 256 = 2 * 5! + 0 * 4! + 2 * 3! + 2 * 2! + 0 * 1! となります。

例によって、アルゴリズムを記述するのはプログラミングコードを以ってというのがいちばんという自説から、自然数から階乗進法への変換を Ruby を用いて書きますと次のようになります。

Ruby によるコード

# 階乗の定義
def fact(n)
	if n > 0 then
		return (n * fact(n-1))
	elsif n == 0 then
		return 1
	else
		retrun nil
	end
end

# 整数を入力
# hoge.to_i で 文字列 hoge を整数に変換
if ARGV.length == 1 then
	n = ARGV[0].to_i
else
	puts "Please give a positive integer."
	exit 1  # 異常終了
end

# 0 未満の整数が入力された場合
if n < 0 then
	puts "Please give a non-negative integer."
	exit 1  # 異常終了
end

# n を超えない最小の d! を決定
# (大文字を使えないので、記事中で N と表現した変数を d としている)
d = 1
while fact(d+1) <= n do
	d += 1
end

# 結果を計算しながら出力
flg = 0  # 出力を見やすくするためのフラグ変数
puts "#{n}"
while d > 0 do
	fd = fact(d) # d の階乗
	a = n / fd   # 商
	n = n % fd   # 余り
	print (flg == 0 ? " = " : " + ") # 行頭に = か + を出力する
	flg = 1
	print "%2d * %2d!\n" % [a, d]
	d -= 1
end

# 終了
exit 0

実行例

% ruby factshin.rb 85
85
 =  3 *  4!
 +  2 *  3!
 +  0 *  2!
 +  1 *  1!

% ruby factshin.rb 119
119
 =  4 *  4!
 +  3 *  3!
 +  2 *  2!
 +  1 *  1!

% ruby factshin.rb 120
120
 =  1 *  5!
 +  0 *  4!
 +  0 *  3!
 +  0 *  2!
 +  0 *  1!

% ruby factshin.rb 256
256
 =  2 *  5!
 +  0 *  4!
 +  2 *  3!
 +  2 *  2!
 +  0 *  1!

% ruby factshin.rb 1234
1234
 =  1 *  6!
 +  4 *  5!
 +  1 *  4!
 +  1 *  3!
 +  2 *  2!
 +  0 *  1!

% ruby factshin.rb 1232453124245
1232453124245
 = 14 * 14!
 +  1 * 13!
 + 11 * 12!
 + 11 * 11!
 +  6 * 10!
 +  0 *  9!
 +  3 *  8!
 +  6 *  7!
 +  0 *  6!
 +  2 *  5!
 +  0 *  4!
 +  0 *  3!
 +  2 *  2!
 +  1 *  1!

% ruby factshin.rb 9876543210123456789
9876543210123456789
 =  4 * 20!
 +  1 * 19!
 +  3 * 18!
 + 11 * 17!
 +  8 * 16!
 +  2 * 15!
 +  4 * 14!
 +  7 * 13!
 +  8 * 12!
 +  9 * 11!
 +  5 * 10!
 +  6 *  9!
 +  2 *  8!
 +  1 *  7!
 +  4 *  6!
 +  4 *  5!
 +  2 *  4!
 +  3 *  3!
 +  1 *  2!
 +  1 *  1!