Bash
ProjectEuler
数学

Project Euler Q53 【組み合わせ選択】

Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。

問題

$12345$から$3$つ選ぶ選び方は$10$通りである.
$123, 124, 125, 134, 135, 145, 234, 235, 245, 345.$

組み合わせでは, 以下の記法を用いてこのことを表す: $_5C_3 = 10.$

一般に, $r ≤ n$ について $_nC_r = \frac{n!}{r!(n-r)!}$ である. ここで, $n! = n×(n−1)×...×3×2×1,$ $0! = 1$ と階乗を定義する.

$n = 23$ になるまで, これらの値が$100$万を超えることはない: $_{23}C_{10} = 1144066.$

$1 ≤ n ≤ 100$ について, $100$万を超える $_nC_r$ は何通りあるか?

解答

time seq 23 100 |
awk '{for(i=1;i<=$1;i++){print $1,i,$1-i}}' |
awk -M '{s=1;t=1;u=1;for(i=1;i<=$1;i++){s*=i};for(i=1;i<=$2;i++){t*=i};for(i=1;i<=$3;i++){u*=i};print s/t/u}' |
awk '1000000<$1' |
wc -l
4075

real    0m1.310s
user    0m1.277s
sys     0m0.184s

階乗を計算するいい方法ないですかねえ。

答え合わせ

こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/053.html