1Math::PlanePath::WythofUfsAerrraCyo(n3t)ributed Perl DocMuamtehn:t:aPtliaonnePath::WythoffArray(3)
2
3
4

NAME

6       Math::PlanePath::WythoffArray -- table of Fibonacci recurrences
7

SYNOPSIS

9        use Math::PlanePath::WythoffArray;
10        my $path = Math::PlanePath::WythoffArray->new;
11        my ($x, $y) = $path->n_to_xy (123);
12

DESCRIPTION

14       This path is the Wythoff array by David R. Morrison
15
16           "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
21       It's an array of Fibonacci recurrences which positions each N according
22       to Zeckendorf base trailing zeros.
23
24            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
43       All rows have the Fibonacci style recurrence
44
45           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
48       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
51       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
54           phi = (sqrt(5)+1)/2
55           spectrum(k) = floor(phi*k)
56           N on Y axis = Y + spectrum(Y+1)
57
58           Eg. Y=5  N=5+floor((5+1)*phi)=14
59
60       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
65       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
69       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
74   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
80           Fibonacci numbers F[0]=1, F[1]=2, F[2]=3, F[3]=5, etc
81
82           45 = 34 + 8 + 3
83              = F[7] + F[4] + F[2]
84              = 10010100        1-bits at 7,4,2
85
86       The Wythoff array written in Zeckendorf base bits is
87
88             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
100       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
104       The Y coordinate is formed by removing the trailing "0100..00", ie. all
105       trailing zeros plus the "01" above them.  For example,
106
107           N = 45 = Zeck 10010100
108                             ^^^^ strip low zeros and "01" above them
109           Y = Zeck(1001) = F[3]+F[0] = 5+1 = 6
110
111       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
116       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
121   Turn Sequence
122       The path turns
123
124           straight     at N=2 and N=10
125           right        N="...101" in Zeckendorf base
126           left         otherwise
127
128       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
132             4  | 12
133             3  |
134             2  |
135             1  |       11
136           Y=0  |                13
137                +--------------------
138                 X=0  1  2  3  4  5
139
140       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
146           | N                        N ending "..101"
147           |
148           |                          N+1 bigger X smaller Y
149           |      N-1                     than N-1
150           |               N+1
151           +--------------------
152
153       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
157       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
162   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
166             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
174       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

FUNCTIONS

179       See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
180       classes.
181
182       "$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
188       "($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
192       "$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
197           N values grow rapidly with $x.  Pass in a bignum type such as
198           "Math::BigInt" for full precision.
199
200       "($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

FORMULAS

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
210           |               N max
211           |     ----------+
212           |    |  ^       |
213           |    |  |       |
214           |    |   ---->  |
215           |    +----------
216           |   N min
217           +-------------------
218

OEIS

220       The Wythoff array is in Sloane's Online Encyclopedia of Integer
221       Sequences in various forms,
222
223           <http://oeis.org/A035614> (etc)
224
225           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
231           x_start=1,y_start=1
232             A035612     X, column numbered from 1
233             A003603     Y, vertical para-budding sequence
234
235             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
242           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
247           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
250           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
255           A035336     N in second column
256           A160997     total N along anti-diagonals X+Y=k
257
258           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
262           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

SEE ALSO

268       Math::PlanePath, Math::PlanePath::PowerArray,
269       Math::PlanePath::FibonacciWordFractal
270
271       Math::NumSeq::Fibbinary, Math::NumSeq::Fibonacci,
272       Math::NumSeq::LucasNumbers, Math::Fibonacci, Math::Fibonacci::Phi
273
274       Ron Knott, "Generalising the Fibonacci Series",
275       <http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibGen.html#wythoff>
276
277       OEIS Classic Sequences, "The Wythoff Array and The Para-Fibonacci
278       Sequence", <http://oeis.org/classic.html>
279

HOME PAGE

281       <http://user42.tuxfamily.org/math-planepath/index.html>
282

LICENSE

284       Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
285
286       This file is part of Math-PlanePath.
287
288       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
293       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
298       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/>.
300
301
302
303perl v5.30.1                      2020-01-30  Math::PlanePath::WythoffArray(3)
Impressum