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, ^(5)C_(3) = 10.

In general,

^(n)C_(r) =
n!
r!(n−r)!
,where r ≤ n, n! = n×(n−1)××3×2×1, 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?

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());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    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;
    }
} 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s