论坛 › 难题征解 › 将正整数分解为不超过3个因子之积

王守恩 发表于 2022-11-21 07:41:56

将正整数分解为不超过3个因子之积

将一个正整数分解为不超2个大于1的因子之积的问题比较简单，基本上等价于因子个数问题，
即`n`的不超过`\sqrt n`的因子个数，答案是`\D\left\lceil\Omega(n)/2\right\rceil`（`\Omega(n)`是整数`n`因子个数），
在OEIS网站上为序列A038548。

`\Omega(n)`的计算公式还是比较简明的。设`n=p_1^{t_1}p_2^{t_2}...p_i^{t_i}...p_r^{t_r}`（标准分解式），那么\[
\Omega(n)=(1+t_1)(1+t_2)...(1+t_i)...(1+t_r)
\]但是，当我们思考将一个正整数分解为不超3个大于1的因子之积的组合有多少时，似乎没那么好计算了。进以一步，去之千里。
前几项手工计算结果如下：
a(01)=1: （约定）
a(02)=1: 2
a(03)=1: 3
a(04)=2: 4, 2×2
a(05)=1: 5
a(06)=2: 6, 2×3
a(07)=1: 7
a(08)=3: 8, 2×4, 2×2×2
a(09)=2: 9, 3×3
a(10)=2: 10, 2×5
a(11)=1: 11
a(12)=4: 12, 2×6, 3×4, 2×2×3
a(13)=1: 13
a(14)=2: 14, 2×7
a(15)=2: 15, 3×5
a(16)=4: 16, 2×8, 4×4, 2×2×4
a(17)=1: 17
a(18)=4: 18,2×9, 3×6, 2×3×3
a(19)=1: 19
a(20)=4: 20, 2×10, 4×5, 2×2×5
a(21)=2: 21, 3×7
a(22)=2: 22, 2×11
a(23)=1: 23
a(24)=6: 24, 2×12,3×8, 4×6, 2×2×6, 2×3×4

得到一个在OEIS找不到的整数序列
1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 4, 1, 4, 1, 4, 2, 2, 1, 6, 2, 2, 3, 4, 1, 5, 1, 5, 2, 2, 2, 8, ......

northwolves 发表于 2022-11-21 21:19:07

A034836: Number of ways to write n as n = x*y*z with 1 <= x <= y <= z

northwolves 发表于 2022-11-21 21:57:25

from sympy import divisors
def a(n):
    d=divisors(n)
    c=len(d)//2+1
    s=[]
    for i in range(c):
      for j in range(i,c):
            k=n//(d*d)
            if k in d and k>=d:
                s.append(str(d)+'*'+str(d)+'*'+str(k))
    return(len(s),s)
print(a(1728))

It returns:
(51, ['1*1*1728', '1*2*864', '1*3*576', '1*4*432', '1*6*288', '1*8*216', '1*9*192', '1*12*144', '1*16*108', '1*18*96', '1*24*72', '1*27*64', '1*32*54', '1*36*48', '2*2*432', '2*3*288', '2*4*216', '2*6*144', '2*8*108', '2*9*96', '2*12*72', '2*16*54', '2*18*48', '2*24*36', '2*27*32', '3*3*192', '3*4*144', '3*6*96', '3*8*72', '3*9*64', '3*12*48', '3*16*36', '3*18*32', '3*24*24', '4*4*108', '4*6*72', '4*8*54', '4*9*48', '4*12*36', '4*16*27', '4*18*24', '6*6*48', '6*8*36', '6*9*32', '6*12*24', '6*16*18', '8*8*27', '8*9*24', '8*12*18', '9*12*16', '12*12*12'])

王守恩 发表于 2022-11-22 16:11:03

受2#启发，得到一个将正整数分解为不超过 a 个大于1的因子之积的程序。（前60项，约定a(1)=1)
Table := b = If, Sum, {d, Select}]]];
Parallelize@Array &@Apply@ Sort, #1[] > #2[] &]] &, 60], {a, 2, 9}]取a=2~9，前60项各如下表：
{1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 3, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 2, 3, 1, 4, 1, 3, 2, 2, 2, 5, 1, 2, 2, 4, 1, 4, 1, 3, 3, 2, 1, 5, 2, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 6},
{1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 4, 1, 4, 1, 4, 2, 2, 1, 6, 2, 2, 3, 4, 1, 5, 1, 5, 2, 2, 2, 8, 1, 2, 2, 6, 1, 5, 1, 4, 4, 2, 1, 9, 2, 4, 2, 4, 1, 6, 2, 6, 2, 2, 1, 10},
{1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 5, 1, 6, 2, 2, 2, 9, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 11, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11},
{1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 5, 1, 7, 2, 2, 2, 9, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 12, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11},
{1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 5, 1, 7, 2, 2, 2, 9, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 12, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11},
{1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 5, 1, 7, 2, 2, 2, 9, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 12, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11},
{1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 5, 1, 7, 2, 2, 2, 9, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 12, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11},
{1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 5, 1, 7, 2, 2, 2, 9, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 12, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11}

将正整数分解为任意多个大于1的因子之积的组合数，则是下面的程序。（前60项，约定a(1)=1)
T = T = 1; T := T = DivisorSum*T &]; a := T; a /@ Range
{1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 5, 1, 7, 2, 2, 2, 9, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 12, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11}

王守恩 发表于 2022-11-24 14:04:16

在前述序列A034836中，a(n)定义为正整数 n 分解为不超过 3 个大于1的因子之积的组合数。（约定a(1)=1)
我们看到A034836远非单调，取值起伏很大，所以可以按其值定义其下标集（即正整数集）的一个划分，即
SubSet(k)={x∈N|a(x)=k}.
显然， SubSet(1)={1和素数列｝,
观察可知，SubSet(2)={双素数积}={4,6,9,10,14,15,21,...}
观察可知，SubSet(3)={素数立方}={8,27,125,343,1331,...}
我们取SubSet(k)中最小数（空集取 0），便得到如下序列：
1, 4, 8, 12, 30, 24, 64, 36, 48, 60, 0, 72, 0, 210, 0, 120, 0, 144, 216, 180, 8192, 0, 0, 240, 768, 0, 32768, 420, 0, 1536, 0, 360, 480, 0, 0, 3072, 262144, 864, 0, 900, 2310, 1296, ......
这便是 OEIS的A081833. OEIS给出了前61项却没能给出一个有效的算法和程序。

mathe 发表于 2022-11-27 07:48:40

这个题目在知道n的因子分解情况，计数并不难，是个组合问题。
设$n=p_1^{t_1}p_2^{t_2}...p_r^{t_r}$
我们需要将每个$t_i$拆分成有序三部分，使用隔板法知道方案为$C_{t_i+2}^2$, 所以总数$\prod_{i=1}^r \frac{(t_i+2)(t_i+1)}2$
当然上面方案会有重复计数，但部分数据被重复计数了$3!=6$次，但是如果分解结果如$n=x*x*y$的只被重复计数3次，而$n=x^3$的只被重复计数1次。
其中形如$n=x*x*y$的方案数目显然为$\prod_{i=1}^r (1+\lfloor\frac{t_i}2\rfloor)$
由此我们知道总数为
$\lfloor\frac{\prod_{i=1}^r \frac{(t_i+2)(t_i+1)}2+3\prod_{i=1}^r (1+\lfloor\frac{t_i}2\rfloor)+5}{6}\rfloor$
遍历$r\le 5$的情况就可以遍历121以内的情况，复杂度其实不高

王守恩 发表于 2022-11-27 14:22:02

王守恩 发表于 2022-11-24 14:04
在前述序列A034836中，a(n)定义为正整数 n 分解为不超过 3 个大于1的因子之积的组合数。（约定a(1)=1)
我 ... OEIS---A081833, 给出了前61项。

1, 4, 8, 12, 30, 24, 64, 36, 48, 60, 0, 72, 0, 210, 0, 120, 0, 144, 216, 180, 8192, 0, 0, 240, 768, 0,
32768, 420, 0, 1536, 0, 360, 480, 0, 0, 3072, 262144, 864, 0, 900, 2310, 1296, 0, 960, 0, 840, 0, 720,
12288, 2304, 1728, 1080, 0, 0, 0, 1260, 2592, 0, 0, 4608, 16777216,.....

这个序列因不单调而显得“不美”，我们通过以下处理让它单调化：
1、去除0，然后
2、如果后面存在更小的项，就去掉前面较大的项。
结果得到如下序列

1, 4, 8, 12, 24, 36, 48, 60, 72, 120, 144, 180, 240, 360, 480, 720, 1080, 1260, 2592, 4608, 16777216,.....

这个序列在OEIS是没有的。

补充内容 (2022-11-28 15:02):
想法参考A059992：找不到最好的，找个次点的先用用。       

northwolves 发表于 2022-11-27 21:04:13

a(62)=17766468

(62, ['1*1*17766468', '1*2*8883234', '1*3*5922156', '1*4*4441617', '1*6*2961078', '1*9*1974052', '1*12*1480539', '1*18*987026', '1*36*493513', '1*79*224892', '1*158*112446', '1*237*74964', '1*316*56223', '1*474*37482', '1*711*24988', '1*948*18741', '1*1422*12494', '1*2844*6247', '2*2*4441617', '2*3*2961078', '2*6*1480539', '2*9*987026', '2*18*493513', '2*79*112446', '2*158*56223', '2*237*37482', '2*474*18741', '2*711*12494', '2*1422*6247', '3*3*1974052', '3*4*1480539', '3*6*987026', '3*12*493513', '3*79*74964', '3*158*37482', '3*237*24988', '3*316*18741', '3*474*12494', '3*948*6247', '4*9*493513', '4*79*56223', '4*237*18741', '4*711*6247', '6*6*493513', '6*79*37482', '6*158*18741', '6*237*12494', '6*474*6247', '9*79*24988', '9*158*12494', '9*316*6247', '12*79*18741', '12*237*6247', '18*79*12494', '18*158*6247', '36*79*6247', '79*237*948', '79*316*711', '79*474*474', '158*158*711', '158*237*474', '237*237*316'])

northwolves 发表于 2022-11-27 21:45:39

本帖最后由 northwolves 于 2022-11-27 23:43 编辑

王守恩 发表于 2022-11-27 14:22
任意正整数分解为 3 个因子之积, 可以有 n 种分解方式，我们取其中最小的那个数。

a(01)=01: 1×1×01,
...

这个很容易漏，比如a(66)=1440,a(100)=786432

northwolves 发表于 2022-11-27 23:36:16

northwolves 发表于 2022-11-27 21:04
a(62)=17766468

(62, ['1*1*17766468', '1*2*8883234', '1*3*5922156', '1*4*4441617', '1*6*2961078',...

计算有误

查看完整版本: 将正整数分解为不超过3个因子之积