Bash
ProjectEuler
数学

Project Euler Q74 【桁の階乗による連鎖】

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

最初はループに入るとか、循環しない項とかの意味がわからなかったけど、一度出てきた数字までの項の数と解釈すればよいらしい。
なんとか自力で解けたので良かった。

答え合わせ

http://www.geocities.jp/oraclesqlpuzzle/csharp/csharp-euler-answers.html