作者buffalobill (水牛比尔)
看板puzzle
标题[问题] 分拆９９
时间Fri Sep 25 22:24:51 2020
puzzleUp风味题 Vol.11
这题比较偏数学
搞不好早已有公式也说不一定
【分拆９９】
将99拆成若干整数的和
且这些整数彼此互质
问这些整数的最大乘积为？
例：将99拆成[49,50]相乘可得2450
拆成[22,23,25,29]相乘可得366850
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.230.79.236 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/puzzle/M.1601043893.A.7F4.html
1F：推 arthurduh1: OEIS 有个数列定义差一点，不过应该可以证明是等价的 09/25 23:21
2F：推 LPH66: A000793? 那个定义和这题问的不等价 09/26 03:35
3F：→ LPH66: 我简单用了 Mathematica 搜了一下, 最小反例是 n=21 09/26 03:35
4F：→ LPH66: A000793(21) 是 2+3+4+5+7, 但若限定互质只能有 2+3+5+11 09/26 03:36
5F：→ LPH66: 有趣的是, 这两个结果不同的地方都是 A000793 出现四项相同 09/26 03:44
6F：→ LPH66: 时的第三和第四个数, 或许是因为正好就是 +1 +2 +3 +4 09/26 03:44
7F：→ LPH66: 然後恰巧题目问的 99 是在 97~100 这组四项相同中的第三项 09/26 03:45
8F：推 arthurduh1: 是 A000793 没错 09/26 05:40
9F：→ arthurduh1: 不过他是算 LCM，{2, 3, 4, 5, 7} 的 LCM 是 420 09/26 05:41
10F：→ arthurduh1: 限定互质也可以 {3, 4, 5, 7}，也是 420 09/26 05:42
11F：→ arthurduh1: 应该说 {1, 1, 3, 5, 7} 啦，用 1 补不够的部分 09/26 05:44
12F：推 arthurduh1: 证明的话是考虑 LCM 的话，可以把重复的质因数拿掉 09/26 05:46
13F：→ arthurduh1: 换成一堆 1，LCM 不会变 09/26 05:48
14F：→ arthurduh1: 比如 {2, 3, 4, 5, 7} 可以改为 {1, 1, 3, 4, 5, 7} 09/26 05:48
15F：→ arthurduh1: 留下该质因数次方数最高的那一项即可 09/26 05:48
16F：→ arthurduh1: *05:44 漏了 4，是 {1, 1, 3, 4, 5, 7} 09/26 05:50
17F：→ arthurduh1: 不过如果限制不能使用 1，的确就不等价了 09/26 05:51
18F：推 arthurduh1: 或者限制数字要相异 09/26 06:05
19F：→ buffalobill: 可以使用1，任意数量的1还是彼此互质的 09/26 09:49
20F：→ buffalobill: 不过限制使用1反而会让答案变小这点很有趣 09/26 09:52