Return to Revisions

Alternative Solution

This will be a bit confusing, so my apologies in advance.

Bottom-Up Search

When I did this problem, rather than brute force looping over all the possible permutations, I constructed my pandigital numbers from the bottom up. We can do this because each 3-digit sub group is highly constrained. For example, the last 3 digits have to be a multiple of 17 and be less than 987. There are only 58 different multiples, and any with duplicate digits, like 119, are ineligible. Let's say that about 40 are valid. that means the next 3 digits (d6d7d8) must contain the first 2 digits of one of those 40 AND also not contain any duplicate digits.

The constraints mean that trying to construct the number from the bottom up is a very, very small search space, and thus very quick to search.

Possible Implementation/Algorithm

Here is a high level breakdown of my implementation:

• For each prime, I generated all the multiples from Prime p to 999 (so 2: 2,4,6,8,..,998, 17: 17,34,51,..,986). I'll refer to each of these multiples as a "sub".
• Each list subs was then filtered such that I only kept the values with unique digits (so 2: ...,240,242,244,246,248,... became 2: 240,246,248,...)
• For each sub [d1d2d3] I break it into [d1d2], the head, and [d2d3], the tail.
• Using a tree structure, I match the tails in the tree to my new sub heads
• After looping through all the subs, any branch that is 6 long (one for each prime) is a solution.

I know this is a bit confusing, and I can edit this answer with additional comments or code as requested. When I implemented this in in ruby, this bottom-up approach ran in 6ms.