盧卡斯數列

盧卡斯數列 (Lucas Sequence) 和斐波那契數列 (Fibonacci Sequence) 有莫大的關係。故本人在介紹斐波那契數以後也得為盧卡斯數列多添一章。

基本介紹

• 中文名：盧卡斯數列
• 外文名：Lucas Sequence
• 通項公式：5)/2]^n
• 數列性質： Ln = Ln-1 + Ln-2

基本概述

盧卡斯數列的通項公式為 f(n)=[(1+√5）/2]^n+[(1-√5)/2]^n

先定義整數 P 和 Q ，使滿足一元二次方程判斷法則： △ = P^2 - 4Q > 0，

從而得一方程 x^2 - Px + Q = 0，其根為 a, b。

現定義盧卡斯數列為：

Un(P,Q) = (a^n - b^n) / (a-b) 及 Vn(P,Q) = a^n + b^n

其中 n 為非負整數，得 U0(P,Q) = 0、 U1(P,Q) = 1 、 V0(P,Q) = 2 、 V1(P,Q) = P、......

我們有下列和盧卡斯數列相關的恆等式：

Um+n = UmVn - a^nb^nUm-n 、 Vm+n = VmVn - a^nb^nVm-n

Um+1 = P*Um - Q*Um-1 、 Vm+1 = P*Vm - Q*Vm-1 (取 n = 1)

U2n = UnVn 、 V2n = Vn2 - 2*Qn

U2n+1 = Un+1Vn - Qn 、 V2n+1 = Vn+1Vn - PQn

若取 (P,Q) = (1,-1)，我們便有 Un 為斐波那契數，

即 0、 1、 1、 2、 3、 5、 8、 13、 21、 34、 55、 89、 144、 233、 377、 610、 987、 1597、 2584、 4181、 6765等。

而 Vn 為盧卡斯數 (Lucas Number)，

即 2、 1、 3、 4、 7、 11、18、 29、 47、 76、 123、 199、 322、 521、 843、 1364、 2207、 3571、 5778、 9349 等。

若取 (P,Q) = (2,-1)，我們便有 Un 為佩爾數 (Pell Number)，

即 0、 1、 2、 5、 12、 29、 70、 169、 408、 985、 2378、 5741等。

而 Vn 為佩爾 - 盧卡斯數 (Pell - Lucas Number) (詳見另文《佩爾數列》)，

即 2、 2、 6、 14、 34、 82、 198、 478、 1154、 2786、 6726等。

此等全都是數學界很有名的數列。

數列性質

盧卡斯數 (簡記 Ln) 有很多性質和斐波那契數很相似。如 Ln = Ln-1 + Ln-2，其中不同的是 L1 = 1、 L2 = 3。

所以盧卡斯數有：1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...... (OEIS A000204)，當中的平方數只有 1 和 4，這是由哥恩 (John H. E. Cohn) 證明的。而素數，即盧卡斯素數 (Lucas Prime) 則有： 3, 7, 11, 29, 47, ...... 。當中現在知道最大的擬素數 (Probable Prime) 為 L574219 ，此數達 120005位之多。

我們有下列和盧卡斯數相關的恆等式：

Ln2 - Ln-1Ln+1 = 5 (-1)n

L12 + L22 + ...... + Ln2 = LnLn+1 - 2

Lm+n = (5FmFn + LmLn) / 2 (式中的 Fn 為斐波那契數)

Lm-n = (-1)n (LmLn - 5FmFn) / 2

Ln2 - 5Fn2 = 4 (-1)n

龍虎榜

n 數位 發現者 年份

56003 11704歐文(Sean A. Irvine) /禾達(Bouk de Water) 2006

51169 10694 禾達 (Bouk de Water) / 布靴斯特 (David Broadhurst)

2001

44507 9302 禾達 (Bouk de Water) / 布靴斯特 (David Broadhurst) /倫斯(John Renze) 2005

36779 7687 禾達 (Bouk de Water) / 布靴斯特 (David Broadhurst) / 倫斯 (John Renze) 2005

35449 7409 禾達 (Bouk de Water) 2001

19469 4069 禾達 (Bouk de Water) / 布靴斯特 (David Broadhurst) 2002

19449 3020 都伯納 (Harvey Dubner) / 凱勒 (Wilfrid Keller) 1995

13963 2919奧基斯(Mike Oakes) 2002

12251 2561 禾達 (Bouk de Water) / 布靴斯特 (David Broadhurst) 2001

10691 2235 都伯納 (Harvey Dubner) / 凱勒 (Wilfrid Keller) 1995

若我們考慮的是擬素數，即那些通過費馬小定理(Fermat's Little Theorem) 逆命題測試的數，這有很大機會是素數，或可能是卡麥可數 (Carmichael Number)。那我們可把 n 推至 202667。但正因為 n 很大，要判斷該數的素性的確不易。

參考資料

Caldwell, C. K. "The Top Twenty: Lucas Number."

Ribenboim, P. "The Little Book of Bigger Prime" , New York: Springer-Verlag, 1991

Weisstein, E. W. "Lucas Number." From MathWorld.

前50項

#include <stdio.h>

#ifdef _WIN32

#define i64 __int64

#define format "%I64d\n"

#else

#define i64 long long

#define format "%lld\n"

#endif

int main(int argc, char **argv)

{

i64 ARRAY[50];

int i;

ARRAY[0] = 2;

ARRAY[1] = 1;

printf(format,ARRAY[0]);

printf(format,ARRAY[1]);

for(i = 2;i < 50;i ++)

{

ARRAY[i] = ARRAY[i-1] + ARRAY[i-2];

printf(format,ARRAY[i]);

}

return 0;

}