ONLY DO WHAT ONLY YOU CAN DO

こけたら立ちなはれ 立ったら歩きなはれ

Scala で Project Euler Problem 12

28の約数を列挙してみる

scala> var factor_list:List[Int] = List(1, 28)
factor_list: List[Int] = List(1, 28)

scala> for (i <- 2 to 28 / 2) {
     |     if (28 % i == 0) {
     |         factor_list = i::factor_list
     |         println(i)
     |     }
     | }
2
4
7
14

scala> factor_list
res1: List[Int] = List(14, 7, 4, 2, 1, 28)

約数のリストを返す関数

scala> def get_factor_list(n:Int) = {
     |     var factor_list = List(1)
     |     for (i <- 2 to n / 2) {
     |         if (n % i == 0) {
     |             factor_list = i::factor_list
     |         }
     |     }
     |     if (n != 1) n::factor_list else factor_list
     | }
get_factor_list: (n: Int)List[Int]

scala> get_factor_list(1)
res2: List[Int] = List(1)

scala> for (n <- 1 to 10) {
     |     print(n + ":")
     |     get_factor_list(n * (n + 1) / 2).foreach(i => print(i + ","))
     |     println
     | }
1:1,
2:3,1,
3:6,3,2,1,
4:10,5,2,1,
5:15,5,3,1,
6:21,7,3,1,
7:28,14,7,4,2,1,
8:36,18,12,9,6,4,3,2,1,
9:45,15,9,5,3,1,
10:55,11,5,1,

約数の数を返す関数

scala> def get_factor_cnt(n:Int) = {
     |     var factor_cnt = 1
     |     for (i <- 2 to n / 2) {
     |         if (n % i == 0) {
     |             factor_cnt += 1
     |         }
     |     }
     |     if (n != 1) factor_cnt += 1
     |     factor_cnt
     | }
get_factor_cnt: (n: Int)Int

scala> get_factor_cnt(1)
res4: Int = 1

scala> for (n <- 1 to 10) {
     |     val triangular_num = n * (n + 1) / 2
     |     println(n + ":" + triangular_num + "->" + get_factor_cnt(triangular_num))
     | }
1:1->1
2:3->2
3:6->4
4:10->4
5:15->4
6:21->4
7:28->6
8:36->9
9:45->6
10:55->4
scala> var n      = 1
n: Int = 1

scala> var fWhile = true
fWhile: Boolean = true

scala> while (fWhile) {
     |     val triangular_num = n * (n + 1) / 2
     |     println(n + ":" + triangular_num + "->" + get_factor_cnt(triangular_num))
     |     if (n > 10) fWhile = false else n += 1
     | }
1:1->1
2:3->2
3:6->4
4:10->4
5:15->4
6:21->4
7:28->6
8:36->9
9:45->6
10:55->4
11:66->8

約数の数が10を超える最初の三角数

scala> var n      = 1
n: Int = 1

scala> var fWhile = true
fWhile: Boolean = true

scala> while (fWhile) {
     |     val triangular_num = n * (n + 1) / 2
     |     val factor_cnt = get_factor_cnt(triangular_num)
     |     println(n + ":" + triangular_num + "->" + factor_cnt)
     |     if (factor_cnt > 10) fWhile = false else n += 1
     | }
1:1->1
2:3->2
3:6->4
4:10->4
5:15->4
6:21->4
7:28->6
8:36->9
9:45->6
10:55->4
11:66->8
12:78->8
13:91->4
14:105->8
15:120->16

約数の数が100を超える最初の三角数

scala> var n      = 1
n: Int = 1

scala> var fWhile = true
fWhile: Boolean = true

scala> while (fWhile) {
     |     val triangular_num = n * (n + 1) / 2
     |     val factor_cnt = get_factor_cnt(triangular_num)
     |     if (factor_cnt > 100) {
     |         println(n + ":" + triangular_num + "->" + factor_cnt)
     |         fWhile = false
     |     } else n += 1
     | }
384:73920->112

約数の数が200を超える最初の三角数

scala> var n      = 1
n: Int = 1

scala> var fWhile = true
fWhile: Boolean = true

scala> while (fWhile) {
     |     val triangular_num = n * (n + 1) / 2
     |     val factor_cnt = get_factor_cnt(triangular_num)
     |     if (factor_cnt > 200) {
     |         println(n + ":" + triangular_num + "->" + factor_cnt)
     |         fWhile = false
     |     } else n += 1
     | }
2015:2031120->240

約数の数が300を超える最初の三角数

scala> var n      = 1
n: Int = 1

scala> var fWhile = true
fWhile: Boolean = true

scala> while (fWhile) {
     |     val triangular_num = n * (n + 1) / 2
     |     val factor_cnt = get_factor_cnt(triangular_num)
     |     if (factor_cnt > 300) {
     |         println(n + ":" + triangular_num + "->" + factor_cnt)
     |         fWhile = false
     |     } else n += 1
     | }
2079:2162160->320

遅すぎて使い物にならんので、別の手を考える
まず、素因数分解

scala> def get_prime_factor_list(n: Long, factor: Long = 2): List[Long] = {
     |     if      (n          <  factor * factor) List(n)
     |     else if (n % factor != 0              )         get_prime_factor_list(n         , factor + 1)
     |     else                                    factor::get_prime_factor_list(n / factor, factor    )
     | }
get_prime_factor_list: (n: Long,factor: Long)List[Long]

scala> get_prime_factor_list(73920)
res11: List[Long] = List(2, 2, 2, 2, 2, 2, 3, 5, 7, 11)

scala> val prime_factor_list = get_prime_factor_list(73920)
prime_factor_list: List[Long] = List(2, 2, 2, 2, 2, 2, 3, 5, 7, 11)

scala> val prime_factor_list = get_prime_factor_list(28)
prime_factor_list: List[Long] = List(2, 2, 7)

それぞれの素因数の 次数+1 を取得

scala> var exp_list:List[Long] = List()
exp_list: List[Long] = List()

scala> var exp    = 0L
exp: Long = 0

scala> var factor = prime_factor_list(0)
factor: Long = 2

scala> prime_factor_list.foreach { n =>
     |     if (n == factor) exp += 1
     |     else {
     |         if (exp != 0) exp_list = (exp + 1)::exp_list
     |         factor = n
     |         exp    = 1
     |     }
     | }

scala> exp_list = (exp + 1)::exp_list
exp_list: List[Long] = List(2, 3)

scala> exp_list
res13: List[Long] = List(2, 3)

それぞれの素因数の 次数+1 の 総積 が 約数の数

scala> exp_list.reduceLeft(_*_)
res14: Long = 6

約数の数を返す関数を作り直す

scala> def get_factor_cnt2(n:Int) = {
     |     val prime_factor_list = get_prime_factor_list(n)
     |     var exp_list:List[Long] = List()
     |     var exp    = 0L
     |     var factor = prime_factor_list(0)
     |     prime_factor_list.foreach { n =>
     |         if (n == factor) exp += 1
     |         else {
     |             if (exp != 0) exp_list = (exp + 1)::exp_list
     |             factor = n
     |             exp    = 1
     |         }
     |     }
     |     exp_list = (exp + 1)::exp_list
     |     exp_list.reduceLeft(_*_)
     | }
get_factor_cnt2: (n: Int)Long

scala> get_factor_cnt2(73920)
res15: Long = 112

約数の数が500を超える最初の三角数

scala> var n      = 1
n: Int = 1

scala> var m      = 500
m: Int = 500

scala> var fWhile = true
fWhile: Boolean = true

scala> while (fWhile) {
     |     val triangular_num = n * (n + 1) / 2
     |     val factor_cnt = get_factor_cnt2(triangular_num)
     |
     |     if (factor_cnt > m) {
     |         println(n + ":" + triangular_num + "->" + factor_cnt)
     |         fWhile = false
     |     } else n += 1
     | }
12375:76576500->576