Numer Leonarda

Liczby Leonarda to sekwencja liczb podanych przez powtarzalność:

${\ Displaystyle L (n) = {\ rozpocząć {przypadki} 1 i { \mbox{if }}n=0\\1&{\mbox{if }}n=1\\L(n-1)+L(n-2)+1&{\mbox{if }}n>1\ \\end{przypadki}}}$

Edsger W. Dijkstra wykorzystał je jako integralną część swojego algorytmu smoothsort , a także szczegółowo je przeanalizował.

Liczba pierwsza Leonarda to liczba Leonarda , która jest również liczbą pierwszą .

Wartości

Pierwsze numery Leonarda to

1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, ... (sekwencja A001595 w OEIS )

Jedynymi liczbami pierwszymi Leonarda są

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

Cykle modulo

Liczby Leonarda tworzą cykl w dowolnym modulo n≥2. Łatwym sposobem, aby to zobaczyć, jest:

• Jeśli para liczb modulo n pojawia się dwa razy w ciągu, to mamy do czynienia z cyklem.
• Jeśli założymy, że główne stwierdzenie jest fałszywe, używając poprzedniego stwierdzenia, oznaczałoby to, że istnieje nieskończona liczba różnych par liczb między 0 a n-1, co jest fałszywe, ponieważ jest n 2 ^takich par.

Cykle dla n≤8 to:

Modulo	Cykl	Długość
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

Cykl zawsze kończy się na parze (1,n-1), ponieważ jest to jedyna para, która może poprzedzać parę (1,1).

Wyrażenia

• L

$n-1) -L (n-3)}$

Dowód

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

Związek z liczbami Fibonacciego

Fibonacci numbers L ${\ Displaystyle L (n) = 2F (n + 1) -1, n$ geq .

Z tej relacji łatwo jest wyprowadzić wyrażenie w postaci zamkniętej dla liczb Leonarda, analogiczne do wzoru Bineta na liczby Fibonacciego:

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

gdzie złoty $_ \ psi = \ lewo (1- {\ sqrt {5}} \ prawej)/2}$$i$ Displaystyle to pierwiastki wielomianu kwadratowego ${\ Displaystyle x ^ {2} -x-1 = 0}$ .

Linki zewnętrzne

• Sekwencja OEIS A001595