Function Repository Resource:

ZeckendorfRepresentation

Source Notebook

Give the 0–1 list that indicates the unique nonconsecutive Fibonacci numbers that sum to the non-negative integer input

Contributed by: Wolfram Staff

ResourceFunction["ZeckendorfRepresentation"][n]

gives the 0–1 list that indicates the unique nonconsecutive Fibonacci numbers that sum to the non-negative integer n.

Details and Options

The Fibonacci numbers here are considered to be 1, 2, 3, 5, …, not 1, 1, 2, 3, 5, …; otherwise, the representation would not be unique.

Examples

Basic Examples (2) 

The first number whose representation takes three summands is 12:

In[1]:=
ResourceFunction["ZeckendorfRepresentation"][12]
Out[1]=

This corresponds to 8 + 3 + 1:

In[2]:=
Reverse@Fibonacci[{2, 4, 6}]
Out[2]=

The first number whose representation takes four summands is 33:

In[3]:=
ResourceFunction["ZeckendorfRepresentation"][33]
Out[3]=
In[4]:=
With[{z = ResourceFunction["ZeckendorfRepresentation"][33]}, Prepend[Reverse@z, 0] . Fibonacci@Range[1 + Length@z]]
Out[4]=

Neat Examples (2) 

In[5]:=
Fibonacci@6
Out[5]=

There are Fk Zeckendorf representations of length k; for example, here are the 13 representations of length 7:

In[6]:=
ResourceFunction["ZeckendorfRepresentation"] /@ Range[21, 33] // Grid
Out[6]=

This visualizes the same pattern:

In[7]:=
Framed@Graphics@
  Raster@Reverse[
    1 - ResourceFunction["ZeckendorfRepresentation"] /@ Range[21, 33]]
Out[7]=

Publisher

George Beck

Requirements

Wolfram Language 11.3 (March 2018) or above

Version History

  • 1.0.0 – 25 February 2019

Related Resources

License Information