1Math::PlanePath::WythofUfsAerrraCyo(n3t)ributed Perl DocMuamtehn:t:aPtliaonnePath::WythoffArray(3)
2
6 Math::PlanePath::WythoffArray -- table of Fibonacci recurrences
7
9 use Math::PlanePath::WythoffArray;
10 my $path = Math::PlanePath::WythoffArray->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This path is the Wythoff array by David R. Morrison
15 "A Stolarsky Array of Wythoff Pairs", in Collection of Manuscripts
17 Related to the Fibonacci Sequence, pages 134 to 136, The Fibonacci
18 Association, 1980.
19 <http://www.math.ucsb.edu/~drm/papers/stolarsky.pdf>
20 It's an array of Fibonacci recurrences which positions each N according
22 to Zeckendorf base trailing zeros.
23 15 | 40 65 105 170 275 445 720 1165 1885 3050 4935
25 14 | 38 62 100 162 262 424 686 1110 1796 2906 4702
26 13 | 35 57 92 149 241 390 631 1021 1652 2673 4325
27 12 | 33 54 87 141 228 369 597 966 1563 2529 4092
28 11 | 30 49 79 128 207 335 542 877 1419 2296 3715
29 10 | 27 44 71 115 186 301 487 788 1275 2063 3338
30 9 | 25 41 66 107 173 280 453 733 1186 1919 3105
31 8 | 22 36 58 94 152 246 398 644 1042 1686 2728
32 7 | 19 31 50 81 131 212 343 555 898 1453 2351
33 6 | 17 28 45 73 118 191 309 500 809 1309 2118
34 5 | 14 23 37 60 97 157 254 411 665 1076 1741
35 4 | 12 20 32 52 84 136 220 356 576 932 1508
36 3 | 9 15 24 39 63 102 165 267 432 699 1131
37 2 | 6 10 16 26 42 68 110 178 288 466 754
38 1 | 4 7 11 18 29 47 76 123 199 322 521
39 Y=0 | 1 2 3 5 8 13 21 34 55 89 144
40 +-------------------------------------------------------
41 X=0 1 2 3 4 5 6 7 8 9 10
42 All rows have the Fibonacci style recurrence
44 W(X+1) = W(X) + W(X-1)
46 eg. X=4,Y=2 is N=42=16+26, sum of the two values to its left
47 X axis N=1,2,3,5,8,etc is the Fibonacci numbers. The row Y=1 above
49 them N=4,7,11,18,etc is the Lucas numbers.
50 Y axis N=1,4,6,9,12,etc is the "spectrum" of the golden ratio, meaning
52 its multiples rounded down to an integer.
53 phi = (sqrt(5)+1)/2
55 spectrum(k) = floor(phi*k)
56 N on Y axis = Y + spectrum(Y+1)
57 Eg. Y=5 N=5+floor((5+1)*phi)=14
59 The recurrence in each row starts as if the row was preceded by two
61 values Y,spectrum(Y+1) which can be thought of adding to be
62 Y+spectrum(Y+1) on the Y axis, then Y+2*spectrum(Y+1) in the X=1
63 column, etc.
64 If the first two values in a row have a common factor then that factor
66 remains in all subsequent sums. For example the Y=2 row starts with
67 two even numbers N=6,N=10 so all N values in the row are even.
68 Every N from 1 upwards occurs precisely once in the table. The
70 recurrence means that in each row N grows roughly as a power phi^X, the
71 same as the Fibonacci numbers. This means they become large quite
72 quickly.
73 Zeckendorf Base
75 The N values are arranged according to trailing zero bits when N is
76 represented in the Zeckendorf base. The Zeckendorf base expresses N as
77 a sum of Fibonacci numbers, choosing at each stage the largest possible
78 Fibonacci. For example
79 Fibonacci numbers F[0]=1, F[1]=2, F[2]=3, F[3]=5, etc
81 45 = 34 + 8 + 3
83 = F[7] + F[4] + F[2]
84 = 10010100 1-bits at 7,4,2
85 The Wythoff array written in Zeckendorf base bits is
87 8 | 1000001 10000010 100000100 1000001000 10000010000
89 7 | 101001 1010010 10100100 101001000 1010010000
90 6 | 100101 1001010 10010100 100101000 1001010000
91 5 | 100001 1000010 10000100 100001000 1000010000
92 4 | 10101 101010 1010100 10101000 101010000
93 3 | 10001 100010 1000100 10001000 100010000
94 2 | 1001 10010 100100 1001000 10010000
95 1 | 101 1010 10100 101000 1010000
96 Y=0 | 1 10 100 1000 10000
97 +---------------------------------------------------
98 X=0 1 2 3 4
99 The X coordinate is the number of trailing zeros, or equivalently the
101 index of the lowest Fibonacci used in the sum. For example in the X=3
102 column all the N's there have F[3]=5 as their lowest term.
103 The Y coordinate is formed by removing the trailing "0100..00", ie. all
105 trailing zeros plus the "01" above them. For example,
106 N = 45 = Zeck 10010100
108 ^^^^ strip low zeros and "01" above them
109 Y = Zeck(1001) = F[3]+F[0] = 5+1 = 6
110 The Zeckendorf form never has consecutive "11" bits, because after
112 subtracting an F[k] the remainder is smaller than the next lower
113 F[k-1]. Numbers with no concecutive "11" bits are sometimes called the
114 fibbinary numbers (see Math::NumSeq::Fibbinary).
115 Stripping low zeros is similar to what the "PowerArray" does with low
117 zero digits in an ordinary base such as binary (see
118 Math::PlanePath::PowerArray). Doing it in the Zeckendorf base is like
119 taking out powers of the golden ratio phi=1.618.
120 Turn Sequence
122 The path turns
123 straight at N=2 and N=10
125 right N="...101" in Zeckendorf base
126 left otherwise
127 For example at N=12 the path turns to the right, since N=13 is on the
129 right hand side of the vector from N=11 to N=12. It's almost
130 180-degrees around and back, but on the right hand side.
131 4 | 12
133 3 |
134 2 |
135 1 | 11
136 Y=0 | 13
137 +--------------------
138 X=0 1 2 3 4 5
139 This happens because N=12 is Zeckendorf "10101" which ends "..101".
141 For such an ending N-1 is "..100" and N+1 is "..1000". So N+1 has more
142 trailing zeros and hence bigger X smaller Y than N-1 has. The way the
143 curve grows in a "concave" fashion means that therefore N+1 is on the
144 right-hand side.
145 | N N ending "..101"
147 |
148 | N+1 bigger X smaller Y
149 | N-1 than N-1
150 | N+1
151 +--------------------
152 Cases for N ending "..000", "..010" and "..100" can be worked through
154 to see that everything else turns left (or the initial N=2 and N=10 go
155 straight ahead).
156 On the Y axis all N values end "..01", with no trailing 0s. As noted
158 above stripping that "01" from N gives the Y coordinate. Those N
159 ending "..101" are therefore at Y coordinates which end "..1", meaning
160 "odd" Y in Zeckendorf base.
161 X,Y Start
163 Options "x_start => $x" and "y_start => $y" give a starting position
164 for the array. For example to start at X=1,Y=1
165 4 | 9 15 24 39 63 x_start => 1
167 3 | 6 10 16 26 42 y_start => 1
168 2 | 4 7 11 18 29
169 1 | 1 2 3 5 8
170 Y=0 |
171 +----------------------
172 X=0 1 2 3 4 5
173 This can be helpful to work in rows and columns numbered from 1 instead
175 of from 0. Numbering from X=1,Y=1 corresponds to the array in
176 Morrison's paper above.
177
179 See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
180 classes.
181 "$path = Math::PlanePath::WythoffArray->new ()"
183 "$path = Math::PlanePath::WythoffArray->new (x_start => $x, y_start =>
184 $y)"
185 Create and return a new path object. The default "x_start" and
186 "y_start" are 0.
187 "($x,$y) = $path->n_to_xy ($n)"
189 Return the X,Y coordinates of point number $n on the path. Points
190 begin at 1 and if "$n < 1" then the return is an empty list.
191 "$n = $path->xy_to_n ($x,$y)"
193 Return the N point number at coordinates "$x,$y". If "$x<0" or
194 "$y<0" (or the "x_start" or "y_start" options) then there's no N
195 and the return is "undef".
196 N values grow rapidly with $x. Pass in a bignum type such as
198 "Math::BigInt" for full precision.
199 "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
201 The returned range is exact, meaning $n_lo and $n_hi are the
202 smallest and biggest in the rectangle.
203
205 Rectangle to N Range
206 Within each row increasing X is increasing N, and in each column
207 increasing Y is increasing N. So in any rectangle the minimum N is in
208 the lower left corner and the maximum N is in the upper right corner.
209 | N max
211 | ----------+
212 | | ^ |
213 | | | |
214 | | ----> |
215 | +----------
216 | N min
217 +-------------------
218
220 The Wythoff array is in Sloane's Online Encyclopedia of Integer
221 Sequences in various forms,
222 <http://oeis.org/A035614> (etc)
224 x_start=0,y_start=0 (the defaults)
226 A035614 X, column numbered from 0
227 A191360 X-Y, the diagonal containing N
228 A019586 Y, the row containing N
229 A083398 max diagonal X+Y+1 for points 1 to N
230 x_start=1,y_start=1
232 A035612 X, column numbered from 1
233 A003603 Y, vertical para-budding sequence
234 A143299 Zeckendorf bit count in row Y
236 A185735 left-justified row addition
237 A186007 row subtraction
238 A173028 row multiples
239 A173027 row of n * Fibonacci numbers
240 A220249 row of n * Lucas numbers
241 A003622 N on Y axis, odd Zeckendorfs "..1"
243 A020941 N on X=Y diagonal
244 A139764 N dropped down to X axis, ie. N value on the X axis,
245 being lowest Fibonacci used in the Zeckendorf form
246 A000045 N on X axis, Fibonacci numbers skipping initial 0,1
248 A000204 N on Y=1 row, Lucas numbers skipping initial 1,3
249 A001950 N+1 of N on Y axis, anti-spectrum of phi
251 A022342 N not on Y axis, even Zeckendorfs "..0"
252 A000201 N+1 of N not on Y axis, spectrum of phi
253 A003849 bool 1,0 if N on Y axis or not, being the Fibonacci word
254 A035336 N in second column
256 A160997 total N along anti-diagonals X+Y=k
257 A188436 turn 1=right,0=left or straight, skip initial five 0s
259 A134860 N positions of right turns, Zeckendorf "..101"
260 A003622 Y coordinate of right turns, Zeckendorf "..1"
261 A114579 permutation N at transpose Y,X
263 A083412 permutation N by Diagonals from Y axis downwards
264 A035513 permutation N by Diagonals from X axis upwards
265 A064274 inverse permutation
266
268 Math::PlanePath, Math::PlanePath::PowerArray,
269 Math::PlanePath::FibonacciWordFractal
270 Math::NumSeq::Fibbinary, Math::NumSeq::Fibonacci,
272 Math::NumSeq::LucasNumbers, Math::Fibonacci, Math::Fibonacci::Phi
273 Ron Knott, "Generalising the Fibonacci Series",
275 <http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibGen.html#wythoff>
276 OEIS Classic Sequences, "The Wythoff Array and The Para-Fibonacci
278 Sequence", <http://oeis.org/classic.html>
279
281 <http://user42.tuxfamily.org/math-planepath/index.html>
282
284 Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
285 This file is part of Math-PlanePath.
287 Math-PlanePath is free software; you can redistribute it and/or modify
289 it under the terms of the GNU General Public License as published by
290 the Free Software Foundation; either version 3, or (at your option) any
291 later version.
292 Math-PlanePath is distributed in the hope that it will be useful, but
294 WITHOUT ANY WARRANTY; without even the implied warranty of
295 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
296 General Public License for more details.
297 You should have received a copy of the GNU General Public License along
299 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
300perl v5.30.0 2019-08-17 Math::PlanePath::WythoffArray(3)