Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
正の整数に以下の式で繰り返し生成する数列を定義する.
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万以上になってもよい
解答
time seq 999999 |
awk '{v=$1;for(i=1;i<=999;i++){print $1,v,c[v];if(c[v]!=""){c[NR]+=c[v];next};if(v==1){next};if(v%2==0){v=v/2}else{v=3*v+1};c[NR]+=1}}' |]
awk '$3==""{s[$1]+=1} $3!=""{s[$1]+=$3+1} END{for(i=1;i<=$1;i++){print i,s[i]}}' |
sort -k2,2n |
tail -1 |
awk '$0=$1'
837799
real 0m20.440s
user 0m25.205s
sys 0m0.451s
awkで次の行に行く為のコマンドnextを知らなかった為、勉強になった。
※2018/01/22修正
実行時間が$70$秒ほどだったのを$20$秒ほどに改善。
答え合わせ
こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/014.html