1

以前(2からNまでを、素因数分解したときの素因数の最小値が小さい順に並べるには?
と異なる規則によって、2からNまでを並びかえを行います。

①2〜Nまでを素因数分解を行い次数のみ取り出すものとします。
②次数の小さい順に並べる。

例えば、N = 10 の場合、次のようになります。

2 => 1,
3 => 10,
4 => 2,
5 => 100,
6 => 11,
7 => 1000,
8 => 3,
9 => 20,
10 => 101

1 < 2 < 3 < 10 < 11 < 20 < 100 < 101 < 1000
より、
2, 4, 8, 3, 6, 9, 5, 10, 7
となる。

一般のNに対し、この規則に従い2からNまでを並びかえを行うには
どうすればよろしいでしょうか?

2
  • 各桁で0を最大とみなすのなら、1000が1100より前に来るのはなぜですか?
    – shirok
    Commented 2015年5月21日 17:43
  • 間違いでした。申し訳ございません。 「0が最大」とする条件を外してください。
    – TOM
    Commented 2015年5月21日 21:48

2 件の回答 2

2

「素因数分解してソートする方針」ではなく「次数を順に作ってから対応する合成数を得る方針」で書いてみました。

※3 => 10 と書くと 210 => 10 と紛らわしいので、3 => 1:0 の様な表記にします。

手順の雰囲気(分かりやすさのため厳密ではありません):

  1. 1 (いわば次数0桁に対応) を配列 arr に登録しておく。
  2. 次数1桁 1, 2, 3, …, k, … に対応する合成数 (21, 22, 23, …, 2k, …) を生成し、arr に追加する。
    但し、これだと無限に続くので 2m > N になった所で止める。
  3. 次数2桁 1:?, 2:?, 3:?, …, k:?, … を考える。ただし、? の部分には 1桁以下の次数(=今迄に生成した次数)の列 が入る。つまり 1:? = 1:0, 1:1, 1:2, 1:3, … の略記。この時、対応する合成数は (今迄に arr に登録した数) × 3k で生成できる。合成数(≦N)を生成して arr に登録する。
  4. 次数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) に。

2
  • (log(n) / log(f))はlog(n, f)とすると短くなります。
    – TOM
    Commented 2015年5月22日 3:21
  • ありがとうございます! (実は普段 Ruby は触らないので、検索して module Math の関数一覧を見て書いたのですが 1.8.7 のページを見てました…)
    – akinomyoga
    Commented 2015年5月22日 3:37
1

Gaucheで素直に書いてみました。

(use math.prime)
(use gauche.sequence)

(define (order N)
  ($ map car $ sort
     (map (^i (cons i (reverse (group-sequence (mc-factorize i))))) (iota (- N 1) 2))
     (rec (cmp a b) (cond [(null? a) #t]
                          [(null? b) #f]
                          [(< (caar a) (caar b)) #t]
                          [(> (caar a) (caar b)) #f]
                          [(< (length (car a)) (length (car b))) #t]
                          [(> (length (car a)) (length (car b))) #f]
                          [else (cmp (cdr a) (cdr b))]))
     cdr))

素因数分解して因数のリストを降順に並べた後、条件によってソートしているだけです。

実行例

gosh> (order 10)
(2 4 8 3 6 9 5 10 7)
gosh> (order 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)

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。