正整数表示为整除链之积

hbghlyj

将正整数$N$表示为正整数之积$d_1×d_2×\cdots×d_k×1×1×\cdots$使得$d_k≠1$且$d_k\mid\cdots\mid d_2\mid d_1$, 有多少种方法.

设$N,N'$表示为整除链之积$\array{N=d_1×d_2×\cdots\\N'=d'_1×d'_2×\cdots}$ 则$NN'$表示为整除链之积$NN'=(d_1d'_1)×(d_2d'_2)×\cdots$
当$N,N'$互素时, 每当$NN'$表示整除链之积, 总能拆成两个$N,N'$的整除链的对应项乘积.
因此只需考虑$N$为素数幂. $N$的方法数等于$N$的各素数幂因数的方法数之积.
$N=p^n$表示为整除链之积等价于把$n$表示为递减的正整数之和的方法数, 即partition function $p(n)$.
例如
$p(2) = 2$：
     2
     1 + 1

$p(3) = 3$：
     3
     2 + 1
     1 + 1 + 1

$p(4) = 5$：
     4
     3 + 1
     2 + 2
     2 + 1 + 1
     1 + 1 + 1 + 1

$p(5) = 7$：
     5
     4 + 1
     3 + 2
     3 + 1 + 1
     2 + 2 + 1
     2 + 1 + 1 + 1
     1 + 1 + 1 + 1 + 1

$p(6) = 11$：
     6
     5 + 1
     4 + 2
     4 + 1 + 1
     3 + 3
     3 + 2 + 1
     3 + 1 + 1 + 1
     2 + 2 + 2
     2 + 2 + 1 + 1
     2 + 1 + 1 + 1 + 1
     1 + 1 + 1 + 1 + 1 + 1

数论函数 $p(n)$ 可以使用 Hardy-Ramanujan-Rademacher 公式递归计算，或使用生成函数计算。

hbghlyj

1. def get_power_factors(n):
2.     factors=[1]
3.     i = 2
4.     while i*i <= n:
5.         power = 2
6.         if n % (i*i) == 0:
7.             if len(factors)<2:
8.                 factors.append(i)
9.             else:
10.                 factors[1]*=i
11.             n//=i*i
12.             factors[0]*=i
13.             while n % i == 0:
14.                 power += 1
15.                 if len(factors)<power:
16.                     factors.append(i)
17.                 else:
18.                     factors[power-1]*=i
19.                 n //= i
20.         i += 1
21.     factors[0]*=n
22.     return factors

Copy the Code

测试
60
[30,2]
99
[33,3]
108
[6,6,3]
288
[6, 6, 2, 2, 2]
5760
[30, 6, 2, 2, 2, 2, 2]

hbghlyj

例子(见The Fundamental Theorem of Finite Abelian Groups)
$108$分解为素幂因数$2^2×3^3$的指数为2、3，所以有$p(2)p(3)=2×3=6$种方法表为整除链之积。
验证:
108
=108
=36×3
=12×3×3
=54×2
=18×6
=6×6×3

青青子衿

hbghlyj 发表于 2023-3-14 16:18
例子(见The Fundamental Theorem of Finite Abelian Groups)
...

有点像整数的乘法分拆，但是要多加一个整除的限制
这个整除限制有点像史密斯标准型的对角元的限制
forum.php?mod=viewthread&tid=7671
$1500=2^2\cdot3\cdot5^3$