程式數學題？

看《網絡暴民 Jacky's Blog》，有篇文章這樣說：

最近發現一個叫 Project Euler 的網站，是一個數學問題的網站，特點是這些問題通常都要用程式解決，例如：

• Add all the natural numbers below one thousand that are multiples of 3 or 5.
• Find the largest prime factor of a composite number.
• Find the only pythagorean triplet, {a,b,c}, for which a + b + c = 1000

的而且確，大部份現實中的數學問題都要用電腦解決，但上述三個例子中剛好有兩個用簡單的筆算就搞得掂。

第一題其實是最基礎的集合論問題（下面 "|" 指 "divides"，而 floor(x) 指最接近但不大於 x 的整數）：

{3|n or 5|n} = ({3|n} ∪ {5|n}) \ {3|n and 5|n}
#{3|n} = floor(999/3) = 333,
#{5|n} = floor(999/5) = 199,
#{3|n and 5|n} = floor(999/15) = 66.

sum({3|n or 5|n})
= sum({3|n}) + sum({5|n}) - sum({3|n and 5|n})
= (3+6+...+999) + (5+10+...+995) - (15+30+...+990)
= (3+999)×333/2 + (5+995)×199/2 + (15+990)×66/2
= 1002×333/2 + 1000×199/2 - 1005×66/2
= 1000×(333+199+66)/2 + 2×333/2 - 5×66/2
= 1000×466/2 + 333 - 165
= 233000 + 168 = 233168.

第二題確是難題。即使是念電腦而不是念數學的也知道在密碼學 (Cryptography) 中，要省時地作因子分解需要一些特殊的算則（例如看這裏）。

第三題以一般情形來說當然困難，但現在這個特殊情形卻很容易解決。其實讀中學時稍稍對數學發燒的人都知道頭四個 a, b 互質的畢達哥拉斯數組為 (3, 4, 5), (5, 12, 13), (7, 24, 25) 及 (8, 15, 17)，其中第四組數 (8, 15, 17) 的總和為 40，可以除盡 1000。把整個數組乘上 1000/40 = 25，得答案 (200, 375, 425)。

即使不知有 (8, 15, 17) 這個數組，問題也可以用些少數學解決。根據 Euclid's formula，所有 Pythagorean triple (a,b,c) 都可以用以下方式生成：

a=k(2mn), b=k(m²-n²), c=k(m²+n²),

其中 k,m,n 為正整數，m>n，而且 m 和 n 之中剛好有一個是單數。運用 Euclid's formula，我們有

a+b+c=1000,
2kmn+2km²=1000
km(m+n)=500.

很自然地，我們從 k=1 試起，得 m(m+n)=500。要 m>n，唯一的可能是 m=20, n=5，剛好一單一雙，於是答案為 a=2mn=200, b=m²-n²=375, c=m²+n²=425。