Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
三角数の数列は自然数の和で表わされ, 7番目の三角数は $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$ である. 三角数の最初の10項は:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
となる.
最初の7項について, その約数を列挙すると, 以下のとおり.
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
これから, 7番目の三角数である28は, 5個より多く約数をもつ最初の三角数であることが分かる.
では, 500個より多く約数をもつ最初の三角数はいくつか.
解答
time seq 20000 |
awk '{print $1*($1+1)/2}' |
factor |
awk '{for(i=2;i<=NF;i++){print $1,$i}}' |
uniq -c |
awk '{if(b!=$2){s[$2]=1};s[$2]*=($1+1);print $2,s[$2];b=$2}' |
awk '500<$2{print $1*1}' |
sort -n |
head -1
76576500
real 0m0.234s
user 0m0.611s
sys 0m0.046s
ポイント
- 三角数の第n項$a_n$は$a_n=\frac{1}{2}n(n+1)$と書けること。
- 約数の個数は素因数分解したときの各素数の指数+1の積で表せること。
※2018/01/22修正
最後の出力から約数の個数を除外
答え合わせ
こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/012.html