zeckendorf(N) using a greedy algorithm with binary exponentiation for computing Fib(n)


Updated 8 Jun 2018

View License

Zeckendorf's theorem states that any positive integer, N, can be written as a sum of non-consecutive Fibonacci numbers uniquely. This is achieved by a greedy algorithm: the representation always starts with the largest Fibonacci number <= N.

Here, I used the definition of Fibonacci numbers as:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2).

For example: N = 100 = 89 + 8 + 3.

This code outputs the Zeckendorf representation of a positive integer N. Fibonacci numbers are computed using binary exponentiation of the Fibonacci matrix [1 1; 1 0].

Cite As

Karl Ezra Pilario (2023). zeckendorf(N) (https://www.mathworks.com/matlabcentral/fileexchange/67017-zeckendorf-n), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2017a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes

Added a bit string representation output.

Updated the description.