﻿ Project Euler Problem 53
You are on the Home/Other Tutorials/Project Euler/Problem 53 page Share Your

# Project Euler - Problem 53

## 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```