The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Math-NumSeq-70
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 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).

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

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

Within the loop r=R[bits] for 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 and step r,rprev accordingly.

The "trailing 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 trailing 0-bits, not the full count.

For a 1-bit the trailing zeros count becomes 0 since there are now no trailing 0-bits. In the Zeckendorf form a 1-bit is always followed by a 0-bit below it. That bit can be worked into the bit=1 case if desired.

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

This is as if the bit=0 code was done immediately after the bit=1. Since trailing zeros is even after bit=1 there's no change to r,rprev by the bit=0 code, so just skip the bit and record trailing zeros is now odd.

The effect of this algorithm is to descend through the array above by taking or not taking the mediant r+rprev or duplicating by rprev=r. This can be compared to the Stern diatomic sequence calculation where the mediant is always taken.

A state machine approach to the calculation can be found in

Runs of 0-bits do an "r += rprev" every second time and hence become "r += rprev*floor(run/2)" which is per the M matrices by Berstel. If making the Zeckendorf breakdown by some sort of logarithm or high binary bit then that would generate Fibonacci number indices (rather than individual bits) and their differences would be the run lengths.

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 use 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). So even positions are either 0 or 1, odd positions 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 have 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 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/>.