Project Euler Problem 14
正の整数に以下の式で繰り返し生成する数列を定義する。
n → n/2 (n が偶数)
n → 3n + 1 (n が奇数)
13からはじめるとこの数列は以下のようになる。
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
13から1まで10個の項になる。この数列はどのような数字からはじめても最終的には 1 になると考えられているが、まだそのことは証明されていない(コラッツ問題) さて、100万未満の数字の中でどの数字からはじめれば一番長い数列を生成するか。 注意: 数列の途中で100万以上になってもよい
問題文の通りに書いたらやっぱり時間がかかる.調べてみるとメモライズという方法を用いて,これまで出てきた値になったらその後の計算を省略するという方法を用いた方が計算時間が断然上がるみたい.まぁでも,とりあえずは気にしなくていいだろう.
len <- function(x) { if(x==1) return(1) if(x%%2==1 && x!=1) return(len(3*x+1)+1) else return(len(x/2)+1) } max.len <- 0 b <- 0 a <- seq(1,1000000,by=2) for (i in a){ if (len(i) > max.len){ max.len <- len(i) b <- i } } max.len b