Add-ins:
Excel
PowerPoint

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! = nx(n1)x...x3x2x1,
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?

Knowing a little about combinatorics will help reduce the search
space. For any value n, the larger values for the number of
combinations are for r towards the middle (i.e., closer to n/2) and
the smallest number of combinations are when r is close to 1 or
close to n (the extremes being ^{n}C_{n}=1 and ^{
n}C_{1}=n). Also, the smaller the n the fewer the
possible combinations for any value of r. These suggest two
ways to constrain the search space. First, start with n=100 and search down to n=1.
If any value of n yields no value of r such that the number of combinations
exceeds 1,000,000, the search can stop. This is because no
smaller value of n can possibly yield a number of combinations that exceed 1,000,000. Second, for any n, start
the search with r=n/2 and search both up and down while the number of
combinations exceeds 1,000,000. Again, stop as soon as the
number of combinations for some r is less than a
million.

Sub Euler053() Dim N As Integer, R As Integer, Rslt As Long, I As Integer, _ DoMore As Boolean, NoMore As Boolean, _ StartTime As Single StartTime = Timer N = 100 Do NoMore = True R = N / 2 I = R DoMore = True Do While DoMore If Application.WorksheetFunction.Combin(N, I) > 10 ^ 6 Then NoMore = False: Rslt = Rslt + 1 _ Else DoMore = False I = I - 1 Loop I = R + 1 DoMore = True Do While DoMore If Application.WorksheetFunction.Combin(N, I) > 10 ^ 6 Then NoMore = False: Rslt = Rslt + 1 _ Else DoMore = False I = I + 1 Loop N = N - 1 Loop Until NoMore Debug.Print Rslt, Timer - StartTime End Sub