「素因数分解してソートする方針」ではなく「次数を順に作ってから対応する合成数を得る方針」で書いてみました。
※3 => 10 と書くと 210 => 10 と紛らわしいので、3 => 1:0 の様な表記にします。
手順の雰囲気(分かりやすさのため厳密ではありません):
- 1 (いわば次数0桁に対応) を配列
arr
に登録しておく。
- 次数1桁 1, 2, 3, …, k, … に対応する合成数 (21, 22, 23, …, 2k, …) を生成し、
arr
に追加する。
但し、これだと無限に続くので 2m > N になった所で止める。
- 次数2桁 1:?, 2:?, 3:?, …, k:?, … を考える。ただし、? の部分には 1桁以下の次数(=今迄に生成した次数)の列 が入る。つまり 1:? = 1:0, 1:1, 1:2, 1:3, … の略記。この時、対応する合成数は (今迄に
arr
に登録した数) × 3k で生成できる。合成数(≦N)を生成して arr
に登録する。
- …
- 次数j桁に対応する合成数(≦N)を (今迄に
arr
に登録した数) × (primej)k で生成して arr
に登録する。
- …
#!/usr/bin/env ruby
include Math
require 'prime'
def special_ordering(n)
arr = [1]
Prime.each(n){|f|
arr.concat(
(1 .. log(n, f).round).map{|k|
ff = f ** k
arr.map{|m| ff * m}.select{|i| i <= n}
}.flatten
)
}
arr[1 .. -1]
end
p special_ordering(10)
出力例:
p special_ordering(10)
[2, 4, 8, 3, 6, 9, 5, 10, 7]
p special_ordering(100)
[2, 4, 8, 16, 32, 64, 3, 6, 12, 24, 48, 96, 9, 18, 36, 72, 27, 54, 81, 5, 10, 20, 40, 80, 15, 30, 60, 45, 90, 25, 50, 100, 75, 7, 14, 28, 56, 21, 42, 84, 63, 35, 70, 49, 98, 11, 22, 44, 88, 33, 66, 99, 55, 77,
13, 26, 52, 39, 78, 65, 91, 17, 34, 68, 51, 85, 19, 38, 76, 57, 95, 23, 46, 92, 69, 29, 58, 87, 31, 62, 93, 37, 74, 41, 82, 43, 86, 47, 94, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
編集: @Manyama さんの指摘で log(n) / log(f)
を log(n, f)
に。