Lucas Sequence

Generate the Lucas sequence efficiently using dynamic programming.

math sequence dynamic programming

Write a function `lucas(n)` that returns the n-th Lucas number. The Lucas sequence is defined as:
- L(0) = 2
- L(1) = 1
- L(n) = L(n-1) + L(n-2) for n >= 2

For example, the sequence begins: 2, 1, 3, 4, 7, 11, 18, 29, ...

Implement the function efficiently. It should handle non-negative integers. The function should return an integer.

Constraints

- 0 <= n <= 5000
- The result may be large; Python handles big integers natively.
- Your implementation should be iterative or use memoization to avoid exponential time.

Example

>>> lucas(0)
2
>>> lucas(1)
1
>>> lucas(2)
3
>>> lucas(10)
123

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of the Fibonacci sequence but with different base cases.

Use a loop to build up the sequence from the bottom instead of recursion without memoization.

Store only the last two values to save space.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.