The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Math-NumSeq-74
River stage zero No dependents
3 ++
/ Math::NumSeq::FibonacciRepresentations

NAME

Math::NumSeq::FibonacciRepresentations -- count of representations by sum of Fibonacci numbers

SYNOPSIS

 use Math::NumSeq::FibonacciRepresentations;
 my $seq = Math::NumSeq::FibonacciRepresentations->new;
 my ($i, $value) = $seq->next;

DESCRIPTION

This is the Fibonacci representations function R(i) which is the number of ways i can be represented as a sum of distinct Fibonacci numbers,

    1, 1, 1, 2, 1, 2, 2, 1, 3, 2, 2, 3, 1, 3, 3, 2, 4, 2, 3, 3, ...
    starting i=0

For example R(11)=3 because 11 is a sum of Fibonacci numbers in the following three different ways

    11 = 8 + 3                R(11)=3 sums
       = 8 + 2 + 1
       = 5 + 3 + 2 + 1

Array

The pattern in the values can be seen by arranging them in rows of an array.

                         1                          i=0 to 0
    1                                         1     i=0 to 1
    1                                         1     i=1 to 2
    1                    2                    1     i=2 to 4
    1               2         2               1     i=4 to 7
    1       3       2         2       3       1     i=7 to 12
    1     3   3     2    4    2     3   3     1     i=12 to 20
    1  4  3   3  5  2   4 4   2  5  3   3  4  1     i=20 to 33
    1 4 4 3 6 3 5 5 2 6 4 4 6 2 5 5 3 6 3 4 4 1     i=33 to 54
                                                  F[y]-1 to F[y+1]-1

There are Fibonacci F[y-1] many values in each row, running from i=F[y]-1 to i=F[y+1]-1. Notice the ranges overlap so each "1" at the right hand end is a repeat of the "1" at the left end. There's just a single 1 in the sequence for each block.

New values in row y are the sum of adjacent values in row y-2, or equivalently a pattern of duplications and sums from row y-1. For example in the third row the "2" has duplicated to be 2,2, then in the fourth row the adjacent 1,2 values sum to give new "3". The row y-2 is a kind of Fibonacci style delay to when values are summed, resulting in F many values in each row.

FUNCTIONS

See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.

$seq = Math::NumSeq::FibonacciRepresentations->new ()

Create and return a new sequence object.

Random Access

$value = $seq->ith($i)

Return the $i'th value of the sequence.

($v0, $v1) = $seq->ith_pair($i)

Return two values ith($i) and ith($i+1) from the sequence. As described below ("Ith Pair") two values can be calculated with the same work as one.

$bool = $seq->pred($value)

Return true if $value occurs in the sequence, which means simply integer $value>=1.

FORMULAS

Ith Pair

For ith_pair() the two sequence values at an arbitrary i,i+1 can be calculated from the Zeckendorf form of i+1 (see "Zeckendorf Base" in Math::NumSeq::Fibbinary) as per

Berstel uses a state machine which results in matrices based on runs of consecutive 0-bits in the Zeckendorf form. If making the Zeckendorf breakdown by some sort of logarithm or high binary bit then that would be Fibonacci number indices and their differences are the run lengths.

If making the Zeckendorf breakdown by individual Fibonacci number comparisons to give the fibbinary form then it's convenient to take each bit individually rather than in runs. In the following algorithm, runs of 0-bits do "r += rprev" every second time and hence become "r += rprev*floor(run/2)" which is per the M matrices of Berstel.

    rprev = 1  = R(0)    will become R[i]
    r     = 1  = R(1)    will become R[i+1]
    zeros = 0            how many consecutive bit=0 seen

    for each bit of fibbinary(i+1) from high to low
      if bit=0 then
        if zeros odd then r += rprev
        zeros ^= 1
      if bit=1 then
        if zeros odd then rprev += r
                     else rprev = r
        zeros = 0

    result R[i]=rprev, R[i+1]=r

The loop maintains r=R[bits] where "bits" is those bits of fibbinary(i+1) which have been processed so far. rprev is the immediately preceding sequence value.

The loop action is to append either a 0-bit or 1-bit Zeckendorf term to the bits processed so far and step r,rprev accordingly.

"zeros" is the count of 0-bits seen since the last 1-bit. This is kept only modulo 2 since the test is just for odd or even run of zeros, not the full count.

For a 1-bit the zeros count becomes 0 since there are now no 0-bits since the last 1-bit seen. In the Zeckendorf form a 1-bit always has a 0-bit immediately below it. That bit can be worked into the bit=1 case,

      if bit=1 then
        if zeros odd then rprev += r
                     else rprev = r
        next lower bit of fibbinary(i+1) is 0-bit, skip it
        zeros = 1

This is as if the bit=0 code is done immediately after the bit=1. zeros=0 is even after the bit=1 so there's no change to r,rprev by the bit=0 code, simply skip the 0-bit and record zeros=1.

When calculating Fibonacci numbers for fibbinary(i+1) it's desirable to use integers <=i only so as not to overflow a finite number type. This can be done by finding the biggest Fibonacci f1<=i and subtracting it before doing the +1, giving i+1-f1 without overflow. If the biggest Fibonacci <=i+1 is in fact f2=f1+f0<=i+1 then will have i+1-f1 >= f0 and should subtract that too for i+1-(f1+f0). The loop begins at the f1 bit in this case, or at the f0 bit if not.

When the high 1-bit is handled like this to avoid overflow the second highest bit is always a 0-bit the same as above. So the loop can begin one lower, so f0 if f2 was subtracted or the Fibonacci below f0 if not. Initial zero=1 to record the 0-bit skipped.

f1<=i and f1+f0<=i+1 only occurs when i+1=f1+f0 exactly, so it has all 0-bits. This can be treated explicitly by floor(count/2) which is the 0-bit cases in the loop. i+1=Fibonacci won't occur very often, but returning count/2 is about the amount code as an i-=f0 and setup to loop from f1.

The effect of the algorithm in each case is to descend through the array above ("Array") by taking or not taking mediant r+rprev or duplication rprev=r. This can be compared to the Stern diatomic sequence calculation which goes by taking or not taking the mediant, no duplicating rprev=r case.

Stern Diatomic

The Fibonacci representations sequence contains the Stern diatomic sequence (eg. Math::NumSeq::SternDiatomic) as a subset, per

Taking the R(i) at indices i for which i in Zeckendorf form uses only even Fibonaccis gives the Stern diatomic sequence.

These indices have fibbinary value (Math::NumSeq::Fibbinary) with 1-bits only at even bit positions (counting the least significant bit position as 0 and going up from there). Even positions are either 0 or 1. Odd positions are always 0. The highest bit is always a 1-bit and it must be at an even position.

    fibbinary(i) = 10a0b0c...0z
                     ^ ^ ^    ^
                     even bits a,b,c,etc 0 or 1,
                     odd bits always 0

In the "Ith Pair" calculation above this kind of i always has an odd number of 0-bits between each 1-bit. So the 1-bit step is always rprev+=r, and the 0-bit step at the even positions is r+=prev. Those two steps are the same as the Stern diatomic calculation per "Ith Pair" in Math::NumSeq::SternDiatomic.

SEE ALSO

Math::NumSeq::Fibonacci, Math::NumSeq::SternDiatomic

HOME PAGE

http://user42.tuxfamily.org/math-numseq/index.html

LICENSE

Copyright 2014, 2016, 2019 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.