レオナルド数

レオナルド数は、次の繰り返しによって与えられる数列です。

${\displaystyle L(n)={\begin{cases}1&{\mbox{if }}n=0\\1&{\mbox{if }}n=1\\L(n-1)+L(n-2)+1&{\mbox{if }}n>1\\\end{cases}}}$

エドガー・W・ダイクストラ^{[1]は、これらを}スムースソート アルゴリズム[ 2 ^]の不可欠な部分として使用し 、詳細に分析しました。^{[3] [4]}

レオナルド素数とは、素数でもあるレオナルド数です。

最初の数個のレオナルド番号は

1、1、3、5、9、15、25、41、67、109、177、287、465、753、1219、1973、3193、5167、8361、...（OEISのシーケンスA001595）

最初のいくつかのレオナルド素数は

3 , 5 , 41 , 67 , 109 , 1973, 5167, 2692537, 11405773, 126491971, 331160281, 535828591, 279167724889, 145446920496281, 28944668049352441, 5760134388741632239, 63880869269980199809, 167242286979696845953, 597222253637954133837103, ... (sequence A145912 in OEIS )​

レオナルド数は n≥2 を法として循環を形成します。これを簡単に確認する方法は次のとおりです。

• n を法とする数のペアがシーケンス内に 2 回出現する場合、循環が存在します。
• 前のステートメントを使用して、メインステートメントが偽であると仮定すると、0 と n-1 の間には無限の異なる数値のペアが存在することになりますが、そのようなペアは n ²個あるため、これは偽です。

n≤8 のサイクルは次のとおりです。

サイクルは常にペア (1,n-1) で終了します。これは、ペア (1,1) の前に存在できる唯一のペアだからです。

• 次の式が適用されます。

${\displaystyle L(n)=2L(n-1)-L(n-3)}$

レオナルド数とフィボナッチ数の間には関係があります。 ${\displaystyle L(n)=2F(n+1)-1,n\geq 0}$

この関係から、フィボナッチ数列のビネの公式に類似したレオナルド数列の 閉じた形式の表現を簡単に導くことができます。

${\displaystyle L(n)=2{\frac {\varphi ^{n+1}-\psi ^{n+1}}{\varphi -\psi }}-1={\frac {2}{\sqrt {5}}}\left(\varphi ^{n+1}-\psi ^{n+1}\right)-1=2F(n+1)-1}$

ここで、黄金比 と は、2次多項式の根です。 ${\displaystyle \varphi =\left(1+{\sqrt {5}}\right)/2}$${\displaystyle \psi =\left(1-{\sqrt {5}}\right)/2}$ ${\displaystyle x^{2}-x-1=0}$

• OEISシーケンスA001595