# Duncan's blog

## October 18, 2014

### Project Euler: problem 53 (PHP) – Combinatoric selections

Filed under: PHP,Project Euler — duncan @ 8:00 am

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, 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?

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.

Advertisements

## Leave a Comment »

No comments yet.

Create a free website or blog at WordPress.com.