有多少n位数字与产品p

Question

我们应该使用什么算法来获得n位数的计数,使得其数字的乘积为p; 这里的特殊情况是没有数字应该是1;

到目前为止我所想的是对p进行素数分解.假设n = 3且p = 24.

我们首先进行24的素因数分解得到:2*2*2*3.

现在我有确定这些组合的问题

4*2*3,2*4*3,....等即使可以这样做...我将如何缩放为n小于素数的方式.

我不太确定这是否是正确的方向......欢迎提出任何意见.

Answer 1

首先,你真的不需要完全素数分解,只需要分解到比你的基数小的素数(我猜你的意思是10,但问题可以推广到任何基数).所以我们只需要分解为前4个素数:2,3,5和7.如果其余(素数或非素数)因子大于1,则问题有0个解.

现在,让我们假设这个数字p被考虑在内:

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

并且还由n数字组成:

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

然后,重新排列数字,也将是:

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

在哪里qi >= 0和q2 + q3 + ... q9 = n

而且(由于因素分解):

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

所以,q5和q7是固定的,我们必须找到所有非负整数解的方程:
(其中未知数是休息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

对于上述每个解决方案,都有几个数字重新排列,可以通过以下公式找到:

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

必须总结一下.

可能有一个封闭的公式,使用生成函数,您可以在Math.SE发布它

示例p=24,n=3:

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

我们有:

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

整数解决方案:

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

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

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

给出:

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

和 3+6 = 9整体解决方案.

示例p=3628800,n=10:

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

我们有:

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

整数解决方案:

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

是(q2, q3, q4, q6, q8, q9)(以及相应的数字和每个解决方案的重新排列):

(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

2043720如果我没有犯任何错误,这是完全解决方案..