Meertens数
Posted feedbacks - Scala
10進数10桁で8秒でした。1桁毎に3倍少しに増える様なので，20桁だと5～10日程度掛かる事になるかと。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | import java.util.Date
import java.text.SimpleDateFormat
object Prime {
private def from(n:Int):Stream[Int] =
Stream.cons(n, from(n + 1))
private def sieve(s:Stream[Int]):Stream[Int] =
Stream.cons(s.head,sieve(s.tail.filter { _ % s.head != 0 }))
def primes = sieve(from(2))
}
class Meertens(max:BigInt) {
val width:Int = max.toString.length
val primes:Stream[Int] = Prime.primes.take(width)
var _meertenses:List[BigInt] = List()
def this() = this(BigInt.apply("9999999999"))
def meertenses_=(meertenses:List[BigInt]) = _meertenses = meertenses
def meertenses = _meertenses
def search:Meertens = {
def _search(depth:Int,number:BigInt,goedel:BigInt):Unit = {
val prime = BigInt.apply(primes.apply(depth))
(new Range(0,9,1)).foreach { d =>
val n = number * 10 + d
val g = goedel * prime.pow(d)
if (n == g) meertenses = n::meertenses
if ((g < max) && (depth < width - 1)) _search(depth + 1,n,g)
}
}
_search(0,0,1)
this
}
}
object Main {
def main(args:Array[String]):Unit = {
var max:String = args.length match { case 0 => "9999999999"; case _ => args(0) }
printf("start:%s\n",new SimpleDateFormat("yyyy/MM/dd HH:mm:ss").format(new Date))
(new Meertens(BigInt.apply(max))).search.meertenses.foreach { m => println(m.toString) }
printf("end:%s\n",new SimpleDateFormat("yyyy/MM/dd HH:mm:ss").format(new Date))
}
}
|
nobsun
#4710()
Rating4/4=1.00
お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．
このような数のことをMeertens数と言うそうです．
32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．
1 reply [ reply ]