1Math::NumSeq::FibonacciURseeprreCsoennttraitbiuotnesdM(a3Pt)ehr:l:NDuomcSuemqe:n:tFaitbioonnacciRepresentations(3)
2
6 Math::NumSeq::FibonacciRepresentations -- count of representations by
7 sum of Fibonacci numbers
8
10 use Math::NumSeq::FibonacciRepresentations;
11 my $seq = Math::NumSeq::FibonacciRepresentations->new;
12 my ($i, $value) = $seq->next;
13
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 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 For example R(11)=3 because 11 is a sum of Fibonacci numbers in the
22 following three different ways
23 11 = 8 + 3 R(11)=3 sums
25 = 8 + 2 + 1
26 = 5 + 3 + 2 + 1
27 Array
29 The pattern in the values can be seen by arranging them in rows of an
30 array.
31 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 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 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
56 See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
57 classes.
58 "$seq = Math::NumSeq::FibonacciRepresentations->new ()"
60 Create and return a new sequence object.
61 Random Access
63 "$value = $seq->ith($i)"
64 Return the $i'th value of the sequence.
65 "($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 "$bool = $seq->pred($value)"
72 Return true if $value occurs in the sequence, which means simply
73 integer "$value>=1".
74
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 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 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 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 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 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 result R[i]=rprev, R[i+1]=r
111 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 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 "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 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 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 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 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 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 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 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 Stern Diatomic
164 The Fibonacci representations sequence contains the Stern diatomic
165 sequence (eg. Math::NumSeq::SternDiatomic) as a subset, per
166 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 <http://www.fq.math.ca/41-2.html>
172 <http://www.fq.math.ca/Scanned/41-2/bicknell.pdf>
173 Taking the R(i) at indices i for which i in Zeckendorf form uses only
175 even Fibonaccis gives the Stern diatomic sequence.
176 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 fibbinary(i) = 10a0b0c...0z
184 ^ ^ ^ ^
185 even bits a,b,c,etc 0 or 1,
186 odd bits always 0
187 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
195 Math::NumSeq::Fibonacci, Math::NumSeq::SternDiatomic
196
198 <http://user42.tuxfamily.org/math-numseq/index.html>
199
201 Copyright 2014 Kevin Ryde
202 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 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 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/>.
215perl v5.28.1 2014M-a0t7h-:1:3NumSeq::FibonacciRepresentations(3)