1Math::NumSeq::FibonacciURseeprreCsoennttraitbiuotnesdM(a3Pt)ehr:l:NDuomcSuemqe:n:tFaitbioonnacciRepresentations(3)
2
3
4

NAME

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

SYNOPSIS

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

DESCRIPTION

15       This is the Fibonacci representations function R(i) which is the number
16       of ways i can be represented as a sum of distinct Fibonacci numbers,
17
18           1, 1, 1, 2, 1, 2, 2, 1, 3, 2, 2, 3, 1, 3, 3, 2, 4, 2, 3, 3, ...
19           starting i=0
20
21       For example R(11)=3 because 11 is a sum of Fibonacci numbers in the
22       following three different ways
23
24           11 = 8 + 3                R(11)=3 sums
25              = 8 + 2 + 1
26              = 5 + 3 + 2 + 1
27
28   Array
29       The pattern in the values can be seen by arranging them in rows of an
30       array.
31
32                                1                          i=0 to 0
33           1                                         1     i=0 to 1
34           1                                         1     i=1 to 2
35           1                    2                    1     i=2 to 4
36           1               2         2               1     i=4 to 7
37           1       3       2         2       3       1     i=7 to 12
38           1     3   3     2    4    2     3   3     1     i=12 to 20
39           1  4  3   3  5  2   4 4   2  5  3   3  4  1     i=20 to 33
40           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
41                                                         F[y]-1 to F[y+1]-1
42
43       There are Fibonacci F[y-1] many values in each row, running from
44       i=F[y]-1 to i=F[y+1]-1.  Notice the ranges overlap so each "1" at the
45       right hand end is a repeat of the "1" at the left end.  There's just a
46       single 1 in the sequence for each block.
47
48       New values in row y are the sum of adjacent values in row y-2, or
49       equivalently a pattern of duplications and sums from row y-1.  For
50       example in the third row the "2" has duplicated to be 2,2, then in the
51       fourth row the adjacent 1,2 values sum to give new "3".  The row y-2 is
52       a kind of Fibonacci style delay to when values are summed, resulting in
53       F many values in each row.
54

FUNCTIONS

56       See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
57       classes.
58
59       "$seq = Math::NumSeq::FibonacciRepresentations->new ()"
60           Create and return a new sequence object.
61
62   Random Access
63       "$value = $seq->ith($i)"
64           Return the $i'th value of the sequence.
65
66       "($v0, $v1) = $seq->ith_pair($i)"
67           Return two values "ith($i)" and "ith($i+1)" from the sequence.  As
68           described below ("Ith Pair") two values can be calculated with the
69           same work as one.
70
71       "$bool = $seq->pred($value)"
72           Return true if $value occurs in the sequence, which means simply
73           integer "$value>=1".
74

FORMULAS

76   Ith Pair
77       For "ith_pair()" the two sequence values at an arbitrary i,i+1 can be
78       calculated from the Zeckendorf form of i+1 (see "Zeckendorf Base" in
79       Math::NumSeq::Fibbinary) as per
80
81           Jean Berstel, "An Exercise on Fibonacci Representations",
82           Theoretical Informatics and Applications, volume 35, 2001, pages
83           491-498.
84           <http://archive.numdam.org/numdam-bin/fitem?id=ITA_2001__35_6_491_0>
85
86       Berstel uses a state machine which results in matrices based on runs of
87       consecutive 0-bits in the Zeckendorf form.  If making the Zeckendorf
88       breakdown by some sort of logarithm or high binary bit then that would
89       be Fibonacci number indices and their differences are the run lengths.
90
91       If making the Zeckendorf breakdown by individual Fibonacci number
92       comparisons to give the fibbinary form then it's convenient to take
93       each bit individually rather than in runs.  In the following algorithm,
94       runs of 0-bits do "r += rprev" every second time and hence become "r +=
95       rprev*floor(run/2)" which is per the M matrices of Berstel.
96
97           rprev = 1  = R(0)    will become R[i]
98           r     = 1  = R(1)    will become R[i+1]
99           zeros = 0            how many consecutive bit=0 seen
100
101           for each bit of fibbinary(i+1) from high to low
102             if bit=0 then
103               if zeros odd then r += rprev
104               zeros ^= 1
105             if bit=1 then
106               if zeros odd then rprev += r
107                            else rprev = r
108               zeros = 0
109
110           result R[i]=rprev, R[i+1]=r
111
112       The loop maintains r=R[bits] where "bits" is those bits of
113       fibbinary(i+1) which have been processed so far.  rprev is the
114       immediately preceding sequence value.
115
116       The loop action is to append either a 0-bit or 1-bit Zeckendorf term to
117       the bits processed so far and step r,rprev accordingly.
118
119       "zeros" is the count of 0-bits seen since the last 1-bit.  This is kept
120       only modulo 2 since the test is just for odd or even run of zeros, not
121       the full count.
122
123       For a 1-bit the zeros count becomes 0 since there are now no 0-bits
124       since the last 1-bit seen.  In the Zeckendorf form a 1-bit always has a
125       0-bit immediately below it.  That bit can be worked into the bit=1
126       case,
127
128             if bit=1 then
129               if zeros odd then rprev += r
130                            else rprev = r
131               next lower bit of fibbinary(i+1) is 0-bit, skip it
132               zeros = 1
133
134       This is as if the bit=0 code is done immediately after the bit=1.
135       zeros=0 is even after the bit=1 so there's no change to r,rprev by the
136       bit=0 code, simply skip the 0-bit and record zeros=1.
137
138       When calculating Fibonacci numbers for fibbinary(i+1) it's desirable to
139       use integers <=i only so as not to overflow a finite number type.  This
140       can be done by finding the biggest Fibonacci f1<=i and subtracting it
141       before doing the +1, giving i+1-f1 without overflow.  If the biggest
142       Fibonacci <=i+1 is in fact f2=f1+f0<=i+1 then will have i+1-f1 >= f0
143       and should subtract that too for i+1-(f1+f0).  The loop begins at the
144       f1 bit in this case, or at the f0 bit if not.
145
146       When the high 1-bit is handled like this to avoid overflow the second
147       highest bit is always a 0-bit the same as above.  So the loop can begin
148       one lower, so f0 if f2 was subtracted or the Fibonacci below f0 if not.
149       Initial zero=1 to record the 0-bit skipped.
150
151       f1<=i and f1+f0<=i+1 only occurs when i+1=f1+f0 exactly, so it has all
152       0-bits.  This can be treated explicitly by floor(count/2) which is the
153       0-bit cases in the loop.  i+1=Fibonacci won't occur very often, but
154       returning count/2 is about the amount code as an i-=f0 and setup to
155       loop from f1.
156
157       The effect of the algorithm in each case is to descend through the
158       array above ("Array") by taking or not taking mediant r+rprev or
159       duplication rprev=r.  This can be compared to the Stern diatomic
160       sequence calculation which goes by taking or not taking the mediant, no
161       duplicating rprev=r case.
162
163   Stern Diatomic
164       The Fibonacci representations sequence contains the Stern diatomic
165       sequence (eg. Math::NumSeq::SternDiatomic) as a subset, per
166
167           Marjorie Bicknell-Johnson, "Stern's Diatomic Array Applied to
168           Fibonacci Representations", Fibonacci Quarterly, volume 41, number
169           2, May 2003, pages 169-180.
170
171           <http://www.fq.math.ca/41-2.html>
172           <http://www.fq.math.ca/Scanned/41-2/bicknell.pdf>
173
174       Taking the R(i) at indices i for which i in Zeckendorf form uses only
175       even Fibonaccis gives the Stern diatomic sequence.
176
177       These indices have fibbinary value (Math::NumSeq::Fibbinary) with
178       1-bits only at even bit positions (counting the least significant bit
179       position as 0 and going up from there).  Even positions are either 0 or
180       1.  Odd positions are always 0.  The highest bit is always a 1-bit and
181       it must be at an even position.
182
183           fibbinary(i) = 10a0b0c...0z
184                            ^ ^ ^    ^
185                            even bits a,b,c,etc 0 or 1,
186                            odd bits always 0
187
188       In the "Ith Pair" calculation above this kind of i always has an odd
189       number of 0-bits between each 1-bit.  So the 1-bit step is always
190       rprev+=r, and the 0-bit step at the even positions is r+=prev.  Those
191       two steps are the same as the Stern diatomic calculation per "Ith Pair"
192       in Math::NumSeq::SternDiatomic.
193

SEE ALSO

195       Math::NumSeq::Fibonacci, Math::NumSeq::SternDiatomic
196

HOME PAGE

198       <http://user42.tuxfamily.org/math-numseq/index.html>
199

LICENSE

201       Copyright 2014 Kevin Ryde
202
203       Math-NumSeq is free software; you can redistribute it and/or modify it
204       under the terms of the GNU General Public License as published by the
205       Free Software Foundation; either version 3, or (at your option) any
206       later version.
207
208       Math-NumSeq is distributed in the hope that it will be useful, but
209       WITHOUT ANY WARRANTY; without even the implied warranty of
210       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
211       General Public License for more details.
212
213       You should have received a copy of the GNU General Public License along
214       with Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.
215
216
217
218perl v5.28.1                      2014M-a0t7h-:1:3NumSeq::FibonacciRepresentations(3)
Impressum