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       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
90       The Wythoff array written in Zeckendorf base bits is
91
92             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
104       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
108       The Y coordinate is formed by removing the trailing "0100..00", ie. all
109       trailing zeros plus the "01" above them.  For example,
110
111           N = 45 = Zeck 10010100
112                             ^^^^ strip low zeros and "01" above them
113           Y = Zeck(1001) = F[3]+F[0] = 5+1 = 6
114
115       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
120       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
125   Turn Sequence
126       The path turns
127
128           straight     at N=2 and N=10
129           right        N="...101" in Zeckendorf base
130           left         otherwise
131
132       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
136             4  | 12
137             3  |
138             2  |
139             1  |       11
140           Y=0  |                13
141                +--------------------
142                 X=0  1  2  3  4  5
143
144       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
150           | N                        N ending "..101"
151           |
152           |                          N+1 bigger X smaller Y
153           |      N-1                     than N-1
154           |               N+1
155           +--------------------
156
157       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
161       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
166   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
170             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
178       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

FUNCTIONS

183       See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
184       classes.
185
186       "$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
192       "($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
196       "$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
201           N values grow rapidly with $x.  Pass in a bignum type such as
202           "Math::BigInt" for full precision.
203
204       "($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

FORMULAS

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
214           |               N max
215           |     ----------+
216           |    |  ^       |
217           |    |  |       |
218           |    |   ---->  |
219           |    +----------
220           |   N min
221           +-------------------
222

OEIS

224       The Wythoff array is in Sloane's Online Encyclopedia of Integer
225       Sequences in various forms,
226
227           <http://oeis.org/A035614> (etc)
228
229           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
235           x_start=1,y_start=1
236             A035612     X, column numbered from 1
237             A003603     Y, vertical para-budding sequence
238
239             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
246           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
251           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
254           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
259           A035336     N in second column
260           A160997     total N along anti-diagonals X+Y=k
261
262           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
266           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

SEE ALSO

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

HOME PAGE

285       <http://user42.tuxfamily.org/math-planepath/index.html>
286

LICENSE

288       Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021
289       Kevin Ryde
290
291       This file is part of Math-PlanePath.
292
293       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
298       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
303       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/>.
305
306
307
308perl v5.32.1                      2021-01-27  Math::PlanePath::WythoffArray(3)
Impressum