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, 5C3 = 10.
In general,
| nCr = |
n!
----------- r!(n-r)! |
,where r
≤
n, n! = nx(n 1)x...x3x2x1,
and 0! = 1. |
It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.
How many, not necessarily distinct, values of nCr, 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 nCn=1 and nC1=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