Zeckendorf Representation Calculator

n = F(k₁) + F(k₂) + ...

CalculatorsFreeNo Signup
4.2(87 reviews)
All Tools

Loading tool...

About Zeckendorf Representation Calculator

A Zeckendorf representation calculator expressing n as a sum of non-consecutive Fibonacci numbers. This representation is unique (Zeckendorf's theorem). Uses the greedy algorithm. Shows the Fibonacci decomposition and verification. All client-side.

Zeckendorf Representation Calculator Features

  • Zeckendorf form
  • Fibonacci parts
  • Greedy algorithm
  • Verification
  • Binary form
Zeckendorf's theorem: every positive integer has a unique representation as a sum of non-consecutive Fibonacci numbers. Use greedy: subtract largest Fibonacci ≤ n, repeat. Example: 100 = 89+8+3 = F(11)+F(6)+F(4). No two consecutive Fibonacci numbers used.

How to Use

Enter n:

  • Representation: Sum of Fibonacci numbers
  • Indices: Which F(k) are used
  • Binary: Fibonacci binary form

Zeckendorf's Theorem

Uniqueness: the representation with no two consecutive Fibonacci numbers is unique. Proof: if F(k) and F(k+1) both used, replace with F(k+2). Repeat until no consecutive pair remains. The greedy algorithm always produces this form.

Fibonacci Coding

Fibonacci coding: represent n in Zeckendorf form, write 1s/0s for used/unused Fibonacci numbers, append '1' as end marker. Used in data compression with the property that no codeword is a prefix of another.

Step-by-Step Instructions

  1. 1Enter n.
  2. 2View Zeckendorf form.
  3. 3See Fibonacci indices.
  4. 4Check verification.
  5. 5View binary form.

Zeckendorf Representation Calculator — Frequently Asked Questions

Why can't consecutive Fibonacci numbers appear?+

F(k)+F(k+1) = F(k+2) by definition, so you'd use F(k+2) instead. The uniqueness relies on this: any representation with consecutive terms can be simplified. The non-consecutive requirement makes the representation unique.

How is this used in data compression?+

Fibonacci coding: Zeckendorf form gives a binary string (1 if F(k) used, 0 if not). Append '11' as terminator (impossible in valid Zeckendorf). This gives a self-delimiting code — used in some compression algorithms and databases.

How efficient is the greedy algorithm?+

The greedy algorithm runs in O(log n) time since there are O(log n) Fibonacci numbers up to n. Simply find the largest F(k) ≤ n, include it, subtract, and repeat. The algorithm always produces the unique Zeckendorf representation.

More Calculators Tools

Explore all 639 other calculators tools available on Generatr

1-Sample Z-Test Calculator2-Sample Z-Test Calculator3D Surface Area CalculatorA/B Testing Significance CalculatorAbsolute Value CalculatorAbundant Number CheckerAccelerated Aging CalculatorAchromatic Number CalculatorAcyclic Chromatic Number CalculatorAdditive Persistence CalculatorAge CalculatorAging Test CalculatorAlbertson Index CalculatorAlgebraic Connectivity CalculatorAliquot Sequence CalculatorAliquot Sum CalculatorAlternating Series Test CalculatorAmicable Number FinderAnnuity CalculatorAPY CalculatorAquarium CO2 Drop CheckerArea CalculatorArea Under Curve CalculatorArithmetic Sequence CalculatorArmstrong Number CalculatorASCVD Risk CalculatorAspect Ratio CalculatorAtom Bond Connectivity CalculatorAugmented Eccentric Connectivity CalculatorAugmented Zagreb Index Calculator
View all 639 calculators tools
Share this tool: