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.

Consider all integer combinations of a^{b}for 2 <= a <= 5 and 2 <= b <= 5:

2^{2}=4, 2^{3}=8, 2^{4}=16, 2^{5}=32

3^{2}=9, 3^{3}=27, 3^{4}=81, 3^{5}=243

4^{2}=16, 4^{3}=64, 4^{4}=256, 4^{5}=1024

5^{2}=25, 5^{3}=125, 5^{4}=625, 5^{5}=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 a^{b}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.

## Leave a Reply