how many n digit numbers are there with product p

Question

What algorithm should we use to get the count of n digit numbers such that the product of its digits is p; the special condition here is that none of the digits should be 1;

What i have thought so far is to do a prime factorization of p. Say n=3 and p=24.

we first do a prime factorization of 24 to get : 2*2*2*3.

now i have problem in determining the combinations of these which are

4*2*3 , 2*4*3, .... etc Even if can do so... how will I scale for n is way smaller than the count of primes.

I am not too sure if thats the right direction... any inputs are welcome.

Answer 1

First, you don't really need full prime decomposition, only decomposition to primes smaller than your base (I guess you mean 10 here but the problem can be generalized to any base). So we only need factorization into the first 4 primes: 2, 3, 5 and 7. If the rest (prime or not) factor is anything bigger than 1, then the problem has 0 solutions.

Now, lets assume that the number p is factored into:

p = 2^d1 * 3^d2 * 5^d3 * 7^d4

and is also composed from the n digits:

p = d_(n-1)d_(n-2)...d₂d₁d₀

Then, rearranging the digits, is will also be:

p = 2^q2 * 3^q3 * 4^q4 * 5^q3 * ... * 9^q9

where qi >= 0 and q2 + q3 + ... q9 = n

and also (due to the factorization):

for prime=2:  d1 = q2      + 2*q4      + q6      + 3*q8
for prime=3:  d2 =      q3             + q6             + 2*q9
for prime=5:  d3 =                  q5
for prime=7:  d4 =                            q7

So the q5 and q7 are fixed and we have to find all non-negative integer solutions to the equations:
(where the unknowns are the rest qi: q2, q3, q4, q6, q8 and q9)

         d1 = q2      + 2*q4 + q6 + 3*q8
         d2 =      q3        + q6        + 2*q9
n - d3 - d4 = q2 + q3 +   q4 + q6 +   q8 +   q9

For every one of the above solutions, there are several rearrangements of the digits, which can be found by the formula:

X = n! / ( q2! * q3! * ... q9! )

which have to be summed up.

There may be a closed formula for this, using generating functions, you could post it at Math.SE

---

Example for p=24, n=3:

p = 2^3 * 3^1 * 5^0 * 7^0

and we have:

d1=3, d2=1, d3=0, d4=0

The integer solutions to:

3 = q2      + 2*q4 + q6 + 3*q8
1 =      q3        + q6        + 2*q9
3 = q2 + q3 +   q4 + q6 +   q8 +   q9

are (q2, q3, q4, q6, q8, q9) =:

(2, 0, 0, 1, 0, 0) 
(1, 1, 1, 0, 0, 0)

which give:

3! / ( 2! * 1! )      = 3
3! / ( 1! * 1! * 1! ) = 6

and 3+6 = 9 total solutions.

---

Example for p=3628800, n=10:

p = 2^8 * 3^4 * 5^1 * 7^1

and we have:

d1=8, d2=4, d3=1, d4=1

The integer solutions to:

8 = q2      + 2*q4 + q6 + 3*q8
4 =      q3        + q6        + 2*q9
8 = q2 + q3 +   q4 + q6 +   q8 +   q9

are (q2, q3, q4, q6, q8, q9) (along with the corresponding digits and the rearrangements per solution):

(5, 0, 0, 0, 1, 2)    22222899 57    10! / (5! 2!)       =  15120
(4, 0, 2, 0, 0, 2)    22224499 57    10! / (4! 2! 2!)    =  37800
(4, 1, 0, 1, 1, 1)    22223689 57    10! / (4!)          = 151200
(3, 2, 1, 0, 1, 1)    22233489 57    10! / (3! 2!)       = 302400
(4, 0, 1, 2, 0, 1)    22224669 57    10! / (4! 2!)       =  75600
(3, 1, 2, 1, 0, 1)    22234469 57    10! / (3! 2!)       = 302400
(2, 2, 3, 0, 0, 1)    22334449 57    10! / (3! 2! 2!)    = 151200
(2, 4, 0, 0, 2, 0)    22333388 57    10! / (4! 2! 2!)    =  37800
(3, 2, 0, 2, 1, 0)    22233668 57    10! / (3! 2! 2!)    = 151200
(2, 3, 1, 1, 1, 0)    22333468 57    10! / (3! 2!)       = 302400
(1, 4, 2, 0, 1, 0)    23333448 57    10! / (4! 2!)       =  75600
(4, 0, 0, 4, 0, 0)    22226666 57    10! / (4! 4!)       =   6300
(3, 1, 1, 3, 0, 0)    22234666 57    10! / (3! 3!)       = 100800
(2, 2, 2, 2, 0, 0)    22334466 57    10! / (2! 2! 2! 2!) = 226800
(1, 3, 3, 1, 0, 0)    23334446 57    10! / (3! 3!)       = 100800
(0, 4, 4, 0, 0, 0)    33334444 57    10! / (4! 4!)       =   6300

which is 2043720 total solutions, if I haven't done any mistakes..

Answer 2

I don't think I'd start by tackling what is known to be a 'hard' problem, computing the prime decomposition. By I don't think I mean my gut feeling, rather than any rigorous computation of complexity, tells me.

Since you are ultimately only interested in the single-digit divisors of p I'd start by dividing p by 2, then by 3, then 4, all the way up to 9. Of course, some of these divisions won't produce an integer result in which case you can discard that digit from further consideration.

For your example of p = 24 you'll get {{2},12}, {{3},8}, {{4},6}, {{6},4}, {{8},3} (ie tuples of divisor and remainder). Now apply the approach again, though this time you are looking for the 2 digit numbers whose digits multiply to the remainder. That is, for {{2},12} you would get {{2,2},6},{{2,3},4},{{2,4},3},{{2,6},2}. As it happens all of these results deliver 3-digit numbers whose digits multiply to 24, but in general it is possible that some of the remainders will still have 2 or more digits and you'll need to trim the search tree at those points. Now go back to {{3},8} and carry on.

Note that this approach avoids having to separately calculate how many permutations of a set of digits you need to consider because it enumerates them all. It also avoids having to consider 2*2 and 4 as separate candidates for inclusion.

I expect you could speed this up with a little memoisation too.

Now I look forward to someone more knowledgeable in combinatorics telling us the closed-form solution to this problem.