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 (OEIS A000119)
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[y1] 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 y2, or equivalently a pattern of duplications and sums from row y1. 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 y2 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.
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)
andith($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
Jean Berstel, "An Exercise on Fibonacci Representations", Theoretical Informatics and Applications, volume 35, 2001, pages 491498. http://archive.numdam.org/numdambin/fitem?id=ITA_2001__35_6_491_0
Berstel uses a state machine which results in matrices based on runs of consecutive 0bits 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 0bits 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 0bit or 1bit Zeckendorf term to the bits processed so far and step r,rprev accordingly.
"zeros" is the count of 0bits seen since the last 1bit. This is kept only modulo 2 since the test is just for odd or even run of zeros, not the full count.
For a 1bit, the zeros count becomes 0 since there are now no 0bits since the last 1bit seen. In the Zeckendorf form a 1bit always has a 0bit 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 0bit, so 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 0bit 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+1f1 without overflow. If the biggest Fibonacci <=i+1 is in fact f2=f1+f0<=i+1 then will have i+1f1 >= 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 1bit is handled like this to avoid overflow, the second highest bit is always a 0bit 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 so as to record the 0bit skipped.
f1<=i and f1+f0<=i+1 only occurs when i+1=f1+f0 exactly, so it has all 0bits. This can be treated explicitly by floor(count/2) which is the 0bit 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
Marjorie BicknellJohnson, "Stern's Diatomic Array Applied to Fibonacci Representations", Fibonacci Quarterly, volume 41, number 2, May 2003, pages 169180.
http://www.fq.math.ca/412.html http://www.fq.math.ca/Scanned/412/bicknell.pdf
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 1bits 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 1bit 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 0bits between each 1bit. So the 1bit step is always rprev+=r, and the 0bit 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/mathnumseq/index.html
LICENSE
Copyright 2014, 2016, 2019, 2020, 2021 Kevin Ryde
MathNumSeq 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.
MathNumSeq 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 MathNumSeq. If not, see <http://www.gnu.org/licenses/>.