an interesting problem

[Don Shepherd]

Thanks to all who participated.

I should have stated the restriction regarding duplicate digits in my original post. Gerson, however, read my mind. I couldn't fall asleep last night (tonight!) thinking that I had omitted something, then I realized it was no duplicate digits allowed.

The maximum number of checks depends entirely on the order of the 6 entries in each of 4 lists: the 137 list, 139 list, the 379 list, and the 971 list. The best case is 4, as Pauli said, assuming you choose a composite number as the first member of each list. The worst case, it seems to me, would be 17, assuming you find all of the primes first in each list [3 primes in the 137 list, 2 primes in the 139 list, 4 primes in the 379 list, and 4 primes in the 971 list means tries = (3+1) + (2+1) + (4+1) + (4+1) = 17]. In my actual case, it was 12, but I went on and checked the remaining 12 numbers for primality too.

Interestingly (to me at least, but then I'm weird), if we evaluate this for a 4-digit number instead of a 3-digit number, the number of permutations is the same [P(4,4)=24] and there is no solution as well.