Zeckendorf representation

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

Documentation

Usage

Details & Options

• The Fibonacci numbers here are considered to be , not ; otherwise, the representation would not be unique.

Setup

use Math::NumberTheory;
use Math::Zeckendorf;

use Graph;
use Graph::Classes;
use Graphviz::DOT::Chessboard;

use Math::SparseMatrix;
use Math::DistanceFunctions;

use Data::Translators;

Examples

Basic examples

The first number whose representation takes three summands is 12:

zeckendorf-representation(12)

This corresponds to :

[2,4,6]».&fibonacci 

The first number whose representation takes four summands is :

zeckendorf-representation(33)

my @z = zeckendorf-representation(33);
([0, |@z.reverse] >>*<< ((1 ... @z.elems + 1)».&fibonacci)).sum

Neat examples

There are Zeckendorf representations of length ; for example, here are the representations of length :

#%html
zeckendorf-representation(21 ... 33)
andthen Math::SparseMatrix.new(dense-matrix => $_, row-names => (21...33), column-names => (^$_.head.elems).reverse)
andthen my $mat = $_
andthen .to-html()

Here is a matrix plot corresponding to the pattern above:

my $matrix-plot = dot-matrix-plot($mat.dense-matrix, row-names => $mat.row-names, column-names => $mat.column-names, :5size):svg;

my $file-name = './img/matrix-plot.svg';
spurt($file-name, $matrix-plot);

"![]($file-name)";

(Using a sparse matrix object made the visualizations easier.)

Make a plot of circle chords that correspond to pairs of integers that have Fibonacci representations with Hamming distance . The chords in slate blue correspond to pairs differences that are prime numbers.

my @mat = (1 ... 250)».&zeckendorf-representation;
my $max-digits = @mat.tail.elems;
@mat .= map({ [|(0 xx ($max-digits - $_.elems)), |$_] });
my @edges = (^@mat.elems X ^@mat.elems).map({ $_ => hamming-distance(|@mat[$_]) }).grep({ $_.value == 1 })».key;
@edges .= map({ $_.head.Str => $_.tail.Str });
my $g = Graph.new(@edges, vertex-coordinates => Graph::Cycle.new(@mat.elems).vertex-coordinates);

#% html
my @highlight = @edges.grep({ is-prime($_.value.Int - $_.key.Int) });
my $chord-plot = $g.dot(
    highlight => {slateblue => @highlight},
    vertex-shape => 'point', 
    vertex-width => 0, 
    vertex-height => 0, 
    edge-thickness => 0.3, 
    :4size,
    engine => 'neato', 
):svg;

my $file-name = './img/chord-plot.svg';
spurt($file-name, $chord-plot);

"![]($file-name)";