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 Here F[] is indexed by bit positions starting 0 for the least
87 signficiant (which would be Fibonacci(2) in the usual Fibonacci
88 indexing).
89 The Wythoff array written in Zeckendorf base bits is
91 8 | 1000001 10000010 100000100 1000001000 10000010000
93 7 | 101001 1010010 10100100 101001000 1010010000
94 6 | 100101 1001010 10010100 100101000 1001010000
95 5 | 100001 1000010 10000100 100001000 1000010000
96 4 | 10101 101010 1010100 10101000 101010000
97 3 | 10001 100010 1000100 10001000 100010000
98 2 | 1001 10010 100100 1001000 10010000
99 1 | 101 1010 10100 101000 1010000
100 Y=0 | 1 10 100 1000 10000
101 +---------------------------------------------------
102 X=0 1 2 3 4
103 The X coordinate is the number of trailing zeros, or equivalently the
105 index of the lowest Fibonacci used in the sum. For example in the X=3
106 column all the N's there have F[3]=5 as their lowest term.
107 The Y coordinate is formed by removing the trailing "0100..00", ie. all
109 trailing zeros plus the "01" above them. For example,
110 N = 45 = Zeck 10010100
112 ^^^^ strip low zeros and "01" above them
113 Y = Zeck(1001) = F[3]+F[0] = 5+1 = 6
114 The Zeckendorf form never has consecutive "11" bits, because after
116 subtracting an F[k] the remainder is smaller than the next lower
117 F[k-1]. Numbers with no concecutive "11" bits are sometimes called the
118 fibbinary numbers (see Math::NumSeq::Fibbinary).
119 Stripping low zeros is similar to what the "PowerArray" does with low
121 zero digits in an ordinary base such as binary (see
122 Math::PlanePath::PowerArray). Doing it in the Zeckendorf base is like
123 taking out powers of the golden ratio phi=1.618.
124 Turn Sequence
126 The path turns
127 straight at N=2 and N=10
129 right N="...101" in Zeckendorf base
130 left otherwise
131 For example at N=12 the path turns to the right, since N=13 is on the
133 right hand side of the vector from N=11 to N=12. It's almost
134 180-degrees around and back, but on the right hand side.
135 4 | 12
137 3 |
138 2 |
139 1 | 11
140 Y=0 | 13
141 +--------------------
142 X=0 1 2 3 4 5
143 This happens because N=12 is Zeckendorf "10101" which ends "..101".
145 For such an ending N-1 is "..100" and N+1 is "..1000". So N+1 has more
146 trailing zeros and hence bigger X smaller Y than N-1 has. The way the
147 curve grows in a "concave" fashion means that therefore N+1 is on the
148 right-hand side.
149 | N N ending "..101"
151 |
152 | N+1 bigger X smaller Y
153 | N-1 than N-1
154 | N+1
155 +--------------------
156 Cases for N ending "..000", "..010" and "..100" can be worked through
158 to see that everything else turns left (or the initial N=2 and N=10 go
159 straight ahead).
160 On the Y axis all N values end "..01", with no trailing 0s. As noted
162 above stripping that "01" from N gives the Y coordinate. Those N
163 ending "..101" are therefore at Y coordinates which end "..1", meaning
164 "odd" Y in Zeckendorf base.
165 X,Y Start
167 Options "x_start => $x" and "y_start => $y" give a starting position
168 for the array. For example to start at X=1,Y=1
169 4 | 9 15 24 39 63 x_start => 1
171 3 | 6 10 16 26 42 y_start => 1
172 2 | 4 7 11 18 29
173 1 | 1 2 3 5 8
174 Y=0 |
175 +----------------------
176 X=0 1 2 3 4 5
177 This can be helpful to work in rows and columns numbered from 1 instead
179 of from 0. Numbering from X=1,Y=1 corresponds to the array in
180 Morrison's paper above.
181
183 See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
184 classes.
185 "$path = Math::PlanePath::WythoffArray->new ()"
187 "$path = Math::PlanePath::WythoffArray->new (x_start => $x, y_start =>
188 $y)"
189 Create and return a new path object. The default "x_start" and
190 "y_start" are 0.
191 "($x,$y) = $path->n_to_xy ($n)"
193 Return the X,Y coordinates of point number $n on the path. Points
194 begin at 1 and if "$n < 1" then the return is an empty list.
195 "$n = $path->xy_to_n ($x,$y)"
197 Return the N point number at coordinates "$x,$y". If "$x<0" or
198 "$y<0" (or the "x_start" or "y_start" options) then there's no N
199 and the return is "undef".
200 N values grow rapidly with $x. Pass in a bignum type such as
202 "Math::BigInt" for full precision.
203 "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
205 The returned range is exact, meaning $n_lo and $n_hi are the
206 smallest and biggest in the rectangle.
207
209 Rectangle to N Range
210 Within each row increasing X is increasing N, and in each column
211 increasing Y is increasing N. So in any rectangle the minimum N is in
212 the lower left corner and the maximum N is in the upper right corner.
213 | N max
215 | ----------+
216 | | ^ |
217 | | | |
218 | | ----> |
219 | +----------
220 | N min
221 +-------------------
222
224 The Wythoff array is in Sloane's Online Encyclopedia of Integer
225 Sequences in various forms,
226 <http://oeis.org/A035614> (etc)
228 x_start=0,y_start=0 (the defaults)
230 A035614 X, column numbered from 0
231 A191360 X-Y, the diagonal containing N
232 A019586 Y, the row containing N
233 A083398 max diagonal X+Y+1 for points 1 to N
234 x_start=1,y_start=1
236 A035612 X, column numbered from 1
237 A003603 Y, vertical para-budding sequence
238 A143299 Zeckendorf bit count in row Y
240 A185735 left-justified row addition
241 A186007 row subtraction
242 A173028 row multiples
243 A173027 row of n * Fibonacci numbers
244 A220249 row of n * Lucas numbers
245 A003622 N on Y axis, odd Zeckendorfs "..1"
247 A020941 N on X=Y diagonal
248 A139764 N dropped down to X axis, ie. N value on the X axis,
249 being lowest Fibonacci used in the Zeckendorf form
250 A000045 N on X axis, Fibonacci numbers skipping initial 0,1
252 A000204 N on Y=1 row, Lucas numbers skipping initial 1,3
253 A001950 N+1 of N on Y axis, anti-spectrum of phi
255 A022342 N not on Y axis, even Zeckendorfs "..0"
256 A000201 N+1 of N not on Y axis, spectrum of phi
257 A003849 bool 1,0 if N on Y axis or not, being the Fibonacci word
258 A035336 N in second column
260 A160997 total N along anti-diagonals X+Y=k
261 A188436 turn 1=right,0=left or straight, skip initial five 0s
263 A134860 N positions of right turns, Zeckendorf "..101"
264 A003622 Y coordinate of right turns, Zeckendorf "..1"
265 A114579 permutation N at transpose Y,X
267 A083412 permutation N by Diagonals from Y axis downwards
268 A035513 permutation N by Diagonals from X axis upwards
269 A064274 inverse permutation
270
272 Math::PlanePath, Math::PlanePath::PowerArray,
273 Math::PlanePath::FibonacciWordFractal
274 Math::NumSeq::Fibbinary, Math::NumSeq::Fibonacci,
276 Math::NumSeq::LucasNumbers, Math::Fibonacci, Math::Fibonacci::Phi
277 Ron Knott, "Generalising the Fibonacci Series",
279 <http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibGen.html#wythoff>
280 OEIS Classic Sequences, "The Wythoff Array and The Para-Fibonacci
282 Sequence", <http://oeis.org/classic.html>
283
285 <http://user42.tuxfamily.org/math-planepath/index.html>
286
288 Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021
289 Kevin Ryde
290 This file is part of Math-PlanePath.
292 Math-PlanePath is free software; you can redistribute it and/or modify
294 it under the terms of the GNU General Public License as published by
295 the Free Software Foundation; either version 3, or (at your option) any
296 later version.
297 Math-PlanePath is distributed in the hope that it will be useful, but
299 WITHOUT ANY WARRANTY; without even the implied warranty of
300 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
301 General Public License for more details.
302 You should have received a copy of the GNU General Public License along
304 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
305perl v5.34.0 2021-07-22 Math::PlanePath::WythoffArray(3)