Lucasův řetěz - Lucas chain

v matematika, a Lucasův řetěz je omezený typ přídavný řetězec, pojmenovaný pro francouzského matematika Édouard Lucas. Je to sekvence

A₀, A₁, A₂, A₃, ...

to uspokojuje

A₀=1,

a

pro každého k > 0: A_k = A_i + A_j, a buď A_i = A_j nebo |A_i − A_j| = A_m, pro některé i, j, m < k.^[1][2]

Posloupnost sil 2 (1, 2, 4, 8, 16, ...) a Fibonacciho sekvence (s mírnou úpravou počátečního bodu 1, 2, 3, 5, 8, ...) jsou jednoduché příklady řetězů Lucas.

Lucasovy řetězy představil Peter Montgomery v roce 1983.^[3] Li L(n) je délka nejkratšího Lucasova řetězce pro n, pak to Kutz ukázal nejvíce n nemít L <(1-ε) log_φ n, kde φ je Zlatý řez.^[1]

Reference

• Guy, Richard K. (2004). Nevyřešené problémy v teorii čísel (3. vyd.). Springer-Verlag. 169–171. ISBN  978-0-387-20860-2. Zbl  1058.11001.
• Kutz, Martin (2002). „Dolní hranice pro Lucasovy řetězy“ (PDF). SIAM J. Comput. 31 (6): 1896–1908. doi:10.1137 / s0097539700379255. Zbl  1055.11077.
• Montgomery, Peter L. (1983). "Hodnocení opakování formy X_{m + n} = f (X_m, X_n, X_m-n) Via Lucas Chains “ (PS). Nepublikovaný.