[問題] 分拆99

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 (水牛比爾)時間4年前 (2020/09/25 22:24), 編輯推噓5(5015)
留言20則, 3人參與, 4年前最新討論串1/2 (看更多)
puzzleUp風味題 Vol.11 這題比較偏數學 搞不好早已有公式也說不一定 【分拆99】 將99拆成若干整數的和 且這些整數彼此互質 問這些整數的最大乘積為? 例:將99拆成[49,50]相乘可得2450 拆成[22,23,25,29]相乘可得366850 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.79.236 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1601043893.A.7F4.html

09/25 23:21, 4年前 , 1F
OEIS 有個數列定義差一點,不過應該可以證明是等價的
09/25 23:21, 1F

09/26 03:35, 4年前 , 2F
A000793? 那個定義和這題問的不等價
09/26 03:35, 2F

09/26 03:35, 4年前 , 3F
我簡單用了 Mathematica 搜了一下, 最小反例是 n=21
09/26 03:35, 3F

09/26 03:36, 4年前 , 4F
A000793(21) 是 2+3+4+5+7, 但若限定互質只能有 2+3+5+11
09/26 03:36, 4F

09/26 03:44, 4年前 , 5F
有趣的是, 這兩個結果不同的地方都是 A000793 出現四項相同
09/26 03:44, 5F

09/26 03:44, 4年前 , 6F
時的第三和第四個數, 或許是因為正好就是 +1 +2 +3 +4
09/26 03:44, 6F

09/26 03:45, 4年前 , 7F
然後恰巧題目問的 99 是在 97~100 這組四項相同中的第三項
09/26 03:45, 7F

09/26 05:40, 4年前 , 8F
是 A000793 沒錯
09/26 05:40, 8F

09/26 05:41, 4年前 , 9F
不過他是算 LCM,{2, 3, 4, 5, 7} 的 LCM 是 420
09/26 05:41, 9F

09/26 05:42, 4年前 , 10F
限定互質也可以 {3, 4, 5, 7},也是 420
09/26 05:42, 10F

09/26 05:44, 4年前 , 11F
應該說 {1, 1, 3, 5, 7} 啦,用 1 補不夠的部分
09/26 05:44, 11F

09/26 05:46, 4年前 , 12F
證明的話是考慮 LCM 的話,可以把重複的質因數拿掉
09/26 05:46, 12F

09/26 05:48, 4年前 , 13F
換成一堆 1,LCM 不會變
09/26 05:48, 13F

09/26 05:48, 4年前 , 14F
比如 {2, 3, 4, 5, 7} 可以改為 {1, 1, 3, 4, 5, 7}
09/26 05:48, 14F

09/26 05:48, 4年前 , 15F
留下該質因數次方數最高的那一項即可
09/26 05:48, 15F

09/26 05:50, 4年前 , 16F
*05:44 漏了 4,是 {1, 1, 3, 4, 5, 7}
09/26 05:50, 16F

09/26 05:51, 4年前 , 17F
不過如果限制不能使用 1,的確就不等價了
09/26 05:51, 17F

09/26 06:05, 4年前 , 18F
或者限制數字要相異
09/26 06:05, 18F

09/26 09:49, 4年前 , 19F
可以使用1,任意數量的1還是彼此互質的
09/26 09:49, 19F

09/26 09:52, 4年前 , 20F
不過限制使用1反而會讓答案變小這點很有趣
09/26 09:52, 20F
文章代碼(AID): #1VRVsrVq (puzzle)
文章代碼(AID): #1VRVsrVq (puzzle)