You are on the Home/Other Tutorials/Project Euler/Problem 53 page
Google
Web This Site

Project Euler - Problem 53

More about Project Euler.

Problem description

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(n−1)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?

Solution

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