Thanks, this makes sense and is indeed connected to the digit sum. :)

(And it's not too hard to understand. But I don't wanna bore you with calculations)

What you are doing is called "sieving", because you apply patterns at repeating steps to avoid futile calculations.

But you could create more complicated sieves

Eg if the first digit is i the max k is 9/i (2-> 4, 3->3, 4->2, 5..9 ->1)

So you can skip looping from 5xxx to 9xxx.

This can be even improved, if the biggest digit is m, max k becomes m/i but that's harder to implement.

Or a k=5 is only possible if you have at least one digit 0 or 5.

Combining all these sieves can get quite complicated and the overhead might not justify it.

But you don't need to search sequentially as long as you cover all integers in an interval.

If you really want to break further speed records inform yourself about techniques of (prime) number searches with sieves.