home
>
Project Euler
>
ForNext
Shut the fuck up and write some code
Problem 12
高度整除三角数
三角数の数列は自然数の和で表わされ, 7番目の三角数は である.
三角数の最初の10項は:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
となる.
最初の7項について, その約数を列挙すると, 以下のとおり.
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
これから, 7番目の三角数である28は, 6個以上の約数をもつ最初の三角数であることが分かる.
では, 500個以上の約数をもつ最初の三角数はいくつか.
Highly divisible triangular number
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be .
The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
考え方
自然数 n が、
( は素数、
は 0 以上の整数)
と素因数分解されるとき、n の約数の個数と 約数の総和は、次の公式で与えられる。
約数の個数：
約数の総和：
たとえば、 は、
と素因数分解され、約数は、
で、約数の個数 は、 個、
約数の総和は
である。
VBScript
JScript
Perl
PHP
Python
Ruby
PowerShell
Scala
更新日 : 2013.01.26
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
F#
更新日 : 2013.01.27
Scala でのロジックをそのまま移植
> let rec get_prime_factor_list(n:int64, factor:int64) = - if n < factor * factor then [n] - elif n % factor = 0L then factor::get_prime_factor_list(n / factor, factor ) - else get_prime_factor_list(n , factor + 1L) - ;; val get_prime_factor_list : int64 * int64 -> int64 list > get_prime_factor_list(73920L, 2L) - ;; val it : int64 list = [2L; 2L; 2L; 2L; 2L; 2L; 3L; 5L; 7L; 11L] > get_prime_factor_list(28L, 2L) - ;; val it : int64 list = [2L; 2L; 7L]
> let mutable exp_list:List<int64> = [] - ;; val mutable exp_list : List<int64> = [] > let mutable exp = 0L - ;; val mutable exp : int64 = 0L > let prime_factor_list = get_prime_factor_list(28L, 2L) - ;; val prime_factor_list : int64 list = [2L; 2L; 7L] > let mutable factor = prime_factor_list.Head - ;; val mutable factor : int64 = 2L > prime_factor_list - |> List.iter(fun n -> - if n = factor then exp <- exp + 1L - else - if exp <> 0L then exp_list <- exp + 1L :: exp_list - factor <- n - exp <- 1L - ) - ;; val it : unit = () > exp_list <- exp + 1L :: exp_list - ;; val it : unit = () > exp_list - ;; val it : List<int64> = [2L; 3L] > exp_list - |> List.reduce(*) - ;; val it : int64 = 6L
> let get_factor_cnt(n:int64) =
- let prime_factor_list = get_prime_factor_list(n, 2L)
- let mutable exp_list:List<int64> = []
- let mutable exp = 0L
- let mutable factor = prime_factor_list.Head
-
- prime_factor_list
- |> List.iter(fun n ->
- if n = factor then exp <- exp + 1L
- else
- if exp <> 0L then exp_list <- exp + 1L :: exp_list
- factor <- n
- exp <- 1L
- )
-
- exp_list <- exp + 1L :: exp_list
- exp_list
- |> List.reduce(*)
- ;;
|> List.iter(fun n ->
-----------------^
stdin(41,18): error FS0407: The mutable variable 'exp_list' is used in an invalid way. Mutable variables cannot be captured by closures. Consider eliminating this use of mutation or using a heap-allocated mutable reference cell via 'ref' and '!'.
> let get_factor_cnt(n:int64) = - let prime_factor_list = get_prime_factor_list(n, 2L) - let exp_list = ref [] - let exp = ref 0L - let factor = ref prime_factor_list.Head - - prime_factor_list - |> List.iter(fun n -> - if n = !factor then exp := !exp + 1L - else - if !exp <> 0L then exp_list := !exp + 1L :: !exp_list - factor := n - exp := 1L - ) - - exp_list := !exp + 1L :: !exp_list - !exp_list - |> List.reduce(*) - ;; val get_factor_cnt : int64 -> int64 > get_factor_cnt 73920L - ;; val it : int64 = 112L
> let mutable n = 1L - ;; val mutable n : int64 = 1L > let m = 500L - ;; val m : int64 = 500L > let mutable fWhile = true - ;; val mutable fWhile : bool = true > while fWhile do - let triangular_num = n * (n + 1L) / 2L - let factor_cnt = get_factor_cnt triangular_num - - if factor_cnt > m then - printf "%d:%d->%d" n triangular_num factor_cnt - fWhile <- false - else - n <- n + 1L - ;; 12375:76576500->576val it : unit = ()