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

Zeckendorf Representation - dCode

Tag(s) : Arithmetics

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*!

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)

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.

dCode retains ownership of the "Zeckendorf Representation" source code. Except explicit open source licence (indicated Creative Commons / free), the "Zeckendorf Representation" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "Zeckendorf Representation" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, or API access for "Zeckendorf Representation" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!

Reminder : dCode is free to use.

The copy-paste of the page "Zeckendorf Representation" or any of its results, is allowed (even for commercial purposes) as long as you credit dCode!

Exporting results as a .csv or .txt file is free by clicking on the *export* icon

Cite as source (bibliography):

*Zeckendorf Representation* on dCode.fr [online website], retrieved on 2024-09-10,

zeckendorf,representation,fibonacci,theorem,edouard

https://www.dcode.fr/zeckendorf-representation

© 2024 dCode — El 'kit de herramientas' definitivo para resolver todos los juegos/acertijos/geocaching/CTF.

Feedback