Lucas sequences

A Lucas sequence is a particular generalization of sequences like the Fibonacci numbers, Lucas numbers, Pell numbers or Jacobsthal numbers. Lucas sequences have one common characteristic: they can be generated over quadratic equations of the form

$x^{2}-Px+Q=0,\ P^{2}-4Q\neq 0.\,$

There exist two kinds of Lucas sequences:

• Sequences $\scriptstyle U(P,Q)\,=\,\{U_{n}(P,Q)\}_{n\geq 0}$ with

$U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}$,

• Sequences $\scriptstyle V(P,Q)\,=\,\{V_{n}(P,Q)\}_{n\geq 0}$ with

$V_{n}(P,Q)=a^{n}+b^{n}\$,

where

$a={\frac {P+{\sqrt {P^{2}-4Q}}}{2}},\ b={\frac {P-{\sqrt {P^{2}-4Q}}}{2}}$

are the solutions of the quadratic equation

$x^{2}-Px+Q=0\,$.

Properties

• The variables $\scriptstyle a\$ and $\scriptstyle b\$, and the parameter $\scriptstyle P\$ and $\scriptstyle Q\$ are interdependent. In particular, $\scriptstyle P=a+b\$ and $\scriptstyle Q=a\cdot b.$.
• For every sequence $\scriptstyle U(P,Q)=(U_{n}(P,Q))_{n\geq 0}$ it holds that $\scriptstyle U_{0}=0\$ and $U_{1}=1$.
• For every sequence $\scriptstyle V(P,Q)=(V_{n}(P,Q))_{n\geq 0}$ is holds that $\scriptstyle V_{0}=2\$ and $V_{1}=P$.

For every Lucas sequence the following are true:

• $\scriptstyle U_{2n}=U_{n}\cdot V_{n}\$
• $\scriptstyle V_{n}=U_{n+1}-QU_{n-1}\$
• $\scriptstyle V_{2n}=V_{n}^{2}-2Q^{n}\$
• $\scriptstyle \operatorname {gcd} (U_{m},U_{n})=U_{\operatorname {gcd} (m,n)}$
• $\scriptstyle m\mid n\implies U_{m}\mid U_{n}$ for all $\scriptstyle U_{m}\neq 1$

Recurrence relation

The Lucas sequences $\scriptstyle U(P,Q)\,$ and $\scriptstyle V(P,Q)\,$ are defined by the recurrence relations

$U_{0}(P,Q)=0\,$

$U_{1}(P,Q)=1\,$

$U_{n}(P,Q)=PU_{n-1}(P,Q)-QU_{n-2}(P,Q){\mbox{ for }}n>1\,$

and

$V_{0}(P,Q)=2\,$

$V_{1}(P,Q)=P\,$

$V_{n}(P,Q)=PV_{n-1}(P,Q)-QV_{n-2}(P,Q){\mbox{ for }}n>1\,$

Fibonacci numbers and Lucas numbers

The two best known Lucas sequences are the Fibonacci numbers $\scriptstyle U(1,-1)\$ and the Lucas numbers $\scriptstyle V(1,-1)\$ with $\scriptstyle a={\frac {1+{\sqrt {5}}}{2}}$ and $\scriptstyle b={\frac {1-{\sqrt {5}}}{2}}$.

Lucas sequences and the prime numbers

If the natural number $\scriptstyle p\$ is a prime number then it holds that

• $\scriptstyle p\$ divides $\scriptstyle U_{p}(P,Q)-\left({\frac {D}{p}}\right)$
• $\scriptstyle p\$ divides $\scriptstyle V_{p}(P,Q)-P\$

Fermat's little theorem can then be seen as a special case of $\scriptstyle p\$ divides $\scriptstyle (V_{n}(P,Q)-P)\$ because $\scriptstyle a^{p}\equiv a{\pmod {p}}$ is equivalent to $\scriptstyle V_{p}(a+1,a)\equiv V_{1}(a+1,a){\pmod {p}}$.

The converse pair of statements that if $\scriptstyle n\$ divides $\scriptstyle U_{n}(P,Q)-\left({\frac {D}{n}}\right)$ then is $\scriptstyle n\$ a prime number and if $m\$ divides $\scriptstyle V_{m}(P,Q)-P\$ then is $m\$ a prime number) are individually false and lead to Fibonacci pseudoprimes and Lucas pseudoprimes, respectively.

Sequences

Sequences are ordered by increasing $\scriptstyle P\,$, then subordered by decreasing $\scriptstyle Q\,$, since

$\{U_{n}(P,Q)\}_{n\geq 0}=\{0,1,P,P^{2}-Q,...\}\,$

and

$\{V_{n}(P,Q)\}_{n\geq 0}=\{2,P,P^{2}-2Q,...\}\,$.

Lucas sequences

$U(P,Q)\,$ and $V(P,Q)\,$	Description	OEIS number	Sequence $\{U_{n}(P,Q)\}_{n\geq 0}\,$ or $\{V_{n}(P,Q)\}_{n\geq 0}\,$
$\scriptstyle U(1,-1)\,$	Fibonacci numbers	A000045	{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, ...}
$\scriptstyle V(1,-1)\,$	Lucas numbers	A000032	{2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, ...}
$\scriptstyle U(1,-2)\,$	Jacobthal numbers	A001045	{0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101, 2796203, 5592405, ...}
$\scriptstyle V(1,-2)\,$	Jacobsthal-Lucas numbers	A014551	{2, 1, 5, 7, 17, 31, 65, 127, 257, 511, 1025, 2047, 4097, 8191, 16385, 32767, 65537, 131071, 262145, 524287, 1048577, 2097151, 4194305, ...}
$\scriptstyle U(1,-3)\,$		A006130(n-1) n ≥ 1	{0, 1, 1, 4, 7, 19, 40, 97, 217, 508, 1159, 2683, 6160, 14209, 32689, 75316, 173383, 399331, 919480, 2117473, 4875913, 11228332, 25856071, 59541067, ...}
$\scriptstyle V(1,-3)\,$		A075118	{2, 1, 7, 10, 31, 61, 154, 337, 799, 1810, 4207, 9637, 22258, 51169, 117943, 271450, 625279, 1439629, 3315466, 7634353, 17580751, 40483810, ...}
$\scriptstyle U(2,-1)\,$	Pell numbers	A000129	{0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, 80782, 195025, 470832, 1136689, 2744210, 6625109, 15994428, 38613965, 93222358, ...}
$\scriptstyle V(2,-1)\,$	Pell-Lucas numbers	A002203	{2, 2, 6, 14, 34, 82, 198, 478, 1154, 2786, 6726, 16238, 39202, 94642, 228486, 551614, 1331714, 3215042, 7761798, 18738638, 45239074, 109216786, ...}
$\scriptstyle U(3,2)\,$	Repunits base 2	A000225	{0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, ...}
$\scriptstyle V(3,2)\,$	$\scriptstyle 2^{n}+1\,$	A000051	{2, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8193, 16385, 32769, 65537, 131073, 262145, 524289, 1048577, 2097153, 4194305, 8388609, ...}
$\scriptstyle U(3,-10)\,$		A015528	{0, 1, 3, 19, 87, 451, 2223, 11179, 55767, 279091, 1394943, 6975739, 34876647, 174387331, 871928463, 4359658699, 21798260727, 108991369171, ...}
$\scriptstyle V(3,-10)\,$		A??????	{2, 3, 29, ...}
$\scriptstyle U(3,-11)\,$		A015529	{0, 1, 3, 20, 93, 499, 2520, 13049, 66867, 344140, 1767957, 9089411, 46715760, 240130801, 1234265763, 6344236100, 32609631693, 167615492179, ...}
$\scriptstyle V(3,-11)\,$		A??????	{2, 3, 31, ...}
$\scriptstyle U(4,3)\,$	Repunits base 3	A003462	{0, 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 1743392200, ...}
$\scriptstyle V(4,3)\,$	$\scriptstyle 3^{n}+1\,$	A034472	{2, 4, 10, 28, 82, 244, 730, 2188, 6562, 19684, 59050, 177148, 531442, 1594324, 4782970, 14348908, 43046722, 129140164, 387420490, 1162261468, ...}
$\scriptstyle U(4,-3)\,$		A015530	{0, 1, 4, 19, 88, 409, 1900, 8827, 41008, 190513, 885076, 4111843, 19102600, 88745929, 412291516, 1915403851, 8898489952, 41340171361, ...}
$\scriptstyle V(4,-3)\,$		A??????	{2, 4, 22, ...}
$\scriptstyle U(4,-5)\,$		A015531	{0, 1, 4, 21, 104, 521, 2604, 13021, 65104, 325521, 1627604, 8138021, 40690104, 203450521, 1017252604, 5086263021, 25431315104, 127156575521, ...}
$\scriptstyle V(4,-5)\,$		A??????	{2, 4, 26, ...}
$\scriptstyle U(5,4)\,$	Repunits base 4	A002450	{0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, 1398101, 5592405, 22369621, 89478485, 357913941, 1431655765, 5726623061, 22906492245, ...}
$\scriptstyle V(5,4)\,$	$\scriptstyle 4^{n}+1\,$	A052539	{2, 5, 17, 65, 257, 1025, 4097, 16385, 65537, 262145, 1048577, 4194305, 16777217, 67108865, 268435457, 1073741825, 4294967297, 17179869185, ...}
$\scriptstyle U(5,-6)\,$		A015540	{0, 1, 5, 31, 185, 1111, 6665, 39991, 239945, 1439671, 8638025, 51828151, 310968905, 1865813431, 11194880585, 67169283511, 403015701065, ...}
$\scriptstyle V(5,-6)\,$		A??????	{2, 5, 37, ...}
$\scriptstyle U(6,5)\,$	Repunits base 5	A003463	{0, 1, 6, 31, 156, 781, 3906, 19531, 97656, 488281, 2441406, 12207031, 61035156, 305175781, 1525878906, 7629394531, 38146972656, 190734863281, ...}
$\scriptstyle V(6,5)\,$	$\scriptstyle 5^{n}+1\,$	A034474	{2, 6, 26, 126, 626, 3126, 15626, 78126, 390626, 1953126, 9765626, 48828126, 244140626, 1220703126, 6103515626, 30517578126, 152587890626, ...}
$\scriptstyle U(7,6)\,$	Repunits base 6	A003464(n) n ≥ 1	{0, 1, 7, 43, 259, 1555, 9331, 55987, 335923, 2015539, 12093235, 72559411, 435356467, 2612138803, 15672832819, 94036996915, 564221981491, ...}
$\scriptstyle V(7,6)\,$	$\scriptstyle 6^{n}+1\,$	A062394	{2, 7, 37, 217, 1297, 7777, 46657, 279937, 1679617, 10077697, 60466177, 362797057, 2176782337, 13060694017, 78364164097, 470184984577, ...}
$\scriptstyle U(8,7)\,$	Repunits base 7	A023000	{0, 1, 8, 57, 400, 2801, 19608, 137257, 960800, 6725601, 47079208, 329554457, 2306881200, 16148168401, 113037178808, 791260251657, 5538821761600, ...}
$\scriptstyle V(8,7)\,$	$\scriptstyle 7^{n}+1\,$	A034491	{2, 8, 50, 344, 2402, 16808, 117650, 823544, 5764802, 40353608, 282475250, 1977326744, 13841287202, 96889010408, 678223072850, 4747561509944, ...}
$\scriptstyle U(8,-9)\,$		A015577	{0, 1, 8, 73, 656, 5905, 53144, 478297, 4304672, 38742049, 348678440, 3138105961, 28242953648, 254186582833, 2287679245496, 20589113209465, ...}
$\scriptstyle V(8,-9)\,$		A??????	{2, 8, 82, ...}
$\scriptstyle U(9,8)\,$	Repunits base 8	A023001	{0, 1, 9, 73, 585, 4681, 37449, 299593, 2396745, 19173961, 153391689, 1227133513, 9817068105, 78536544841, 628292358729, 5026338869833, ...}
$\scriptstyle V(9,8)\,$	$\scriptstyle 8^{n}+1\,$	A062395	{2, 9, 65, 513, 4097, 32769, 262145, 2097153, 16777217, 134217729, 1073741825, 8589934593, 68719476737, 549755813889, 4398046511105, ...}
$\scriptstyle U(10,9)\,$	Repunits base 9	A002452(n) n ≥ 1	{0, 1, 10, 91, 820, 7381, 66430, 597871, 5380840, 48427561, 435848050, 3922632451, 35303692060, 317733228541, 2859599056870, 25736391511831, ...}
$\scriptstyle V(10,9)\,$	$\scriptstyle 9^{n}+1\,$	A062396	{2, 10, 82, 730, 6562, 59050, 531442, 4782970, 43046722, 387420490, 3486784402, 31381059610, 282429536482, 2541865828330, 22876792454962, ...}
$\scriptstyle U(11,10)\,$	Repunits base 10	A002275	{0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111, 1111111111111, 11111111111111, 111111111111111, ...}
$\scriptstyle V(11,10)\,$	$\scriptstyle {10}^{n}+1\,$	A062397	{2, 11, 101, 1001, 10001, 100001, 1000001, 10000001, 100000001, 1000000001, 10000000001, 100000000001, 1000000000001, 10000000000001, ...}
$\scriptstyle U(12,11)\,$	Repunits base 11	A016123(n-1) n ≥ 1	{0, 1, 12, 133, 1464, 16105, 177156, 1948717, 21435888, 235794769, 2593742460, 28531167061, 313842837672, 3452271214393, 37974983358324, ...}
$\scriptstyle V(12,11)\,$	$\scriptstyle {11}^{n}+1\,$	A034524	{2, 12, 122, 1332, 14642, 161052, 1771562, 19487172, 214358882, 2357947692, 25937424602, 285311670612, 3138428376722, 34522712143932, ...}
$\scriptstyle U(13,12)\,$	Repunits base 12	A016125(n-1) n ≥ 1	{0, 1, 13, 157, 1885, 22621, 271453, 3257437, 39089245, 469070941, 5628851293, 67546215517, 810554586205, 9726655034461, 116719860413533, ...}
$\scriptstyle V(13,12)\,$	$\scriptstyle {12}^{n}+1\,$	Axxxxxx	{2, 13, 1729, 20737, ...}

References

• P. Ribenboim, The New Book of Prime Number Records (3 ed.), Springer, 1996, ISBN 0-387-94457-5.
• P. Ribenboim, My Numbers, My Friends, Springer, 2000, ISBN 0-387-98911-0.