This site is supported by donations to The OEIS Foundation.

Lucas sequences

From OeisWiki
Jump to: navigation, search

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

There exist two kinds of Lucas sequences:

  • Sequences with
,
  • Sequences with
,

where

are the solutions of the quadratic equation

.

Properties

  • The variables and , and the parameter and are interdependent. In particular, and .
  • For every sequence it holds that and .
  • For every sequence is holds that and .

For every Lucas sequence the following are true:

  • for all

Recurrence relation

The Lucas sequences and are defined by the recurrence relations

and

Fibonacci numbers and Lucas numbers

The two best known Lucas sequences are the Fibonacci numbers and the Lucas numbers with and .

Lucas sequences and the prime numbers

If the natural number is a prime number then it holds that

  • divides
  • divides

Fermat's little theorem can then be seen as a special case of divides because is equivalent to .

The converse pair of statements that if divides then is a prime number and if divides then is a prime number) are individually false and lead to Fibonacci pseudoprimes and Lucas pseudoprimes, respectively.

Sequences

Sequences are ordered by increasing , then subordered by decreasing , since

and

.
Lucas sequences

and

Description OEIS

number

Sequence

or

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, ...}
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, ...}
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, ...}
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, ...}
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, ...}
A075118 {2, 1, 7, 10, 31, 61, 154, 337, 799, 1810, 4207, 9637, 22258, 51169, 117943, 271450, 625279, 1439629, 3315466, 7634353, 17580751, 40483810, ...}
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, ...}
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, ...}
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, ...}
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, ...}
A015528 {0, 1, 3, 19, 87, 451, 2223, 11179, 55767, 279091, 1394943, 6975739, 34876647, 174387331, 871928463, 4359658699, 21798260727, 108991369171, ...}
A?????? {2, 3, 29, ...}
A015529 {0, 1, 3, 20, 93, 499, 2520, 13049, 66867, 344140, 1767957, 9089411, 46715760, 240130801, 1234265763, 6344236100, 32609631693, 167615492179, ...}
A?????? {2, 3, 31, ...}
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, ...}
A034472 {2, 4, 10, 28, 82, 244, 730, 2188, 6562, 19684, 59050, 177148, 531442, 1594324, 4782970, 14348908, 43046722, 129140164, 387420490, 1162261468, ...}
A015530 {0, 1, 4, 19, 88, 409, 1900, 8827, 41008, 190513, 885076, 4111843, 19102600, 88745929, 412291516, 1915403851, 8898489952, 41340171361, ...}
A?????? {2, 4, 22, ...}
A015531 {0, 1, 4, 21, 104, 521, 2604, 13021, 65104, 325521, 1627604, 8138021, 40690104, 203450521, 1017252604, 5086263021, 25431315104, 127156575521, ...}
A?????? {2, 4, 26, ...}
Repunits base 4 A002450 {0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, 1398101, 5592405, 22369621, 89478485, 357913941, 1431655765, 5726623061, 22906492245, ...}
A052539 {2, 5, 17, 65, 257, 1025, 4097, 16385, 65537, 262145, 1048577, 4194305, 16777217, 67108865, 268435457, 1073741825, 4294967297, 17179869185, ...}
A015540 {0, 1, 5, 31, 185, 1111, 6665, 39991, 239945, 1439671, 8638025, 51828151, 310968905, 1865813431, 11194880585, 67169283511, 403015701065, ...}
A?????? {2, 5, 37, ...}
Repunits base 5 A003463 {0, 1, 6, 31, 156, 781, 3906, 19531, 97656, 488281, 2441406, 12207031, 61035156, 305175781, 1525878906, 7629394531, 38146972656, 190734863281, ...}
A034474 {2, 6, 26, 126, 626, 3126, 15626, 78126, 390626, 1953126, 9765626, 48828126, 244140626, 1220703126, 6103515626, 30517578126, 152587890626, ...}
Repunits base 6 A003464(n)
n ≥ 1
{0, 1, 7, 43, 259, 1555, 9331, 55987, 335923, 2015539, 12093235, 72559411, 435356467, 2612138803, 15672832819, 94036996915, 564221981491, ...}
A062394 {2, 7, 37, 217, 1297, 7777, 46657, 279937, 1679617, 10077697, 60466177, 362797057, 2176782337, 13060694017, 78364164097, 470184984577, ...}
Repunits base 7 A023000 {0, 1, 8, 57, 400, 2801, 19608, 137257, 960800, 6725601, 47079208, 329554457, 2306881200, 16148168401, 113037178808, 791260251657, 5538821761600, ...}
A034491 {2, 8, 50, 344, 2402, 16808, 117650, 823544, 5764802, 40353608, 282475250, 1977326744, 13841287202, 96889010408, 678223072850, 4747561509944, ...}
A015577 {0, 1, 8, 73, 656, 5905, 53144, 478297, 4304672, 38742049, 348678440, 3138105961, 28242953648, 254186582833, 2287679245496, 20589113209465, ...}
A?????? {2, 8, 82, ...}
Repunits base 8 A023001 {0, 1, 9, 73, 585, 4681, 37449, 299593, 2396745, 19173961, 153391689, 1227133513, 9817068105, 78536544841, 628292358729, 5026338869833, ...}
A062395 {2, 9, 65, 513, 4097, 32769, 262145, 2097153, 16777217, 134217729, 1073741825, 8589934593, 68719476737, 549755813889, 4398046511105, ...}
Repunits base 9 A002452(n)
n ≥ 1
{0, 1, 10, 91, 820, 7381, 66430, 597871, 5380840, 48427561, 435848050, 3922632451, 35303692060, 317733228541, 2859599056870, 25736391511831, ...}
A062396 {2, 10, 82, 730, 6562, 59050, 531442, 4782970, 43046722, 387420490, 3486784402, 31381059610, 282429536482, 2541865828330, 22876792454962, ...}
Repunits base 10 A002275 {0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111, 1111111111111, 11111111111111, 111111111111111, ...}
A062397 {2, 11, 101, 1001, 10001, 100001, 1000001, 10000001, 100000001, 1000000001, 10000000001, 100000000001, 1000000000001, 10000000000001, ...}
Repunits base 11 A016123(n-1)
n ≥ 1
{0, 1, 12, 133, 1464, 16105, 177156, 1948717, 21435888, 235794769, 2593742460, 28531167061, 313842837672, 3452271214393, 37974983358324, ...}
A034524 {2, 12, 122, 1332, 14642, 161052, 1771562, 19487172, 214358882, 2357947692, 25937424602, 285311670612, 3138428376722, 34522712143932, ...}
Repunits base 12 A016125(n-1)
n ≥ 1
{0, 1, 13, 157, 1885, 22621, 271453, 3257437, 39089245, 469070941, 5628851293, 67546215517, 810554586205, 9726655034461, 116719860413533, ...}
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.