Scala で Project Euler Problem 14

まづは、コラッツ数列がどんなものか見てみる

scala> def collatz_list(n: Long): List[Long] = {
     |     if      (n     == 1) List(1L)
     |     else if (n % 2 == 0) n::collatz_list(n / 2)
     |     else                 n::collatz_list(3 * n + 1)
     | }
collatz_list: (n: Long)List[Long]

scala> collatz_list(1)
res0: List[Long] = List(1)

scala> collatz_list(2)
res1: List[Long] = List(2, 1)

scala> collatz_list(3)
res2: List[Long] = List(3, 10, 5, 16, 8, 4, 2, 1)

scala> collatz_list(4)
res3: List[Long] = List(4, 2, 1)

scala> collatz_list(5)
res4: List[Long] = List(5, 16, 8, 4, 2, 1)

scala> collatz_list(6)
res5: List[Long] = List(6, 3, 10, 5, 16, 8, 4, 2, 1)

scala> collatz_list(7)
res6: List[Long] = List(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)

scala> collatz_list(8)
res7: List[Long] = List(8, 4, 2, 1)

scala> collatz_list(9)
res8: List[Long] = List(9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)

scala> collatz_list(10)
res9: List[Long] = List(10, 5, 16, 8, 4, 2, 1)

途中から、同じ数列になるので、毎回作成せずに、辞書に保存しておく

scala> def add_map(lst:List[Long], map:collection.mutable.Map[Long, List[Long]]):Unit = {
     |     if (!lst.isEmpty) {
     |         if (!map.contains(lst.head)) {
     |             map += lst.head -> lst
     |             add_map(lst.tail, map)
     |         }
     |     }
     | }
add_map: (lst: List[Long], map: scala.collection.mutable.Map[Long,List[Long]])Unit

scala> def collatz_list(n:Long, map:collection.mutable.Map[Long, List[Long]]): List[Long] = {
     |     if (n == 1)
     |         List(1L)
     |     else {
     |         if (map.contains(n)) {
     |             map(n)
     |         } else {
     |             if (n % 2 == 0) n::collatz_list(n / 2,     map)
     |             else            n::collatz_list(3 * n + 1, map)
     |         }
     |     }
     | }
collatz_list: (n: Long, map: scala.collection.mutable.Map[Long,List[Long]])List[Long]

scala> val map = collection.mutable.Map[Long, List[Long]] ()
map: scala.collection.mutable.Map[Long,List[Long]] = Map()

scala> var lst = collatz_list(1, map)
lst: List[Long] = List(1)

scala> add_map(lst, map)

scala> map
res11: scala.collection.mutable.Map[Long,List[Long]] = Map(1 -> List(1))

scala> var lst = collatz_list(2, map)
lst: List[Long] = List(2, 1)

scala> add_map(lst, map)

scala> map
res13: scala.collection.mutable.Map[Long,List[Long]] = Map(1 -> List(1), 2 -> List(2, 1))

scala> var lst = collatz_list(3, map)
lst: List[Long] = List(3, 10, 5, 16, 8, 4, 2, 1)

scala> add_map(lst, map)

scala> map
res15: scala.collection.mutable.Map[Long,List[Long]] = Map(16 -> List(16, 8, 4, 2, 1), 5 -> List(5, 16, 8, 4, 2, 1), 10 -> List(10, 5, 16, 8, 4, 2, 1), 8 -> List(8, 4, 2, 1), 3 -> List(3, 10, 5, 16, 8, 4, 2, 1), 4 -> List(4, 2, 1), 1 -> List(1), 2 -> List(2, 1))

まとめ

scala> for (i <- 1 to 9) {
     |     var lst = collatz_list(i, map)
     |     println(lst.length)
     |     add_map(lst, map)
     | }
1
2
8
3
6
9
17
4
20

scala> var max_num = 0
max_num: Int = 0

scala> var max_idx = 0
max_idx: Int = 0

scala> for (i <- 1 to 99) {
     |     var lst = collatz_list(i, map)
     |     if (lst.length > max_num) {
     |         max_num = lst.length
     |         max_idx = i
     |     }
     |     add_map(lst, map)
     | }

scala> println(max_idx + ":" + max_num)
97:119

scala> var max_num = 0
max_num: Int = 0

scala> var max_idx = 0
max_idx: Int = 0

scala> for (i <- 1 to 9999) {
     |     var lst = collatz_list(i, map)
     |     if (lst.length > max_num) {
     |         max_num = lst.length
     |         max_idx = i
     |     }
     |     add_map(lst, map)
     | }

scala> println(max_idx + ":" + max_num)
6171:262

scala> var max_num = 0
max_num: Int = 0

scala> var max_idx = 0
max_idx: Int = 0

scala> for (i <- 1 to 999999) {
     |     var lst = collatz_list(i, map)
     |     if (lst.length > max_num) {
     |         max_num = lst.length
     |         max_idx = i
     |     }
     |     add_map(lst, map)
     | }

scala> println(max_idx + ":" + max_num)
837799:525