独角兽高达价格:斐波拉契数列&卢卡斯数列

斐波拉契数列&卢卡斯数列2011-03-13 16:39 费波拿契数:

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

　　卢卡斯数 (Lucas Number):

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

　　佩尔数 (Pell Number):

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

　　佩尔 - 卢卡斯数 (Pell - Lucas Number):

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

　　此等全都是数学界很有名的数列。

 

斐波拉契数列

斐波拉契数列的简介

　　斐波拉契数列（又译作“斐波那契数列”或“斐波那切数列”）是一个非常美丽、和谐的数列，它的形状可以用排成螺旋状的一系列正方形来说明（如右词条图），起始的正方形(图中用灰色表示)的边长为1，在它左边的那个正方形的边长也是1 ，在这两个正方形的上方再放一个正方形，其边长为2，以后顺次加上边长为3、5、8、13、21……等等的正方形。这些数字每一个都等于前面两个数之和，它们正好构成了斐波那契数列。“斐波那契数列”的发明者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci，生于公元1170年，卒于1240年。籍贯大概是比萨）。他被人称作“比萨的列昂纳多”。1202年，他撰写了《珠算原理》(Liber Abaci)一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点相当于今日的阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯研究数学。

　　斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34……

　　这个数列从第三项开始，每一项都等于前两项之和。它的通项公式为：(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}　(√5表示5的算术平方根)　(19世纪法国数学家敏聂(Jacques Phillipe Marie Binet 1786-1856)

　　很有趣的是：这样一个完全是自然数的数列，通项公式居然是用无理数来表达的。

　　斐波拉契数列之闻名，可能还跟美国悬疑作家丹·布朗有关，他在他的小说《达芬奇密码》之中巧妙地运用了该数列。

　　其实，我国现行的高中教材中提及了杨辉三角，斐波拉契数列可在其中寻得。

　　■斐波拉契数列的出现

　　13世纪初，欧洲最好的数学家是斐波拉契；他写了一本叫做《算盘书》的著作，是当时欧洲最好的数学书。书中有许多有趣的数学题，其中最有趣的是下面这个题目：

　　“如果一对兔子每月能生1对小兔子，而每对小兔在它出生后的第3个月裏，又能开始生1对小兔子，假定在不发生死亡的情况下，由1对初生的兔子开始，1年后能繁殖成多少对兔子？”

　　斐波拉契把推算得到的头几个数摆成一串：1，1，2，3，5，8……

　　这串数里隐含着一个规律：从第3个数起，后面的每个数都是它前面那两个数的和。而根据这个规律，只要作一些简单的加法，就能推算出以后各个月兔子的数目了。

　　于是，按照这个规律推算出来的数，构成了数学史上一个有名的数列。大家都叫它“斐波拉契数列”，又称“兔子数列”。这个数列有许多奇特的的性质，例如，从第3个数起，每个数与它后面那个数的比值，都很接近于0.618，正好与大名鼎鼎的“黄金分割律”相吻合。人们还发现，连一些生物的生长规律，在某种假定下也可由这个数列来刻画呢。

　　斐氏本人对这个数列并没有再做进一步的探讨。直到十九世纪初才有人详加研究，1960年左右，许多数学家对斐波拉契数列和有关的现象非常感到兴趣，不但成立了斐氏学会，还创办了相关刊物，其后各种相关文章也像斐氏的兔子一样迅速地增加。

　　■斐波拉契数列的来源及关系

　　斐波拉契（Fibonacci）数列来源于兔子问题，它有一个递推关系，

　　f(1)=1

　　f(2)=1

　　f(n)=f(n-1)+f(n-2),其中n>=2

　　{f(n)}即为斐波拉契数列。

　　■斐波拉契数列的公式

　　它的通项公式为:{[（1＋√5）/2]^n － [（1－√5）/2]^n }/√5 （注：√5表示根号5）

　　■斐波拉契数列的某些性质

　　1)，f(n)f(n)-f(n+1)f(n-1)=(-1)^n;

　　2), f(1)+f(2)+f(3)+……+f(n)=f(n+2)-1

　　3),arctan[1/f(2n+1)]=arctan[1/f(2n+2)]+arctan[1/f(2n+3)]

【斐波拉契数列的存在】     甚至可以说，斐波拉契数列无处不在，以下仅举几条常见的例子：
　　1．杨辉三角对角线上各数之和构成斐波拉契数列 ．
　　2．多米诺牌（可以看作一个2×1大小的方格）完全覆盖一个n×2的棋盘，覆盖的方案数等于斐波拉契数列。
　　3． 从蜜蜂的繁殖来看，雄峰只有母亲，没有父亲，因为蜂后产的卵，受精的孵化为雌蜂，未受精的孵化为雄峰。人们在追溯雄峰的祖先时，发现一只雄峰的第n代祖先的数目刚好就是斐波拉契数列的第n项Fn。
　　4．钢琴的13个半音阶的排列完全与雄峰第六代的排列情况类似，说明音调也与斐波拉契数列有关。
　　5．自然界中一些花朵的花瓣数目符合于斐波拉契数列，也就是说在大多数情况下，一朵花花瓣的数目都是3,5,8,13,21,34,……(有6枚是两套3枚;有4枚可能是基因突变)。
　　6．如果一根树枝每年长出一根新枝，而长出的新枝两年以后，每年也长出一根新枝，那么历年的树枝数，也构成一个斐波拉契数列 ．

【斐波拉契数列与黄金分割】

　　斐波拉契数列与黄金分割有什么关系呢？经研究发现，相邻两个斐波拉契数的比值是随序号的增加而逐渐趋于黄金分割比的。即f(n-1)/f(n)-→0.618…。由于斐波拉契数都是整数，两个整数相除之商是有理数，所以只是逐渐逼近黄金分割比这个无理数。但是当我们继续计算出后面更大的斐波拉契数时，就会发现相邻两数之比确实是非常接近黄金分割比的。
　　不仅这个由1,1,2,3,5....开始的"斐波拉契数"是这样,随便选两个整数,然后按照斐波拉契数的规律排下去,两数间比也是会逐渐逼近黄金比的．
　　

帕多瓦数列的三角形

【斐波拉契数列的变式】■１.帕多瓦数列：1，1，1，2，2，3，4，5，7，9，12，16，21，……这样的数列称为帕多瓦数列。它和斐波拉契数列非常相似，稍有不同的是：每个数都是跳过它前面的那个数，并把再前面的两个数相加而得出的。这个数列可以用另一幅图来表示，它是由一些等边三角形构成的(如右图)。开始的三角形用灰色表示，为了使这些三角形天衣无缝地拼在一起，头三个三角形的边长均为1，其后的两个三角形的边长为2，然后依次是3、4、5、7、9、12、16、2l……等等。
　　■２.冬冬有15块糖，如果每天至少吃3块，吃完为止，那么共有多少种不同的吃法？
　　如果冬冬有3块糖、4块糖或者5块糖，都只有1种吃法；如果有6块糖，则有2种吃法；如果有7块糖，则有3种吃法；如果有8块糖，则有4种吃法；如果有9块糖，则有6种吃法．
　　既：吃糖的粒数：３　４　５　６　７　８　９　１０　１１　１２．．．
　　糖的吃法：１　１　１　２　３　４　６　９ １３　１９．．．
　　这样的数列，它和斐波拉契数列不同的是，每次都是跳过中间的那个数，再把第1、3两个数相加，等于第4个数。它的规律和斐波拉契数列既相似之处又有不同之处．
　　■３.小明要上楼梯，他每次能向上走一级、两级或三级，如果楼梯有10级，他有几种不同的走法？
　　这里我们不妨也来研究一下其中的规律：如果楼梯就一级，他有1种走法；如果楼梯有两级，他有2种走法；如果楼梯有三级，他有4种走法；如果有五级楼梯，他有7种走法．
　　既：楼梯的级数：１　２　３　４　５　６　７　８ ．．．
　　上楼梯的走法：１　２　４　７　１３　２４　４４　８１．．．
　　这其中的规律就是，这里从第4个数开始，每一个数都等于它前面的3个数之和。 【该数列有很多奇妙的属性】 　　比如：随着数列项数的增加，前一项与后一项之比越逼近黄金分割0.6180339887…… (后一项与前一项之比1.6180339887…… )
　　还有一项性质，从第二项开始，每个奇数项的平方都比前后两项之积多1，每个偶数项的平方都比前后两项之积少1。
　　如果你看到有这样一个题目：某人把一个8*8的方格切成四块，拼成一个5*13的长方形，故作惊讶地问你：为什么64＝65？其实就是利用了斐波那契数列的这个性质：5、8、13正是数列中相邻的三项，事实上前后两块的面积确实差1，只不过后面那个图中有一条细长的狭缝，一般人不容易注意到。
　　如果任意挑两个数为起始，比如5、-2.4，然后两项两项地相加下去，形成5、-2.4、2.6、0.2、2.8、3、5.8、8.8、14.6……等，你将发现随着数列的发展，前后两项之比也越来越逼近黄金分割，且某一项的平方与前后两项之积的差值也交替相差某个值。
　　斐波那契数列的第n项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数的子集个数。 　斐波那契数列（f(n)，f(0)=0，f(1)=1，f(2)=1，f(3)=2……）的其他性质：
　　1.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1
　　2.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)
　　3.f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1
　　4.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1)
　　5.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1
　　6.f(m+n)=f(m-1)·f(n-1)+f(m)·f(n)
　　利用这一点，可以用程序编出时间复杂度仅为O（log n）的程序。
　　7.[f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1)
　　8.f(2n-1)=[f(n)]^2-[f(n-2)]^2
　　9.3f(n)=f(n+2)+f(n-2)
　　10.f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1]  

斐波那契数列

        【斐波那契数列别名】   　　斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。
　　一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？
　　我们不妨拿新出生的一对小兔子分析一下：
　　第一个月小兔子没有繁殖能力，所以还是一对;
　　两个月后，生下一对小兔民数共有两对;
　　三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对;
　　－－－－－－
　　依次类推可以列出下表：
　　经过月数：0 1 2 3 4 5 6 7 8 9 10 11 12
　　兔子对数：1 1 2 3 5 8 13 21 34 55 89 144 233
　　表中数字1，1，2，3，5，8－－－构成了一个数列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。
　　这个数列是意大利中世纪数学家斐波那契在＜算盘全书＞中提出的，这个级数的通项公式，除了具有a(n+2)=an+a(n+1)/的性质外，还可以证明通项公式为：an=1/√[（1＋√5/2) n-(1-√5/2) n](n=1,2,3.....）  

卢卡斯数列

    卢卡斯数列 (Lucas Sequence) 和费波拿契数列 (Fibonnacci Sequence) 有莫大的关系。

　　先定义整数 P 和 Q 使 D = P2 - 4Q > 0，

　　从而得一方程 x2 - Px + Q = 0，其根为 a, b，

　　现定义卢卡斯数列为：

　　Un(P,Q) = (an - bn) / (a-b) 及 Vn(P,Q) = an + bn

　　其中 n 为非负整数，得 U0(P,Q) = 0、 U1(P,Q) = 1 、 V0(P,Q) = 2 、 V1(P,Q) = P、......

　　我们有下列和卢卡斯数列相关的恒等式：

　　Um+n = UmVn - anbnUm-n 、 Vm+n = VmVn - anbnVm-n

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

　　U2n = UnVn 、 V2n = Vn2 - 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、 4141、 6765等。

　　而 Vn 为卢卡斯数 (Lucas Number)，

　　即 2、 1、 3、 4、 7、 11、18、 29、 47、 76、 123、 199、 322、 521、 843、 1364、 2207、 3571、 5781、 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 很大，要判断该数的素性的确不易。

 

http://chensmiles.blog.163.com/blog/static/121463991200991785940935/