# Duncan's blog

## October 8, 2014

### Project Euler: problem 29 (PHP) – Distinct powers

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

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

Problem 29:

Consider all integer combinations of ab for 2 <= a <= 5 and 2 <= b <= 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 <= a <= 100 and 2 <= b <= 100?

Here’s my code:

```<?php
ini_set('max_execution_time', 100);

\$limit = 100;
\$numbers = [];

for (\$i = 2; \$i <= \$limit; \$i++) {
for (\$j = 2; \$j <= \$limit; \$j++) {
\$x = bcpow(\$i, \$j);

\$newNumbers = array_flip(\$numbers);

if (!isset(\$newNumbers[\$x])) {
\$numbers[] = \$x;
}
}
}

echo count(\$numbers);
```

Taking a similar approach as with the ColdFusion.  Initially I tried using the in_array() function to check if the current value was already in the \$numbers array. That didn’t seem to work (I can’t remember why not), so instead I went with isset().  Prior to being able to do that I had to use array_flip() to swap the keys and values, i.e. this:

```\$numbers = [
[0] => 4,
[1] => 8,
[2] => 16,
...
];
```

becomes:

```\$numbers = [
[4] => 0,
[8] => 1,
[16] => 2,
...
];
```

So the isset() is just checking if we have a key in the array matching the current value of \$x.  And again I’m having to use bcpow() for dealing with large numbers.

Update: My mate and colleague Adam Cameron suggested a much better way of doing this.

```<?php
\$limit = 100;
\$numbers = [];

for (\$i = 2; \$i <= \$limit; \$i++) {
for (\$j = 2; \$j <= \$limit; \$j++) {
\$x = bcpow(\$i, \$j);

\$numbers[\$x] = true;
}
}

echo count(\$numbers);
```

My problem is I’ve been doing mostly straight conversions of old CFML/Python code into PHP, rather than trying to re-think it properly. So previously with ColdFusion  I had a list which I was examining at every iteration of the inner loop, to see if a value already existed in the list. This isn’t particularly efficient; at the time I couldn’t have used ArrayFind as that was only added in CF 9, which I didn’t have access to at the time. However even then I’d have been better using a ColdFusion struct, which is similar to PHP arrays. And simply by adding the values into the struct, at worse I might overwrite the same value multiple times; this is much more efficient than doing an IF statement on every iteration, thousands of times! This was significantly faster.

PS: Adam also solved it using PHP’s array_reduce, array_merge and array_unique functions with callbacks, which makes logical sense (although I’m still getting my head round these), and was only fractionally slower than the updated version of the code above.