2009年2月16日星期一

程式數學題?

看《網絡暴民 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(m2-n2), c=k(m2+n2),

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

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

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

沒有留言: