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

northwolves · 发表于 2022-12-3 20:23:57

对比了一下数据，我的前200项似乎都对了。有个疑问，新的质因子的加入需要什么条件？比如第一次出现17，19，23，29？或者3^3,5^3代替新的两个因子？

mathe · 发表于 2022-12-3 21:35:47

很容易分析一个必要条件，比如如果有$2^a3^b5^c7^d11^e17$是一个数目达到$\frac{(a+1)(b+1)(c+1)(d+1)2}2$的最优解
由于$2^{2a+1)3^b5^c7^d11^e$也达到同样数目，于是就可以得出$2^a 17\le 2^{2a+1}$,即$17 \le 2^{a+1}$
同样还有$2^a3^{2b+1}5^c7^d11^e$也达到同样数目，得到$17\le 3^{b+1}$等等。
类似还有反向操作，如果$2^a3^b5^c7^d11^e$是最优的达到数目$\lfloor\frac{(a+1)(b+1)(c+1)(d+1)}2\rfloor$的方案
那么如果a是奇数，$2^{(a-1)/2}3^b5^c7^d11^e17$可以达到相同的数目，于是得出$17 \ge \frac{a+1}2$等等

mathe · 发表于 2022-12-3 21:58:51

这个题目和 https://www.zhihu.com/question/536022619/answer/2515444318 密切相关

王守恩 · 发表于 2022-12-4 08:09:43

northwolves 发表于 2022-12-2 19:09
硬算的前200项，估计部分项不一定是最小的，期待mathe的优化
[1, 2, 6, 12, 24, 48, 60, 144, 120, 180, ...

任意正整数分解为 2 个因子之积, 可以有 n 种分解方式，我们取其中最小的那个数。

a(01)=001: 1×001,
a(02)=004: 1×004, 2×002,
a(03)=012: 1×012, 2×006, 3×04,
a(04)=024: 1×024, 2×012, 3×08, 4×06,
a(05)=036: 1×036, 2×018, 3×12, 4×09, 6×06,
a(06)=060: 1×060, 2×030, 3×20, 4×15, 5×12, 6×10,
a(07)=192: 1×192, 2×096, 3×64, 4×48, 6×32, 8×24, 12×16,
a(08)=120: 1×120, 2×060, 3×40, 4×30, 5×24, 6×20, 08×15, 10×12,
a(09)=180: 1×180, 2×090, 3×60, 4×45, 5×36, 6×30, 09×20, 10×18, 12×15,
a(10)=240: 1×240, 2×120, 3×80, 4×60, 5×48, 6×40, 08×30, 10×24, 12×20, 15×16,

OEIS---A038549, 给出了前 1000 项。

1, 4, 12, 24, 36, 60, 192, 120, 180, 240, 576, 360, 1296, 900, 720, 840, 9216, 1260,
786432, 1680, 2880, 15360, 3600, 2520, 6480, 61440, 6300, 6720, 2359296, 5040,
3221225472, 7560, 46080, 983040, 25920,10080, 206158430208, 32400, 184320, .....

两位大侠的算法我还是没看懂，能再来几项？谢谢 mathe！谢谢 northwolves！

王守恩 · 发表于 2022-12-4 10:22:56

northwolves 发表于 2022-12-3 20:23
对比了一下数据，我的前200项似乎都对了。有个疑问，新的质因子的加入需要什么条件？比如第一次出现17，19 ...

类似的疑问。

不存在: 恰好有 6 组 5 个因子之积的正整数。

王守恩 · 发表于 2022-12-8 12:12:10

任意正整数的倒数分拆为 2 个单位分数之和, 恰好有 n 种分拆方式，我们取其中最小的那个数。

a(1)=02: 1/03+1/006,
a(2)=04: 1/05+1/0020, 1/06+1/0012,
a(3)=08: 1/09+1/0072, 1/10+1/0040, 1/12+1/0024,
a(4)=06: 1/07+1/0042, 1/08+1/0024, 1/09+1/0018, 1/10+1/015,
a(5)=32: 1/33+1/1056, 1/34+1/0544, 1/36+1/0288, 1/40+1/160, 1/48+1/090,
a(6)=64: 1/65+1/4160, 1/66+1/2112, 1/68+1/1088, 1/72+1/576, 1/80+1/320, 1/96+1/192,
a(7)=12: 1/13+1/0156, 1/14+1/0084, 1/15+1/0060, 1/16+1/048, 1/18+1/036, 1/20+1/030, 1/21+1/28,

2, 4, 8, 6, 32, 64, 12, 256, 512, 24, 2048, 36, 30, 16384, 32768, 96, 72, 262144, 192, 1048576,
2097152, 60, 8388608, 216, 768, 67108864, 288, 1536, 536870912, 1073741824, 120, 576, 8589934592,
6144, 34359738368, 68719476736, 180, 864, 549755813888, 210, 2199023255552, 2304, 49152, ......

参考OEIS---A016017, 给出了前 1000 项。考虑实用，我们这样想：

任意正整数的倒数分拆为 2 个单位分数之和, 在 n 种分拆方式中，我们取最小的那个数。

2, 4, 6, 12, 24, 30, 60, 120, 180, 210, 360, 420, 840, 1260, 2310,2520, 4620, 7560, 9240,
13860, 27720, 60060, 83160, 110880, 120120, 221760, 485100, 2419200, .....

猜测: 每一项不会超过前面项的2倍。是这样吗？

northwolves · 发表于 2022-12-8 12:24:12

13860, 27720, 60060, 83160, 110880, 120120, 221760, 485100, 2419200, .....

王守恩 · 发表于 2022-12-9 09:47:14

任意正整数的倒数分拆为 3 个单位分数之和, 有 n 种分拆方式。

a(1)=03: 1/2+1/03+1/0006, 1/2+1/04+1/0004, 1/3+1/03+1/003,
a(2)=10: 1/3+1/07+1/0042, 1/3+1/08+1/0024, 1/3+1/09+1/018, 1/3+1/10+1/015, 1/3+1/12+1/012, ......
a(3)=21: 1/4+1/13+1/0156, 1/4+1/14+1/0084, 1/4+1/15+1/060, 1/4+1/16+1/048, 1/4+1/18+1/036, ......
a(4)=28: 1/5+1/21+1/0420, 1/5+1/22+1/0220, 1/5+1/24+1/120, 1/5+1/25+1/100, 1/5+1/28+1/070, ......
a(5)=36: 1/6+1/31+1/0930, 1/6+1/32+1/0480, 1/6+1/33+1/330, 1/6+1/34+1/255, 1/6+1/35+1/210, ......
a(6)=57: 1/7+1/43+1/1806, 1/7+1/44+1/0924, 1/7+1/45+1/630, 1/7+1/46+1/483, 1/7+1/48+1/336, ......
a(7)=42: 1/8+1/57+1/3192, 1/8+1/58+1/1624, 1/8+1/60+1/840, 1/8+1/63+1/504, 1/8+1/64+1/448, ......

OEIS---A004194, 只给出了前 100 项。就这100 项，我的电脑也是可以的。

{3, 10, 21, 28, 36, 57, 42, 70, 79, 96, 62, 160, 59, 136, 196, 128, 73, 211, 80, 292, 245, 157, 93, 366, 156, 174, 230, 340,
106, 497, 90, 269, 322, 211, 453, 538, 85, 216, 378, 604, 121, 623, 104, 473, 648, 204, 135, 706, 227, 437, 387, 467, 125,
601, 561, 783, 385, 252, 172, 1290, 108, 273, 887, 442, 586, 753, 121, 555, 478, 1054, 161, 1166, 118, 288, 869, 561, 705,
843, 147, 1178, 465, 297, 190, 1687, 599, 288, 501, 969, 190, 1723, 646, 558, 472, 310, 733, 1211, 143, 664, 1124, 1106,}

王守恩 · 发表于 2022-12-9 14:18:59

northwolves 发表于 2022-12-8 12:24
13860, 27720, 60060, 83160, 110880, 120120, 221760, 485100, 2419200, .....

约定 3/n=1/A+1/B 有 n 种分拆方式。

a(01)=0:
a(02)=1: 1/1+1/02,
a(03)=1: 1/2+1/02,
a(04)=1: 1/2+1/04,
a(05)=1: 1/2+1/10,
a(06)=2: 1/3+1/06, 1/4+1/04,
a(07)=0:
a(08)=2: 1/3+1/24, 1/4+1/08,
a(09)=2: 1/4+1/12, 1/6+1/06,
a(10)=2: 1/4+1/20, 1/5+1/10,
a(11)=1: 1/4+1/44,
a(12)=3: 1/5+1/20, 1/6+1/12, 1/8+1/8,

{0, 1, 1, 1, 1, 2, 0, 2, 2, 2, 1, 3, 0, 3, 2, 2, 1, 5, 0, 4, 2, 2, 1, 4, 1, 3, 3, 3, 1, 5, 0, 3, 2, 2, 3, 8,
0, 3, 2, 5, 1, 5, 0, 4, 5, 2, 1, 5, 0, 4, 2, 3, 1, 8, 2, 6, 2, 2, 1, 8, 0, 3, 5, 3, 3, 5, 0, 4, 2, 6, 1, 11,
0, 3, 3, 3, 3, 5, 0, 7, 4, 2, 1, 8, 2, 3, 2, 5, 1,14,0, 4, 2, 2, 3, 6, 0, 5, 5, 6, 1, 5, 0, 6, 5, 2, 1, 13}

粗看: n=1,7, 13, 19, 25, 31, 37, 43, 49, 55, 61, ..... 即 6k+1, 3/n=1/A+1/B 无解

细看: n= 25, 55, 85, 115, 121, 145, 175, 187, 205, 235, ......  3/n=1/A+1/B 还是有解的

就这串数：25, 55, 85, 115, 121, 145, 175, 187, 205, 235, 253, 265, 289, 295, 319, 325, ......

1, A176275给出数字串
  25, 55, 85, 115, 121, 145, 175, 187, 205, 235, 253, 265, 289, 295, 319, 325, 355, 385, 391, 415,
  445, 451, 475, 493, 505, 517, 529, 535, 565, 583, 595, 625, 649, 655, 667, 685, 697, 715, 745, 775,
  781, 799, 805, 835, 841, 865, 895, 901, 913, 925, 943, 955, 979, 985, 1003, 1015, 1045, 1075, ........

2,  northwolves  给出通项公式: (6a+5)(6b+5) ,a,b>=0

1 与 2 的差异在于:  1 没有数字 847， 2 有 847 , 自己就搞糊涂了？
又：怎么把 “(6a+5)(6b+5) ,a,b>=0”  按从小到大排列起来？

补充内容 (2022-12-10 07:35):
搞清楚了: northwolves  给出通项公式是对的，A176275不是做这道题的。

王守恩 · 发表于 2022-12-10 07:30:46

约定 3/n=1/A+1/B 有 n 种分拆方式。

a(01)=0:
a(02)=1: 1/1+1/02,
a(03)=1: 1/2+1/02,
a(04)=1: 1/2+1/04,
a(05)=1: 1/2+1/10,
a(06)=2: 1/3+1/06, 1/4+1/04,
a(07)=0:
a(08)=2: 1/3+1/24, 1/4+1/08,
a(09)=2: 1/4+1/12, 1/6+1/06,
a(10)=2: 1/4+1/20, 1/5+1/10,
a(11)=1: 1/4+1/44,
a(12)=3: 1/5+1/20, 1/6+1/12, 1/8+1/8,

{0, 1, 1, 1, 1, 2, 0, 2, 2, 2, 1, 3, 0, 3, 2, 2, 1, 5, 0, 4, 2, 2, 1, 4, 1, 3, 3, 3, 1, 5, 0, 3, 2, 2, 3, 8,
0, 3, 2, 5, 1, 5, 0, 4, 5, 2, 1, 5, 0, 4, 2, 3, 1, 8, 2, 6, 2, 2, 1, 8, 0, 3, 5, 3, 3, 5, 0, 4, 2, 6, 1, 11,
0, 3, 3, 3, 3, 5, 0, 7, 4, 2, 1, 8, 2, 3, 2, 5, 1,14,0, 4, 2, 2, 3, 6, 0, 5, 5, 6, 1, 5, 0, 6, 5, 2, 1, 13}

粗看: n=1,7, 13, 19, 25, 31, 37, 43, 49, 55, 61, ..... 即 6k+1, 3/n=1/A+1/B 无解

细看: n= 25, 55, 85, 115, 121, 145, 175, 187, 205, 235, ...... 3/n=1/A+1/B 还是有解的

为节约篇幅，我们把 6k+1 特别地拉出来：

0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 1, 0, 0, 0, 2, 0, 0, 0, 0, 3, 0, 2, 0, 0, 2, 0, 0, 0, 0, 2,
0, 0, 2, 0, 2, 0, 0, 0, 1, 2, 0, 0, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 0, 6, 2, 0, 0, 0, 2, 0, 0, 0, 0, 2, 2, 0, 0, 0, 3,
0, 0, 2, 0, 2, 0, 2, 0, 1, 2, 0, 0, 0, 0, 2, 0, 0, 2, 0, 6, 0, 0, 0, 0, 2, 0, 0, 0, 2, 2, 0, 2, 0, 0, 2, 0, 2, 0, 0, 6,
0, 0, 0, 0, 2, 0, 0, 0, 0, 3, 2, 0, 0, 2, 6, 0, 0, 0, 0, 2, 1, 3, 0, 0, 2, 0, 0, 0, 0, 2, 2, 0, 2, 0, 3, 0, 0, 2, 0, 2,

对上面的数字串，我们把不是 0 的又特别地拉出来：

5, 10, 15, 20, 21, 25, 30, 32, 35, 40, 43, 45, 49, 50, 54, 55, 60, 65, 66, 70, 75, 76, 80, 83, 85, 87, 89, 90, 95, 98,
100, 105, 109, 110, 112, 115, 117, 120, 125, 130, 131, 134, 135, 140, 141, 142, 145, 150, 151, 153, 155, 158, 160,
164, 165, 168, 170, 175, 180, 181, 185, 186, 190, 195, 197, 199, 200, 202, 204, 205, 208, 210, 215, 219, 220, 225,
227, 228, 230, 235, 236, 240, 241, 245, 250, 252, 253, 255, 257, 260, 263, 265, 270, 273, 274, 275, 280, 281, 285,
286, 287, 290, 295, 296, 300, 304, 305, 307, 310, 315, 318, 319, 320, 321, 322, 325, 329, 330, 335, 338, 340, 342,
344, 345, 350, 351, 355, 360, 362, 363, 365, 369, 370, 372, 373, 375, 380, 384, 385, 388, 389, 390, 395, 400, ......

A199860 是这串数，可通项公式没这么好。

Select[Range[568], MemberQ[Mod[Take[Divisors[6 # - 5], {1, -1}], 6], 5] &]

账号		自动登录	找回密码
密码			欢迎注册

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

评分

点评