Tool to apply / check the Zeckendorf theorem stipulating that any integer can be written in the form of sum of Fibonacci numbers also called Zeckendorf representation.

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day! A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!

Tool to apply / check the Zeckendorf theorem stipulating that any integer can be written in the form of sum of Fibonacci numbers also called Zeckendorf representation.

Answers to Questions

What is the Zeckendorf theorem? (Definition)

Every natural integer $ n \in \mathbb {N} $ has a unique representation in the form of a sum of non-consecutive Fibonacci numbers. Its formula is written: $$ n = \sum_{i=0}^{k} \alpha_i F_{i} $$ with $ F_i $ the ith Fibonacci number, $ \alpha_i $ is a binary number $ 0 $ or $ 1 $ (a way to indicate that the number of Fibonacci is in the sum, or it is not) and $ \alpha_i \times \alpha_{i + 1} = 0 $ (a way to prevent 2 numbers consecutive Fibonacci).

This proprety is used in Fibonacci coding (a binary representation of any integer based on the values of $ \alpha_i $ in the formula above)

How to calculate a Zeckendorf representation?

Enter a value of a number $ N $ and dCode will do the calculation automatically.

Example: 10000 is the sum of $ 6765 + 2584 + 610 + 34 + 5 + 2 $, respectively the 20th, 18th, 15th, 9th, 5th and 3rd Fibonacci numbers

Algorithmically, dCode uses Binet's formula to obtain Fibonacci numbers close to a given number and subtracts them recursively until finding the Zeckendorf representation.

Source code

dCode retains ownership of the source code of the script Zeckendorf Representation online. Except explicit open source licence (indicated Creative Commons / free), any algorithm, applet, snippet, software (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt, encrypt, decipher, cipher, decode, code, translate) written in any informatic langauge (PHP, Java, C#, Python, Javascript, Matlab, etc.) which dCode owns rights will not be given for free. To download the online Zeckendorf Representation script for offline use on PC, iPhone or Android, ask for price quote on contact page !