Comment by zahlman

> Test if the number is < min or > max _before_ doing the digit sum. It's a free 5.5x speedup that renders some of the other optimizations, like trying to memoize digit sums, unnecessary.

How exactly did you arrive at this conclusion? The input is a million numbers in the range from 1 to 100000, chosen with a uniform random distribution; the minimum and maximum values are therefore very likely to be close to 1 and 100000 respectively - on average there won't be that much range to include. (There should only be something like a 1 in 11000 chance of excluding any numbers!)

On the other hand, we only need to consider numbers congruent to 3 modulo 9.

And memoizing digit sums is going to be helpful regardless because on average each value in the input appears 10 times.

And as others point out, by the same reasoning, the minimum and maximum values with the required digit sum are overwhelmingly likely to be present.

And if they aren't, we could just step through 9 at a time until we find the values that are in the input (and have the required digit sum; since it could differ from 30 by a multiple of 9) - building a `set` from the input values.