数学研发论坛

 找回密码
 欢迎注册
查看: 312|回复: 30

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

[复制链接]
发表于 2022-11-21 07:41:56 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
将一个正整数分解为不超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, ......
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-11-21 21:19:07 | 显示全部楼层

点评

还是有嘛,不知道王守恩同志怎么搜的。  发表于 2022-11-22 09:15
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-11-21 21:57:25 | 显示全部楼层
  1. from sympy import divisors
  2. def a(n):
  3.     d=divisors(n)
  4.     c=len(d)//2+1
  5.     s=[]
  6.     for i in range(c):
  7.         for j in range(i,c):
  8.             k=n//(d[i]*d[j])
  9.             if k in d and k>=d[j]:
  10.                 s.append(str(d[i])+'*'+str(d[j])+'*'+str(k))
  11.     return(len(s),s)
  12. 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'])

评分

参与人数 1威望 +9 金币 +9 贡献 +9 经验 +9 鲜花 +9 收起 理由
王守恩 + 9 + 9 + 9 + 9 + 9 谢谢 northwolves!>61的可以有吗?

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-11-22 16:11:03 | 显示全部楼层
受2#启发,得到一个将正整数分解为不超过 a 个大于1的因子之积的程序。(前60项,约定a(1)=1)
  1. Table[b[n_, i_, t_] := b[n, i, t] = If[n == 1, 1, If[t == 1, Boole[n <= i], Sum[b[n/d, d, t - 1], {d, Select[Divisors@n, # <= i &]}]]];
  2. Parallelize@Array[b[#, #, a] &@Apply[Times, Power @@[url=home.php?mod=space&uid=6175]@[/url] Sort[FactorInteger[#], #1[[2]] > #2[[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)
  1. T[_, 1] = T[1, _] = 1; T[n_, m_] := T[n, m] = DivisorSum[n, Boole[1 < # <= m]*T[n/#, #] &]; a[n_] := T[n, n]; a /@ Range[60]
复制代码

{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}

点评

nyy
你的代码真难看!我看到这种代码,直接受不了,一定注释都没有,也没有缩进  发表于 2022-11-23 08:58
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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项却没能给出一个有效的算法和程序。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 5 天前 | 显示全部楼层
这个题目在知道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以内的情况,复杂度其实不高

点评

我就好奇: 庞大的第62项是怎样的一个数(那么多年没有出现)。  发表于 5 天前
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 5 天前 | 显示全部楼层
王守恩 发表于 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:找不到最好的,找个次点的先用用。       

点评

有才怪呢!你这么处理的意义在哪里?  发表于 4 天前
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 5 天前 | 显示全部楼层
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'])
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 5 天前 | 显示全部楼层
本帖最后由 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

点评

a(64)=1800,a(69)=1680,a(70)=3840,...每个数都得从头开始。  发表于 4 天前
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 5 天前 | 显示全部楼层
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',  ...

计算有误

点评

这是一个比单纯的素数分解更要命的问题。  发表于 4 天前
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-12-2 19:49 , Processed in 0.074305 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表