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.
|,where r ≤ n, n! = nx(n1)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