Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
$145$は各桁の階乗の和が$145$と自分自身に一致することで有名である.
$1! + 4! + 5! = 1 + 24 + 120 = 145$
$169$の性質はあまり知られていない. これは$169$に戻る数の中で最長の列を成す. このように他の数を経て自分自身に戻るループは$3$つしか存在しない.
$169 → 363601 → 1454 → 169$
$871 → 45361 → 871$
$872 → 45362 → 872$
どのような数からスタートしてもループに入ることが示せる.
例を見てみよう.
$69 → 363600 → 1454 → 169 → 363601 (→ 1454)$
$78 → 45360 → 871 → 45361 (→ 871)$
$540 → 145 (→ 145)$
$69$から始めた場合, 列は$5$つの循環しない項を持つ. また$100$万未満の数から始めた場合最長の循環しない項は$60$個であることが知られている.
$100$万未満の数から開始する列の中で, $60$個の循環しない項を持つものはいくつあるか?
解答
time seq 999999 |
awk -v FS= '{printf $0" ";delete a;for(i=1;i<=NF;i++){a[$i]+=1};for(i=0;i<=9;i++){printf a[i]*1};print ""}' |
sort -k2,2n |
uniq -f1 -c |
awk 'BEGIN{a[0]=1;for(i=1;i<=9;i++){a[i]=a[i-1]*i}} {delete b;b[$2]=1;x=$2;c=1;while(1){s=0;for(i=1;i<=length(x);i++){s+=a[substr(x,i,1)]};if(s in b){break};b[s]=1;x=s;c++};print $1,$2,c}' |
sort -k3,3n |
awk '$3==60{s+=$1} END{print s}'
402
real 0m20.945s
user 0m23.641s
sys 0m0.367s
最初はループに入るとか、循環しない項とかの意味がわからなかったけど、一度出てきた数字までの項の数と解釈すればよいらしい。
なんとか自力で解けたので良かった。