Scala で Project Euler Problem 23

F# 版 を そのまま移植

与えられた数を素因数分解して、素因数とその指数とを Map にして返す関数

scala> def get_prime_factor(map:collection.mutable.Map[Long, Long], n: Long, factor: Long = 2) {
     |     if  (n  >= factor) {
     |         if (n % factor != 0 )
     |             get_prime_factor(map, n, factor + 1)
     |         else {
     |             if (map.contains(factor))
     |                 map(factor) += 1
     |             else
     |                 map += factor -> 1
     |
     |             get_prime_factor(map, n / factor, factor)
     |         }
     |     }
     | }
get_prime_factor: (map: scala.collection.mutable.Map[Long,Long],n: Long,factor: Long)Unit

真の約数の和を返す関数

scala> def sum_of_proper_divisors(n:Long):Long = {
     |     var map = collection.mutable.Map[Long, Long] ()
     |     get_prime_factor(map, n)
     |     if (map.size == 0) 0
     |     else {
     |         map.transform((k,v) => (math.pow(k, v + 1) - 1).toLong / (k - 1))
     |         map.values.reduceLeft(_*_) - n
     |     }
     | }
sum_of_proper_divisors: (n: Long)Long

過剰数の List を 作成

scala> val abundant_list:List[Long] = (12L to 28123L).toList.filter(n => sum_of_proper_divisors(n) > n)
abundant_list: List[Long] = List(12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 100, 102, 104, 108, 112, 114, 120, 126, 132, 138, 140, 144, 150, 156, 160, 162, 168, 174, 176, 180, 186, 192, 196, 198, 200, 204, 208, 210, 216, 220, 222, 224, 228, 234, 240, 246, 252, 258, 260, 264, 270, 272, 276, 280, 282, 288, 294, 300, 304, 306, 308, 312, 318, 320, 324, 330, 336, 340, 342, 348, 350, 352, 354, 360, 364, 366, 368, 372, 378, 380, 384, 390, 392, 396, 400, 402, 408, 414, 416, 420, 426, 432, 438, 440, 444, 448, 450, 456, 460, 462, 464, 468, 474, 476, 480, 486, 490, 492, 498, 500, 504, 510, 516, 520, 522, 528, 532, 534, 540, 544, 546, 550, 552, 558, 560, 564, 570, 572, 576, 580, 582, 588, 594, 600, 606, 608, 612, 616, 618, 620, 624, 630, 636, 640, 642, 644, ...
scala> abundant_list.length
res0: Int = 6965

2つの過剰数の和で書ける数の Set を 作成

scala> val abundant_set = Set (
     |     for (x <- abundant_list) yield {
     |         for (y <- (abundant_list.filter(n => n >= x))) yield {
     |             val i = x + y
     |             if (i <= 28123L) i else 0
     |         }
     |     }
     | ).flatten
java.lang.OutOfMemoryError: Java heap space
        at scala.collection.mutable.ListBuffer.$plus$eq(ListBuffer.scala:119)
        at scala.collection.mutable.ListBuffer.$plus$eq(ListBuffer.scala:42)
        at scala.collection.TraversableLike$$anonfun$filter$1.apply(TraversableLike.scala:240)
        at scala.collection.LinearSeqOptimized$class.foreach(LinearSeqOptimized.scala:61)
        at scala.collection.immutable.List.foreach(List.scala:45)
        at scala.collection.TraversableLike$class.filter(TraversableLike.scala:239)
        at scala.collection.immutable.List.filter(List.scala:45)
        at $anonfun$1.apply(<console>:10)
        at $anonfun$1.apply(<console>:9)
        at scala.collection.TraversableLike$$anonfun$map$1.apply(TraversableLike.scala:206)
        at scala.collection.TraversableLike$$anonfun$map$1.apply(TraversableLike.scala:206)
        at scal...

こうなると、ちょっと手に負えない...

scala> var abundant_set:Set[Long] = Set ()
abundant_set: Set[Long] = Set()

scala> for (x <- abundant_list) {
     |     for (y <- (abundant_list.filter(n => n >= x))) {
     |         val i = x + y
     |         if (i <= 28123L) abundant_set = abundant_set + i
     |     }
     | }

2つの過剰数の和で書けない数の総和

scala> abundant_set.sum
res3: Long = 391285755

scala> (1L to 28123L).toList.sum - abundant_set.sum
res4: Long = 4179871