Project Euler Problem 53

Problem 53

26 September 2003

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, ⁵C₃ = 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: ²³C₁₀ = 1144066.

How many, not necessarily distinct, values of  ⁿC_r, for 1 n 100, are greater than one-million?

Answer: 4075

Cached factorial

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Euler {
    static class Program {
        static Dictionary<BigInteger, BigInteger> fCache = new Dictionary<BigInteger, BigInteger>();
        static BigInteger factorial(this BigInteger n) {
            if (fCache.ContainsKey(n)) return fCache[n];
            BigInteger f = 1;
            for (BigInteger i = 2; i <= n; i++) {
                f *= i;
                if (!fCache.ContainsKey(i)) {
                    fCache[i] = f;
                }
            }
            return f;
        }

        static BigInteger combination(int n, int r) {
            return (factorial(n) / factorial(r) / factorial(n - r));
        }

        static void Main(string[] args) {
            var count = 0;
            for (var n = 1; n <= 100; n++) {
                for (var r = 0; r <= n; r++) {
                    if (combination(n, r) > 1000000) count++;
                }
            }
            Console.WriteLine(count);
            Console.ReadKey();
        }
    }
}