## Project Euler 53: Count the values of C(n,r), for 1 ≤ n ≤ 100, that exceed one-million

#### Project Euler 53 Problem Description

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

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, ^{5}C_{3} = 10.

In general, ^{n}C_{r} = *n*! / *r*!(*n−r*)!, where *r* ≤ *n*, *n*! = *n*×(*n*−1)×…×3×2×1, and 0! = 1.

It is not until *n* = 23, that a value exceeds one-million: ^{23}C_{10} = 1144066.

How many, not necessarily distinct, values of ^{n}C_{r}, for 1 ≤ *n* ≤ 100, are greater than one-million?

#### Analysis

There is an efficient way to solve this using Pascal’s triangle.

1 | ||||||||||||||

1 | 1 | |||||||||||||

1 | 2 | 1 | ||||||||||||

1 | 3 | 3 | 1 | |||||||||||

1 | 4 | 6 | 4 | 1 | ||||||||||

1 | 5 | 10 | 10 | 5 | 1 | |||||||||

1 | 6 | 15 | 20 | 15 | 6 | 1 | ||||||||

1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 |

Each row of this triangle is vertically symmetric, so C(n, r) = C(n, n-r) and any C(n, x) for x from r to (n-r) is greater than C(n, r).

If C(n, r) > 10^{6} then C(n, x) for x from r to (n-r) will also > 10^{6}, therefore, the number of C(n, r) > 10^{6}, is simply (n-r)-r+1 for that row *n*.

#### Project Euler 53 Solution

Runs < 0.001 seconds in Python 2.7.Use this link to get the Project Euler 53 Solution Python 2.7 source.

#### Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose*define*to reveal the answer.

#### Afterthoughts

- Function
`binomial`

is listed in Common Functions and Routines for Project Euler - Instead of the binomial function you could calculate them on the fly.
- How many, not necessarily distinct, values of
^{n}C_{r}, for 1 ≤*n*≤ 1000, are greater than ten-billion? 490,806

*Project Euler 53 Solution last updated*

## Discussion

## No comments yet.