Leonardo raqami

Leonardo raqamlari takrorlanish orqali berilgan raqamlar ketma-ketligi hisoblanadi:

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

Edsger W. Dijkstra^[1] ularni silliq tartiblash algoritmining ajralmas qismi sifatida ishlatgan va shuningdek, ularni batafsil tahlil qilganlar^[2][3].

Leonardo tubi Leonardo soni boʻlib, u ham tub son hisoblanadi.

Qiymatlari

Birinchi bir nechta Leonardo raqamlari quyidagilar:

1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167,…

Leonardoning birinchi bir necha asosiy sonlari:

3, 5, 41, 67, 109, 1973, 5167, 2692537, 11405773, 126491971, 331160281, 535828591, 279167724889, 145446920496281, 28944668049352441, 5760134388741632239, 63880869269980199809, 167242286979696845953, 597222253637954133837103, …

Modul sikllari

Leonardo raqamlari har qanday modulda n≥2 sikl hosil qiladi. Uni koʻrishning oson yoʻli quyidagilar:

• Agar juftlik moduli n ketma-ketlikda ikki marta paydo boʻlsa, unda sikl mavjud.
• Agar oldingi bayonotdan foydalanib, asosiy bayonotni notoʻgʻri deb hisoblasak, bu 0 va n-1 oʻrtasida cheksiz aniq juft raqamlar mavjudligini bildiradi, chunki bu notoʻgʻri, chunki n² juftlik mavjud boʻladi.

n≤8 uchun sikllar:

Modul	Davr	Uzunlik
2	1	1
3	1,1,0,2,0,0,1,2	8
4	1,1,3	3
5	1,1,3,0,4,0,0,1,2,4,2,2,0,3,4,3,3,2,1,4	20
6	1,1,3,5,3,3,1,5	8
7	1,1,3,5,2,1,4,6,4,4,2,0,3,4,1,6	16
8	1,1,3,5,1,7	6

Davr har doim (1,n-1) juftlikda tugaydi, chunki bu juftlikdan (1,1) oldin kelishi mumkin boʻlgan yagona juftlik boʻladi.

Ifodalar

• Quyidagi tenglama qoʻllanadi:

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

Fibonachchi raqamlariga munosabat

Leonardo raqamlari Fibonachchi raqamlari bilan quyidagi munosabatlarga bogʻliq ${\displaystyle L(n)=2F(n+1)-1,n\geq 0}$ .

Bu munosabatdan Leonardo raqamlari uchun Binetning Fibonachchi raqamlari formulasiga oʻxshash yopiq shakldagi ifodani olish juda oson:

${\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}$

bu yerda oltin nisbat ${\displaystyle \varphi =\left(1+{\sqrt {5}}\right)/2}$ va ${\displaystyle \psi =\left(1-{\sqrt {5}}\right)/2}$ kvadrat polinomning ildizlari ${\displaystyle x^{2}-x-1=0}$ shunga teng .

Manbalar

1. „E.W.Dijkstra Archive: Fibonacci numbers and Leonardo numbers. (EWD 797)“. www.cs.utexas.edu. Qaraldi: 2020-yil 11-avgust.
2. „E.W.Dijkstra Archive: Smoothsort, an alternative for sorting in situ (EWD 796a)“. www.cs.utexas.edu. Qaraldi: 2020-yil 11-avgust.
3. „Leonardo Number - GeeksforGeeks“. www.geeksforgeeks.org. Qaraldi: 2022-yil 8-oktyabr.

Havolalar

• OEIS sequence A001595

Andoza:Classes of natural numbers