The number of permutations of a particular row is divided by the number

Question

Suppose I have a multiset of 10 digits, for example S = { 1, 1, 2, 2, 2, 3, 3, 3, 8, 9 } . Is there any method other than brute force to find the number of different permutations of elements from S such that when the permutation is considered as a ten-digit integer, it is divided by a certain number n ? n will range from 1 to 10000 .

For instance:

if S = { 1, 2, 3, 4, 6, 1, 2, 3, 4, 6 } and n = 10 , the result is 0 (since no permutation of these 10 digits will ever give a number divisible by 10)

if S = { 1, 1, 3, 3, 5, 5, 7, 7, 9, 2} and n = 2 , the result is 9! / 2^4 9! / 2^4 (since in the end we must have 2 , there is a 9! Way to rearrange other elements, but there are four pairs of identical elements)

Answer 1

You can crop the search like this: find the first factorization of NUM. Obviously, in order to be divisible by NUM, the permutation must be divisible by all NUM-prime factors. Therefore, you can use simple divisibility rules to avoid generating many invalid candidates.

Answer 2

I have some thoughts, but it is not organized into a real algorithm.

For N = 2, we just see how many even digits we can put at the end of our permutations and calculate their number.

For N = 3, we know that the sum of the digits must be divisible by 3. This means that we can freely introduce any 3s, 6s, 9s and 0s in our permutations, but any other digits that we have to put in pairs that are summed up to 3, 6 or 9 (or triplet 1 s). I do not think it would be too difficult to implement.

With N = 4, we can do something similar to N = 2.

I think we can come up with cases like before N = 10 (N = 7 can be tricky). Then we could make any N> 10 by expanding it. For example, if N = 18, any and all permutations that are divisible by N are also divisible by 2 and 9. Of course, if N is a prime, we may be in trouble.

Answer 3

My idea is to sort the S digits increasing and decreasing. Now you have min and max, which can be generated from S. Now take all the multiples of N in the interval min, max and see which ones are formed by digits in S.