How many n numbers of digits are there with product p

Question

Which algorithm should we use to count the number n of digits, so the product of its digits is p; a special condition here is that none of the numbers should be 1;

What I have been thinking so far is to do a basic factorization of p. Say n = 3 and p = 24.

first we make a simple factorization of 24 to obtain: 2 * 2 * 2 * 3.

Now I have a problem in determining combinations of them which

4 * 2 * 3, 2 * 4 * 3, .... etc. Even if it can be done ... as I scale for n, it is less than the number of primes.

I'm not too sure this is the right direction ... any inputs are welcome.

Answer 1

Firstly, you really do not need a complete simple decomposition, but only decomposition into primes smaller than your base (I think you have 10 in mind here, but the problem can be generalized to any base). Thus, we only need to factorize into the first 4 primes: 2, 3, 5 and 7. If the stop coefficient (simple or not) is greater than 1, then the problem has 0 solutions.

Now let's assume that the number p taken into account in:

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

and also consists of digits n :

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

Then, reordering the numbers will also be:

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

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

as well (due to 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, q7 and q7 fixed, and we need to find all non-negative integer solutions of the equations: (where unknowns are the remaining 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 each of the above solutions, there are several permutations of numbers that can be found by the formula:

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

to be summarized.

There can be a closed formula for this, using the generation functions, you can publish it on 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 

Entire solutions for:

 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 complete 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 

Entire solutions for:

 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) (together with the corresponding digits and permutations of the 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 a 2043720 complete solution if I have not made any mistakes.

Answer 2

I don’t think I’ll start by solving what is known to be a “difficult” problem by calculating a simple decomposition. I do not think that I mean my gut feeling, and not any rigorous calculations of complexity, tells me.

Since you are ultimately only interested in single-digit divisors p , I would start by dividing p by 2 , then by 3 , then 4 , up to 9 . Of course, some of these divisions will not lead to an integer result, in which case you can discard this figure from further consideration.

In your p = 24 example, you get {{2},12}, {{3},8}, {{4},6}, {{6},4}, {{8},3} (i.e. e. tuples of divider and remainder). Now take the approach again, although this time you are looking for double-digit numbers whose digits are multiplied by the remainder. That is, for {{2},12} you get {{2,2},6},{{2,3},4},{{2,4},3},{{2,6},2} . Since all these results lead to 3-digit numbers, the numbers of which are multiplied by 24 , but in general it is possible that some of the residuals will still have 2 or more digits, and you need to trim the search tree at these points. Now return to {{3},8} and continue.

Please note that this approach avoids the need to separately calculate how many permutations of the set of digits you need to consider, since it lists them all. This also avoids considering 2*2 and 4 as separate candidates for inclusion.

I expect you to speed this up with a little memory too.

Now I look forward to the one who knows more about combinatorics, telling us about the closed form of solving this problem.

Answer 3

You can use the dynamic programming approach based on the following formula:

 f[ n ][ p ] = 9 * ( 10^(n-1) - 9^(n-1) ), if p = 0 0, if n = 1 and p >= 10 1, if n = 1 and p < 10 sum{ f[ n - 1 ][ p / k ] for 0 < k < 10, p mod k = 0 }, if n > 1 

The first case is a separate case for p = 0. This case calculates in O (1), in addition, it helps to exclude k = 0 values ​​from the 4th case.
2 and 3 - dynamic base.
Case 4 k consecutively takes all possible values ​​of the last digit and sums the number of numbers with the product p with the last digit k , reducing to the same smaller problem.

You will have O (n * p) runtime if you implement dp with remembering.

PS: My answer is for a more general problem than the OP described. If the condition that no digit should be equal to 1 must be satisfied, the formulas can be adjusted as follows:

 f[ n ][ p ] = 8 * ( 9^(n-1) - 8^(n-1) ), if p = 0 0, if n = 1 and p >= 10 or p = 1 1, if n = 1 and 1 < p < 10 sum{ f[ n - 1 ][ p / k ] for 1 < k < 10, p mod k = 0 }, if n > 1 

Answer 4

For N numbers of digits and the product of its digits - p;

For example, if n = 3 and p = 24

The agreement will be as follows: (Permutation)

 = (p!)/(pn)! = (24!) /(24 -3)! = (24 * 23 * 22 * 21 )! / 21 ! = (24 * 23 * 22 ) = 12144 

Thus, one could create circuit 12144

And for the combination you should follow

 = (p!)/(n!) * (pn)! = (24!) /(3!) * (24 -3)! = (24 * 23 * 22 * 21 )! / (3!) * 21 ! = (24 * 23 * 22 ) / 6 = 2024 

May it help you

Answer 5

The problems seem far-fetched, but in any case there are upper limits to what you saw. For example, p cannot have a prime divisor> 7, since it must be a single digit ("such that the product of its digits").

It follows that p = 1 * 2 ^ a * 3 ^ b * 5 ^ c * 7 ^ d.

2 ^ a can come from ceil (a / 3) to 'a' digits. 3 ^ b can come from ceil (b / 2) to the digits 'b'. 5 ^ c and 7 ^ d can come from the numbers "c" and "d", respectively. The remaining digits can be filled in 1 s.

Therefore, n can vary from ceil (a / 3) + ceil (b / 2) + c + d to infinity, and p has a set of fixed values.

Answer 6

Primary factorization is like the right direction, although you don't need more than 7, so you can simply divide by 2,3,5,7 times. (There is no solution unless we get the prime or get one> 7).

Once we have the main factors, p % x and p / x can be implemented as constant-time operations (you really don't need p , you can just keep simple coefficients).

My idea is to compute combinations with the algorithm below, and permutations from there are easy.

 getCombinations(map<int, int> primeCounts, int numSoFar, string str) if (numSoFar == n) if (primeCounts == allZeroes) addCombination(str); else ;// do nothing, too many digits else if (primeCounts[7] >= 1) // p % 7 getCombinations(primeCounts - [7]->1, numSoFar-1, str + "7") else if (primeCounts[5] >= 1) // p % 5 getCombinations(primeCounts - [5]->1, numSoFar-1, str + "5") else if (primeCounts[3] >= 2) // p % 9 getCombinations(primeCounts - [3]->2, numSoFar-1, str + "9") getCombinations(primeCounts - [3]->2, numSoFar-2, str + "33") else if (primeCounts[2] >= 3) // p % 8 getCombinations(primeCounts - [2]->3, numSoFar-1, str + "8") getCombinations(primeCounts - [2]->3, numSoFar-2, str + "24") getCombinations(primeCounts - [2]->3, numSoFar-3, str + "222") else if (primeCounts[3] >= 1 && primeCounts[2] >= 1) // p % 6 getCombinations(primeCounts - {[2]->1,[3]->1}, numSoFar-1, str + "6") getCombinations(primeCounts - {[2]->1,[3]->1}, numSoFar-2, str + "23") else if (primeCounts[2] >= 2) // p % 4 getCombinations(primeCounts - [2]->2, numSoFar-1, str + "4") getCombinations(primeCounts - [2]->2, numSoFar-2, str + "22") else if (primeCounts[3] >= 1) // p % 3 getCombinations(primeCounts - [3]->1, numSoFar-1, str + "3") else if (primeCounts[2] >= 1) // p % 2 getCombinations(primeCounts - [2]->1, numSoFar-1, str + "2") else ;// do nothing, too few digits 

Given the order in which everything is done, I don't think there would be duplicates.

Improvement:

You do not need to look at p%7 again (deeper on the stack) if you looked at p%5 , since we know that it can no longer be divisible by 7, so many of these checks can be optimized.

primeCounts need not be a map, it can just be an array of 4 in length, and it does not need to be copied, you can simply increase and decrease the values ​​accordingly. Something similar can be done with str (an array of characters).

If there were too many digits for getCombinations(..., str + "8") , it makes no sense to check "24" or "222" . This and similar checks should not be too complicated to implement (just return the bool function).