# Euler Problem 53

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!(nr)! ,where r n, n! = n(n1)…321, 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?

Just do it all with the BigInteger class.

import java.math.*;

public class Euler53
{
public static void main(String[] args)
{
Euler53 e = new Euler53();
System.out.format(“Problem: %s\n”, e.getClass().getName());
}
public String Problem ()
{
int count = 0;
for (int n = 1; n <= 100; n++)
for (int r = 1; r <= n; r++)
{
BigInteger c = C(n,r);
System.out.format(“n:%d r:%d C(n,r):%d\n”, n, r, c);
if (c.compareTo(BigInteger.valueOf(1000000)) == 1)
count++;
}
return String.valueOf(count);
}
public BigInteger C (int n, int r)
{
BigInteger calc = new BigInteger(“1”);
calc = calc.multiply(F(n));
calc = calc.divide(F(r));
calc = calc.divide(F(n-r));
return calc;
}
public BigInteger F (int d)
{
BigInteger sum = new BigInteger(“1”);
if (d > 0)
for (int i = d; i >= 1; i–)
sum = sum.multiply(BigInteger.valueOf(i));
return sum;
}
} ﻿