Lucas Numbers#
Contents#
Lucas Numbers
\( \begin{aligned} L(n) &= \begin{cases} 2 & n = 0 \\ 1 & n = 1 \\ L(n - 1) + L(n - 2) & n \gt 1 \\ \end {cases} \\ &= 2, 1, 3, 4, 7, 11, \dotsc \end {aligned} \)
We can compute the \(n\)-th Lucas number recursively.
L(15)
/ \
L(13) L(14)
/ \ / \
L(11) L(12) L(12) L(13)
/ \ / \ / \ / \
\(T(n) = \Theta(2^n)\)
The height of this tree is \(n\).
Alternative approach which trades time for space: add a linear space requirement to reduce exponential time to linear time.
Compute \(L(6)\).
First, initialize an array of size \(7\).
Traverse down the left side to \(L(0)\).
Then up to \(L(1)\).
Then up to \(L(2)\): fetch \(L(0)\) from the array.
Then up to \(L(3)\): fetch \(L(1)\) from the array.
Then up to \(L(4)\): fetch \(L(2)\) from the array.
Then up to \(L(5)\): fetch \(L(3)\) from the array.
Then up to \(L(6)\): fetch \(L(4)\) from the array.
L(6)
/ \
L(5) L(4)
/ \ / \
L(4) L(3) L(3) L(2)
/ \ / \ / \ / \
L(3) L(2) L(2) L(1) L(2) L(1) L(1) L(0)
/ \ / \ / \ / / \ / /
L(2) L(1) L(1) L(0) L(1) L(0) L(0) L(1) L(0) L(0) L(0)
/ \
L(1) L(0)
/
L(0)
Resources#
https://www.geeksforgeeks.org/lucas-numbers/