## Project Euler Problem #38

### May 3, 2010

Read the details of the problem here

Summary

What is the largest 1 to 9 pandigital that can be formed by multiplying a fixed number by 1, 2, 3, … ?

Solution

As with a lot of Project Euler problems it’s worth having a bit of a think about the problem before jumping into coding a solution in order to understand the potential search space.

In the second part of the question it states that (9*1)…(9*5) is going to give 918273645 so, as that’s most probably not the actual answer, any solution has to exceed that value. This means that the seed number must begin with a “9”.

This therefore forces additional constraints on the range. A two-digit seed number (90-98) won’t work as, the concatenated sequence would either be 8 digits long (for 3 multipliers) or 11 digits long (for 4 multipliers) and so could not be pandigital. Also, it can’t be a three-digit seed number (901-987) as the length would be either 7 or 11 digits for multipliers of 2 and 3 respectively. As at least two numbers have to be concatenated, this means that it has to be a four-digit seed number, using only multipliers of 1 & 2, between the range of 9182 and 9876. As we’re looking for the highest number, it would probably make sense to code a descending search so the first item satisfying criteria will be the solution, but I’ll use Groovy listops unless performance is horrible.

The code itself is then very straightforward to write and declarative of the problem.

```def answer =
(9876..9182).collect { it.toString() + (it*2).toString() }
.findAll { it.toList().sort().join() == "123456789" }
.max()
```

This runs in 16 ms. So quite quick even with Groovy listops! A non-listop approach using a descending search, as mentioned above and coded as below, runs in 6 ms.

```def answer = 0

for (i in 9876..9182) {
def s = i.toString() + (i*2).toString()
if (s.toList().sort().join() == "123456789") {