※ 引述《AndyDing (丁彬)》之銘言：
: 原來的題目是：
: 求最小的 10 組正整數數對 (a,b)，a<b，
: 使得 1+2+3+…+a = a+(a+1)+(a+2)+…+b。
: 我用程式算得
: ( 6, 8)
: ( 35, 49)
: ( 204, 288)
: ( 1189, 1681)
: ( 6930, 9800)
: ( 40391, 57121)
: ( 235416, 332928)
: ( 1372105, 1940449)
: ( 7997214,11309768)
: (46611179,65918161)
: 以上沒什麼問題。
: 但我發現第 n 組答案會等於 7 * [第(n-1)組 - 第(n-2)組] + 第(n-3)組。
: 這是為什麼呢？
: 謝謝大家。
(1/2)a(a+1)=(1/2)b(b+1)-(1/2)a(a-1)
=> a^2 = (1/2)b(b+1)
因 b 與 (b+1) 互質
故若 b 為偶, 則 b/2 與 (b+1) 互質
若 b 為奇, 則 b 與 (b+1)/2 互質
總之若把 a^2 的質因數分解, p 一定不會同時整除兩者
故其實 b/2 (resp. b) 是平方數, b+1 (resp. (b+1)/2) 也是平方數
兩種情形分別討論: (假設 x,y 是整數)
若 b=2y^2, b+1=x^2 則 x^2-2y^2=1
若 b=x^2, b+1=2y^2 則 x^2-2y^2=-1
而且所有此類的 x,y 也可還原成 a,b
所以就是要找 x^2-2y^2=+-1 的整數解
為了省事, 對任意整數 x,y
定義 N(x+yw)=(x+yw)(x-yw)=x^2-2y^2, 其中 w^2=2
(就是取共軛的乘積啦)
(有興趣的可以檢查, 對每一有以上形式的 u,v
N(u)N(v)=N(uv), N(u)>=0
就像複數絕對值的平方一樣)
注意此形式的數彼此相乘仍為同一形式
那現在就來找 N(u)=+-1 的 u :
第一個很好找的就是 1+w 跟 1-w
N(1+w)=N(1-w)=-1 ( -1/(1-w)=1+w )
現在要來證明所有 N(u)=+-1 的 u 都是 +-(1+w)^k, k 是某一整數
對任一 u = x+yw
N(u)=+-1 表示 x^2 = 2y^2 +-1 , 故若 x!=0 則 |x|>=|y|
假設 |x|!=|y| (即 u!= 1+w or 1-w)
不妨再假設 x,y 皆為正
(否則可乘上 -1 或取倒數, 1/(x+yw)=+-(x-yw), 事後還原回來即可)
則 x > y => 2y-x < x
由 -(x+yw)/(1+w) = -(x+yw)(1-w) = ((2y-x)+(x-y)w)
則此數的前一項整數部份 2y-x 比原有的 x 小
若一直重複類似的步驟
我們得到的數的前一項整數部份(的絕對值)只會越來越小
除非是 1+w 或 1-w=-1/(1+w)
而在此過程中我們只用到 "乘 +-1 "、"取倒數"、"除 (1+w)" 等步驟
故可證明 u 為 +-(1+w)^k 之形
現在題目是 0<a<b
故欲求的 x,y 都是正整數
即為 (1+w)^k 且 k>1
若 k=2, 則 x+yw=(1+w)^2=3+2w, 故 x=3, y=2, a=xy=6, b=2y^2=8
若 k=3, 則 x+yw=(1+w)^3=7+5w, 故 x=7, y=5, a=xy=25, b=x^2=49
若 k=4, 則 x+yw=(1+w)^4=17+12w, 故 x=13, y=6, a=xy=204, b=2y^2=288
(注意一開始的時候有用 b 的奇偶分成 N(u)=1 與 -1 的兩種情形)
依此類推...
(當 k 增加時, a=xy 一定增加, 故要求最小的十個解只要考慮 k=2 到 11 即可)
至於你最後說到的規則
首先只要注意每一解都可以由 a 的值決定
而當 u=x+yw 時, u^2 的 w 係數是 2xy=2a
所以若令 s=(1+w)^2=3+2w
則只要計算 s^n-7[s^(n-1)-s^(n-2)]-s^(n-3) 中 w 的係數
再看看結果 w 的係數是否為零 (即結果是否得到一整數) 即可
上式可化為 s^(n-3)*F(s)
其中 F(s)=(3+2w)^3-7[(3+2w)^2-(3+2w)]-1=(99+70w)-7(14w+10w)-1=0
故不管 n 的值為何, 結果都是 0 (更不用說 w 的係數)
所以得證
不過其實你的規則稍微複雜了一點
上面的 F(s) 其實可以寫成 F(s)=s^3-7s^2+7s-1
所以關鍵在於 F 可不可以分解出更簡單的因式而仍然以 s 為根
則由 s^3-7s^2+7s^1-1=(s-1)(s^2-6s+1)
只要取 F 為 s^2-6s+1 即可
套用你的句子, 就是:
"第 n 組答案會等於 6 * 第(n-1)組 - 第(n-2)組"
簡單多了吧 |D
一般要求這種規則的話只要考慮 s=(1+w)^2=3+2w 所謂最小多項式
就是求最低次的 f 使得 f(s)=0
而因為 s (只有)開到二次根, 這個 f (最多)是二次
所以只要設兩個未知數 A,B
解 s^2+As+B = (3+2w)^2+A(3+2w)+B = (17+3A+B)+(12+2A)w = 0
得 A=-6, B=1
則 s 的最小多項式為 f(s) = s^2+As+B = s^2-6s+1
規則就可以馬上得出...
--
過程其實很簡短的東西, 寫起來還真是麻煩...
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: courant.math.nt