ルーカスチェーン

数学において、ルーカス連鎖はフランスの数学者エドゥアール・ルーカスにちなんで名付けられた、制限されたタイプの加算連鎖である。これは、

0、1、2、3 _、 ..._​​​

満足する

0 =1 _、

そして

各k > 0に対して、a _k = a _i + a _jであり、 a _i = a _jまたは| a _i − a _j | = a _m （ i、j、m < k）のいずれかである。^{[1] [2]}

2 の累乗の数列 (1、2、4、8、16、...) とフィボナッチ数列(開始点をわずかに調整した 1、2、3、5、8、...) は、ルーカス連鎖の簡単な例です。

ルーカス連鎖は1983年にピーター・モンゴメリーによって導入されました。 ^[3] L ( n )がnに対する最短ルーカス連鎖の長さである 場合、ほとんどのnはL <(1-ε)logφn_を 満たさないことをクッツは示しました。ここでφは黄金比です。^[1]

• ガイ、リチャード K. (2004)。数論における未解決問題(第 3 版)。Springer -Verlag。pp . 169–171。ISBN 978-0-387-20860-2.ZBL1058.11001  。​
• Kutz, Martin (2002). 「Lucas 連鎖の下限値」(PDF) . SIAM J. Comput . 31 (6): 1896–1908. doi :10.1137/s0097539700379255. Zbl  1055.11077.
• Montgomery, Peter L. (1983). 「ルーカス連鎖による形式 Xm+n = f(Xm, Xn, Xm-n) の再帰の評価」(PS) .未発表.