Bash
ProjectEuler
数学

Project Euler Q14 【最長のコラッツ数列】

More than 1 year has passed since last update.

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


参考にさせて頂いたサイト様

next = 次行の処理に移る - AWK - to_dk notebook