53.php

<!-- 
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!(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: 23C10 = 1144066.
How many, not necessarily distinct, values of  nCr, for 1 ≤ n ≤ 100, are greater than one-million?
-->
<?php $startTime = microtime(true);

function nCr($n,$r)
{
	global $factorials;
	$top = $factorials[$n];
	$bottom1 = $factorials[$r];
	$bottom2 = $factorials[($n-$r)];
	return bcdiv($top,bcmul($bottom1,$bottom2));
}
//put all factorials 0-100 into an array
$factorials[0] = 1;
$total = "1";
for ($n=1; $n <= 100; $n++) { 
	$total = bcmul($total,("".$n));
	$factorials[$n] = $total;
}
$greaterCount = 0;
for ($n=1; $n <= 100; $n++) { 
	for ($r=1; $r <= $n; $r++) { 
		if (intval(nCr($n,$r))>1000000) {
			$greaterCount++;
		}
	}
}

$answer = $greaterCount;
$endTime = microtime(true);
echo "Answer: ",$answer,"\nTime: ",($endTime - $startTime),"\n";
// Answer: 4075
// Time: 0.19s