This blog post explores a Fibonacci-based number representation through the lens of a familiar party trick and its rigorous mathematical foundation. Starting from the classical Zeckendorf representation, where every integer is written uniquely as a sum of nonconsecutive Fibonacci numbers, we reinterpret the trick as a structured encoding problem rather than sleight of hand. Using a table indexed by Fibonacci positions, an attendee silently decomposes a chosen number according to the locations of the 1’s in its Zeckendorf encoding. Remarkably, the host can reconstruct the original number by reading only the first column of the table, whose entries are Fibonacci numbers themselves. What appears to be a party trick ultimately becomes a concrete illustration of uniqueness, encoding constraints, and the deep structure hidden.
YouTube video: https://youtu.be/S5FTe5KP2Cw
Zeckendorf representation
Zeckendorf representation
The Zeckendorf representation of a number is a unique way of expressing it as a sum of non-consecutive Fibonacci numbers. In this representation, each number is decomposed into a sum where no two consecutive Fibonacci numbers are used, which ensures the uniqueness of the representation. For example, the number 10 would be represented as in terms of Fibonacci numbers, since and and are non-consecutive Fibonacci numbers.
8+2
10=8+2
8
2
Convert 1 to 100 to Zeckendorf representation:
In[]:=
fbZR=ResourceFunction["ZeckendorfRepresentation"]/@Range[100]
Check the maximum number of elements in all lines:
In[]:=
resZR=With[{ml1=Max[Length/@fbZR]},Print[ml=ml1];PadLeft[#,ml1]&/@fbZR];
10
Quickly eyeball the terms:
In[]:=
Short[resZR,5]
Out[]//Short=
{{0,0,0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,1,0},{0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,1,0,1},{0,0,0,0,0,0,1,0,0,0},{0,0,0,0,0,0,1,0,0,1},{0,0,0,0,0,0,1,0,1,0},{0,0,0,0,0,1,0,0,0,0},{0,0,0,0,0,1,0,0,0,1},83,{1,0,0,0,0,0,0,1,0,1},{1,0,0,0,0,0,1,0,0,0},{1,0,0,0,0,0,1,0,0,1},{1,0,0,0,0,0,1,0,1,0},{1,0,0,0,0,1,0,0,0,0},{1,0,0,0,0,1,0,0,0,1},{1,0,0,0,0,1,0,0,1,0},{1,0,0,0,0,1,0,1,0,0}}
Backward base conversion using simple linear algebra:
In[]:=
base=Reverse[Array[Fibonacci,ml,2]]
Out[]=
{89,55,34,21,13,8,5,3,2,1}
Test on entries of terms ending with one:
In[]:=
Select[resZR,#[[-1]]==1&].base
Out[]=
{1,4,6,9,12,14,17,19,22,25,27,30,33,35,38,40,43,46,48,51,53,56,59,61,64,67,69,72,74,77,80,82,85,88,90,93,95,98}
Test on entries of terms in which the second last term is one:
In[]:=
Select[resZR,#[[-2]]==1&].base
Out[]=
{2,7,10,15,20,23,28,31,36,41,44,49,54,57,62,65,70,75,78,83,86,91,96,99}
Apply base conversion to every row:
In[]:=
resZR2=Table[Select[resZR,#[[-k]]==1&].base,{k,1,ml}]
Out[]=
{{1,4,6,9,12,14,17,19,22,25,27,30,33,35,38,40,43,46,48,51,53,56,59,61,64,67,69,72,74,77,80,82,85,88,90,93,95,98},{2,7,10,15,20,23,28,31,36,41,44,49,54,57,62,65,70,75,78,83,86,91,96,99},{3,4,11,12,16,17,24,25,32,33,37,38,45,46,50,51,58,59,66,67,71,72,79,80,87,88,92,93,100},{5,6,7,18,19,20,26,27,28,39,40,41,52,53,54,60,61,62,73,74,75,81,82,83,94,95,96},{8,9,10,11,12,29,30,31,32,33,42,43,44,45,46,63,64,65,66,67,84,85,86,87,88,97,98,99,100},{13,14,15,16,17,18,19,20,47,48,49,50,51,52,53,54,68,69,70,71,72,73,74,75},{21,22,23,24,25,26,27,28,29,30,31,32,33,76,77,78,79,80,81,82,83,84,85,86,87,88},{34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54},{55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88},{89,90,91,92,93,94,95,96,97,98,99,100}}
Create the table used in the video and wrap it with Manipulate to test all numbers in the given range:
In[]:=
Manipulate[myNum2=myNum;ToTabular[<|"Numbers"->Row[Riffle[highlightHead@#,", "]],"Check"->If[MemberQ[#,myNum],Style["V",Bold,StandardOrange],Missing[]]|>&/@resZR2,ItemSize->{{73,5},0.8}],{myNum,1,100,1},SaveDefinitions->True]
Out[]=
Sync the output with the slider above and recover the guessed number from the position of check marks::
In[]:=
Dynamic[With[{pos=Flatten@Position[Reverse@ResourceFunction["ZeckendorfRepresentation"][myNum2],1]},Row[{"Row ",pos," checked. \n",myNum2," = sum of ",Fibonacci[pos+1]}]]]//Framed
Out[]=
Dual Zeckendorf representation
Dual Zeckendorf representation
We then extend the discussion to a dual Fibonacci representation, governed by a complementary constraint that forbids neighboring missing Fibonacci terms. While visually similar, this dual rule produces a distinct combinatorial structure. Use similar code above
In[]:=
fb2=ResourceFunction["DualZeckendorfRepresentation"]/@Range[100];
The maximum length is smaller in this representation:
In[]:=
res=With[{ml1=Max[Length/@fb2]},Print[ml=ml1];PadLeft[#,ml1]&/@fb2];
9
Backward base conversion using simple linear algebra:
In[]:=
base=Reverse@Array[Fibonacci,ml,2]
Out[]=
{55,34,21,13,8,5,3,2,1}
Convert binary encode back to the decimal representations:
In[]:=
resDZR=Table[Select[res,#[[-k]]==1&].base,{k,1,ml}];
Create the party trick table similar to the one above but using dual representation:
In[]:=
Manipulate[myNum3=myNum;ToTabular[<|"Numbers"->Column@(Row[Riffle[#,", "]]&/@Partition[highlightHead@#,Floor[Length[#]/2]]),"Check"->If[MemberQ[#,myNum],Style["V",Bold,StandardOrange],Missing[]]|>&/@resDZR,ItemSize->{{78,3},2},Alignment-><|"Rows"->Center|>,ImageSize->{850,800}],{myNum,1,100,1}]
Out[]=
Recover the guessed number from the position of check marks:
In[]:=
Dynamic[With[{pos=Flatten@Position[Reverse@ResourceFunction["DualZeckendorfRepresentation"][myNum3],1]},Row[{"Row ",pos," checked. \n",myNum3," = sum of ",Fibonacci[pos+1]}]]]//Framed
Out[]=
Cover art
Cover art
Hamming Graph Embedding for Zeckendorf Rep.:
In[]:=
fbZR=ResourceFunction["ZeckendorfRepresentation"]/@Range[250];circleLayout[n_]:=Table[{Cos[2π/ni],Sin[2π/ni]},{i,n}];resZR=With[{ml1=Max[Length/@fbZR]},base=Reverse[Array[Fibonacci,ml1,2]];PadLeft[#,ml1]&/@fbZR];Graph[UndirectedEdge@@@Map[#.base&,Select[Subsets[resZR,{2}],HammingDistance@@#==1&],{2}],VertexCoordinates->Thread[Range[250]->circleLayout[250]],VertexSize->Small]
Out[]=
Utility
Utility
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Companion to "Base Fibonacci - Numberphile"
by Shenghui Yang
Wolfram Community, STAFF PICKS, January 11, 2025
https://community.wolfram.com/groups/-/m/t/3604657
by Shenghui Yang
Wolfram Community, STAFF PICKS, January 11, 2025
https://community.wolfram.com/groups/-/m/t/3604657