I previously blogged about this Project Euler puzzle nearly 6 years ago, using Python. This is my approach using PHP as a simple practical exercise for myself, and I’d appreciate any feedback on my PHP code.

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?

Code:

<?php
$values = 0;
function factorial($x) {
$factorial = 1;
for ($i = $x; $i > 1; $i--) {
$factorial *= $i;
}
return $factorial;
}
function calc($n, $r) {
return factorial($n) / (factorial($r) * factorial($n-$r));
}
foreach (range(1,100) as $i) {
foreach (range(1, $i) as $j) {
if (calc($i, $j) > 1000000) {
$values++;
}
}
}
echo $values;

One key difference here from how I did it in Python is I previously used the range() function in my *factorial* function. Calling that function with* ($n – $r)* means that sometimes we’re calling *factorial(0)*. This means that we then call *range(1,0)*, which in Python returns an empty list. However in PHP this returns an array like this, even if I specify *step=+1* :

array(2) {
[0]=>int(1)
[1]=>int(0)
}

So I would then have had to do an additional check that I’m not trying to calculate *factorial(0)*, which slowed the code right down. However I was able to re-use the factorial function from Problem 34, looping down from $x to 1, instead of doing a foreach loop over the array returned by range(). Doing so kept the code pretty quick.

### Like this:

Like Loading...

*Related*

## Leave a Reply