10481


以前（[2からNまでを、素因数分解したときの素因数の最小値が小さい順に並べるには？](https://ja.stackoverflow.com/questions/10436/2%E3%81%8B%E3%82%89n%E3%81%BE%E3%81%A7%E3%82%92-%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E3%81%97%E3%81%9F%E3%81%A8%E3%81%8D%E3%81%AE%E7%B4%A0%E5%9B%A0%E6%95%B0%E3%81%AE%E6%9C%80%E5%B0%8F%E5%80%A4%E3%81%8C%E5%B0%8F%E3%81%95%E3%81%84%E9%A0%86%E3%81%AB%E4%B8%A6%E3%81%B9%E3%82%8B%E3%81%AB%E3%81%AF)）  
と異なる規則によって、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までを並びかえを行うには  
どうすればよろしいでしょうか？


CC BY-SA 3.0
2015-05-21T14:51:07.257
10472
2015-05-22T03:40:38.373
2017-04-13T12:52:39.113
-1
5363
question
アルゴリズム
2からNまでを、素因数分解したときの次数によって並べるには？


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

[code]

    (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))
    
[/code]

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

実行例

[code]

    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)
    
[/code]


CC BY-SA 3.0
2015-05-21T22:42:59.977
10477
2015-05-21T22:42:59.977
5258
10472
answer


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

※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. …
  5. 次数j桁に対応する合成数(≦N)を ( _今迄に`arr` に登録した数_) × (primej)k で生成して `arr` に登録する。
  6. …

[code]

    #!/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)
    
[/code]

出力例:

[code]

    p special_ordering(10)
    
[/code]

[2, 4, 8, 3, 6, 9, 5, 10, 7]

[code]

    p special_ordering(100)
    
[/code]

[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)` に。


CC BY-SA 3.0
2015-05-22T00:32:43.830
10481
2015-05-22T03:40:38.373
2015-05-22T03:40:38.373
5300
5300
10472
answer