ホーム - Project Euler

Problem 53¶

Combinatoric Selections¶

There are exactly ten ways of selecting three from five, 12345:

In combinatorics, we use the notation, $\displaystyle \binom 5 3 = 10$.

In general, $\displaystyle \binom n r = \dfrac{n!}{r!(n-r)!}$, where $r \le n$, $n! = n \times (n-1) \times ... \times 3 \times 2 \times 1$, and $0! = 1$.

It is not until $n = 23$, that a value exceeds one-million: $\displaystyle \binom {23} {10} = 1144066$.

How many, not necessarily distinct, values of $\displaystyle \binom n r$ for $1 \le n \le 100$, are greater than one-million?

組み合わせ選択¶

12345から3つ選ぶ選び方は10通りである.

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

一般に, $r \le n$ について $\displaystyle \binom n r = \dfrac{n!}{r!(n-r)!}$ である. ここで, $n! = n \times (n-1) \times ... \times 3 \times 2 \times 1$, $0! = 1$ と階乗を定義する.

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

$1 \le n \le 100$ について, 100万を超える $\displaystyle \binom n r$ は何通りあるか?

(import (scheme base)
        (gauche base))

(define (combination-num n r)
  (assume (exact-integer? n))
  (assume (exact-integer? r))
  (assume (<= 1 r n 100))
  (/ (apply * (iota r n -1))
     (apply * (iota r r -1))))

(define combination-list
  (fold-right
    (^[i lis]
      (append
        (map (^j `(,i ,j))
             (iota i 1))
        lis))
    '()
    (iota 100 1)))

(define over100_0000list
  (filter (cut < 100_0000 <>)
          (map (^[lis]
                 (combination-num (car lis)
                                  (cadr lis)))
               combination-list)))

(define answer-53
  (length over100_0000list))

(format #t "53: ~d~%" answer-53)