作者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/m.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