Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]

# [[Problem 53]]

## Combinatoric Selections

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

<div style="text-align:center">123, 124, 125, 134, 135, 145, 234, 235, 245, and 345</div>

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通りである.

<div style="text-align:center">123, 124, 125, 134, 135, 145, 234, 235, 245, 345.</div>

組み合わせでは, 以下の記法を用いてこのことを表す: $\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$ は何通りあるか?

```scheme

(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)

```