DouKaku? 1125 yuin: 素因数分解しているので速いです。調子に乗...(ダブル完全数)

Comment detail

素因数分解しているので速いです。調子に乗って1000000まで出してみましたが、わりとすぐでました。

import scala.collection.mutable.HashMap

def searchDoublePerfectNumber(start:int, end:int):List[int] = {
  def factorize(n:int):HashMap[int,int] = {
    var result = new HashMap[int,int]
    def update(i:int) = {result += i -> (1+result.getOrElseUpdate(i, 0));result}
    var x = n
    while(x >= 4 && x%2 ==0){update(2);x = x/2}
    var d = 3
    var q = x/d
    while(q >= d) {
      if(x%d == 0){update(d);x = q}
      else d += 2
      q = x/d
    }
    update(x)
  }

  def divsum(n:int):int = factorize(n).foldLeft(1){(r, p) => 
    r * (0 to p._2).foldLeft(0){(r2,i) => r2 + Math.pow(p._1.toDouble, i.toDouble).toInt}
  } - n

  for(i <- List.range(start, end) if divsum(i) == i*2) yield i
}

println(searchDoublePerfectNumber(0, 1000000))
// => List(120, 672, 523776)

アルゴリズムが面白そうだったのでPythonに逐語訳してみました。
Scalaのコードを読むのは初めてでしたが、
これくらいの規模で内容もわかっていると、
わからない演算子があってもパズルみたいで面白いですね…

「なんでx >= 4なのかな、2の時にどうするのだろう」
と思ったのですが、最後にupdate(x)するのでOKなわけですね。
Doubleに変換しているところで丸め誤差が入らないかがちょっと心配です。

def search_double_perfect_number(start, end):
    def factorize(n):
        result = {}
        def update(i):
            result[i] = 1 + result.get(i, 0)
            return result
        x = n
        while x >= 4 and x % 2 == 0:
            update(2)
            x /= 2
        d = 3
        q = x / d
        while q >= d:
            if x % d == 0:
                update(d)
                x = q
            else:
                d += 2
            q = x / d

        update(x)
        return result

    def divsum(n):
        return reduce(
            lambda r, p: r * reduce(
                (lambda r2, i: r2 + p[0] ** i),
                range(p[1] + 1), 0),
            factorize(n).iteritems(), 1) - n
    
    for i in range(start, end):
        if divsum(i) == i * 2:
            yield i
    
for x in search_double_perfect_number(0, 10000):
    print x

で、このコードの実行速度を#1156と比べてみましたが、
#1156が0.1秒ですむところを0.7秒と7倍もかかりますね…

10万までで求めると
#1156が1.1秒なのに対して、10秒とさらに差が広がってしまいました。
逆転は難しそうです。

アルゴリズム的にはやはり素因数分解の負担が重すぎるようですね…

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq