→ apom0228 : 感謝指點 10/22 08:02
※ 編輯: LPH66 (106.1.234.196 臺灣), 11/17/2020 20:21:45
※ 引述《apom0228 (ㄚ碰)》之銘言：
: 2.設a,b,c為質數,若a^2+b^2+c^2=2019,則a+b+c的最大值與最小值的差?
: → tyz : 第二題我除了暴力土法煉鋼之外 還想不到其他解~ 10/21 22:57
其實一個個拆不會很麻煩 (因為數字真的不大)
主要是質因數分解後運用 Brahmagupta–Fibonacci 恆等式:
(a^2+b^2)(c^2+d^2) = (ac+bd)^2 + (ad-bc)^2 = (ac-bd)^2 + (ad+bc)^2
以及平方和定理: 一數是平方和若且唯若它質因數分解中 4k+3 的質因數次方皆為偶數
來逐一檢討
2019 < 2025 = 45^2, 所以從 43 往下試:
2019-43^2 = 2019-1849 = 170 = 10*17 = (1^2+3^2)*(1^2+4^2) = 7^2 + 11^2 (O)
= 1^2 + 13^2 (X)
2019-41^2 = 2019-1681 = 338 = 13*26 = (2^2+3^2)*(1^2+5^2) = 7^2 + 17^2 (O)
= 13^2 + 13^2 (O)
2019-37^2 = 2019-1369 = 650 = 50*13
= (1^2+7^2)*(2^2+3^2) = 11^2 + 23^2 (O)
= 17^2 + 19^2 (O)
= (5^2+5^2)*(2^2+3^2) = 5^2 + 25^2 (X)
2019-31^2 = 2019-961 = 1058 = 2*23*23 = 23^2 + 23^2 (O)
2019-29^2 = 2019-841 = 1178 = 2*19*31, 出現單獨 4k+3 質數故 1178 不是平方和
2019-23^2 以下就不用算了, 因為已經有 2019 = 23^2+23^2+31^2 的組合
(以上未寫出的分解是會找出重覆的組合的分解, 主要是 2 = 1^2 + 1^2 的關係)
總計這裡一共找到了:
2019 = 7^2 + 11^2 + 43^2
= 7^2 + 17^2 + 41^2
= 13^2 + 13^2 + 41^2
= 11^2 + 23^2 + 37^2
= 17^2 + 19^2 + 37^2
= 23^2 + 23^2 + 31^2 一共六組解
所求最大是第六組 77, 最小是第一組 61
====
這樣的計算量做為中學競賽題應該還算可以
其他巧解方面我只想得到用餘數篩
但因為 2019 = 2016+3 的關係, 若除數是 2016 的因數幾乎不會有明確組合的線索
偏偏不論是平方數的常用除數 3, 4, 8 或質數的常用除數 6, 12 都是 2016 的因數..
我只能由除以 6 知沒有 2 和 3, 由除以 5 知沒有 5 而已
--
LPH [acronym]
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.1.234.196 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1603305241.A.5E7.html