| Math::PlanePath::WythoffArray(3) | User Contributed Perl Documentation | Math::PlanePath::WythoffArray(3) |
NAME¶
Math::PlanePath::WythoffArray -- table of Fibonacci recurrences
SYNOPSIS¶
use Math::PlanePath::WythoffArray; my $path = Math::PlanePath::WythoffArray->new; my ($x, $y) = $path->n_to_xy (123);
DESCRIPTION¶
This path is the Wythoff array by David R. Morrison
It's an array of Fibonacci recurrences which positions each N according to Zeckendorf base trailing zeros.
15 | 40 65 105 170 275 445 720 1165 1885 3050 4935
14 | 38 62 100 162 262 424 686 1110 1796 2906 4702
13 | 35 57 92 149 241 390 631 1021 1652 2673 4325
12 | 33 54 87 141 228 369 597 966 1563 2529 4092
11 | 30 49 79 128 207 335 542 877 1419 2296 3715
10 | 27 44 71 115 186 301 487 788 1275 2063 3338
9 | 25 41 66 107 173 280 453 733 1186 1919 3105
8 | 22 36 58 94 152 246 398 644 1042 1686 2728
7 | 19 31 50 81 131 212 343 555 898 1453 2351
6 | 17 28 45 73 118 191 309 500 809 1309 2118
5 | 14 23 37 60 97 157 254 411 665 1076 1741
4 | 12 20 32 52 84 136 220 356 576 932 1508
3 | 9 15 24 39 63 102 165 267 432 699 1131
2 | 6 10 16 26 42 68 110 178 288 466 754
1 | 4 7 11 18 29 47 76 123 199 322 521
Y=0 | 1 2 3 5 8 13 21 34 55 89 144
+-------------------------------------------------------
X=0 1 2 3 4 5 6 7 8 9 10
All rows have the Fibonacci style recurrence
W(X+1) = W(X) + W(X-1)
eg. X=4,Y=2 is N=42=16+26, sum of the two values to its left
X axis N=1,2,3,5,8,etc is the Fibonacci numbers. The row Y=1 above them N=4,7,11,18,etc is the Lucas numbers.
Y axis N=1,4,6,9,12,etc is the "spectrum" of the golden ratio, meaning its multiples rounded down to an integer.
phi = (sqrt(5)+1)/2
spectrum(k) = floor(phi*k)
N on Y axis = Y + spectrum(Y+1)
Eg. Y=5 N=5+floor((5+1)*phi)=14
The recurrence in each row starts as if the row was preceded by two values Y,spectrum(Y+1) which can be thought of adding to be Y+spectrum(Y+1) on the Y axis, then Y+2*spectrum(Y+1) in the X=1 column, etc.
If the first two values in a row have a common factor then that factor remains in all subsequent sums. For example the Y=2 row starts with two even numbers N=6,N=10 so all N values in the row are even.
Every N from 1 upwards occurs precisely once in the table. The recurrence means that in each row N grows roughly as a power phi^X, the same as the Fibonacci numbers. This means they become large quite quickly.
Zeckendorf Base¶
The N values are arranged according to trailing zero bits when N is represented in the Zeckendorf base. The Zeckendorf base expresses N as a sum of Fibonacci numbers, choosing at each stage the largest possible Fibonacci. For example
Fibonacci numbers F[0]=1, F[1]=2, F[2]=3, F[3]=5, etc
45 = 34 + 8 + 3
= F[7] + F[4] + F[2]
= 10010100 1-bits at 7,4,2
Here F[] is indexed by bit positions starting 0 for the least signficiant (which would be Fibonacci(2) in the usual Fibonacci indexing).
The Wythoff array written in Zeckendorf base bits is
8 | 1000001 10000010 100000100 1000001000 10000010000
7 | 101001 1010010 10100100 101001000 1010010000
6 | 100101 1001010 10010100 100101000 1001010000
5 | 100001 1000010 10000100 100001000 1000010000
4 | 10101 101010 1010100 10101000 101010000
3 | 10001 100010 1000100 10001000 100010000
2 | 1001 10010 100100 1001000 10010000
1 | 101 1010 10100 101000 1010000
Y=0 | 1 10 100 1000 10000
+---------------------------------------------------
X=0 1 2 3 4
The X coordinate is the number of trailing zeros, or equivalently the index of the lowest Fibonacci used in the sum. For example in the X=3 column all the N's there have F[3]=5 as their lowest term.
The Y coordinate is formed by removing the trailing "0100..00", ie. all trailing zeros plus the "01" above them. For example,
N = 45 = Zeck 10010100
^^^^ strip low zeros and "01" above them
Y = Zeck(1001) = F[3]+F[0] = 5+1 = 6
The Zeckendorf form never has consecutive "11" bits, because after subtracting an F[k] the remainder is smaller than the next lower F[k-1]. Numbers with no concecutive "11" bits are sometimes called the fibbinary numbers (see Math::NumSeq::Fibbinary).
Stripping low zeros is similar to what the "PowerArray" does with low zero digits in an ordinary base such as binary (see Math::PlanePath::PowerArray). Doing it in the Zeckendorf base is like taking out powers of the golden ratio phi=1.618.
Turn Sequence¶
The path turns
straight at N=2 and N=10
right N="...101" in Zeckendorf base
left otherwise
For example at N=12 the path turns to the right, since N=13 is on the right hand side of the vector from N=11 to N=12. It's almost 180-degrees around and back, but on the right hand side.
4 | 12
3 |
2 |
1 | 11
Y=0 | 13
+--------------------
X=0 1 2 3 4 5
This happens because N=12 is Zeckendorf "10101" which ends "..101". For such an ending N-1 is "..100" and N+1 is "..1000". So N+1 has more trailing zeros and hence bigger X smaller Y than N-1 has. The way the curve grows in a "concave" fashion means that therefore N+1 is on the right-hand side.
| N N ending "..101"
|
| N+1 bigger X smaller Y
| N-1 than N-1
| N+1
+--------------------
Cases for N ending "..000", "..010" and "..100" can be worked through to see that everything else turns left (or the initial N=2 and N=10 go straight ahead).
On the Y axis all N values end "..01", with no trailing 0s. As noted above stripping that "01" from N gives the Y coordinate. Those N ending "..101" are therefore at Y coordinates which end "..1", meaning "odd" Y in Zeckendorf base.
X,Y Start¶
Options "x_start => $x" and "y_start => $y" give a starting position for the array. For example to start at X=1,Y=1
4 | 9 15 24 39 63 x_start => 1
3 | 6 10 16 26 42 y_start => 1
2 | 4 7 11 18 29
1 | 1 2 3 5 8
Y=0 |
+----------------------
X=0 1 2 3 4 5
This can be helpful to work in rows and columns numbered from 1 instead of from 0. Numbering from X=1,Y=1 corresponds to the array in Morrison's paper above.
FUNCTIONS¶
See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.
- "$path = Math::PlanePath::WythoffArray->new ()"
- "$path = Math::PlanePath::WythoffArray->new (x_start => $x, y_start => $y)"
- Create and return a new path object. The default "x_start" and "y_start" are 0.
- "($x,$y) = $path->n_to_xy ($n)"
- Return the X,Y coordinates of point number $n on the path. Points begin at 1 and if "$n < 1" then the return is an empty list.
- "$n = $path->xy_to_n ($x,$y)"
- Return the N point number at coordinates
"$x,$y". If
"$x<0" or
"$y<0" (or the
"x_start" or
"y_start" options) then there's no N and
the return is "undef".
N values grow rapidly with $x. Pass in a bignum type such as "Math::BigInt" for full precision.
- "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
- The returned range is exact, meaning $n_lo and $n_hi are the smallest and biggest in the rectangle.
FORMULAS¶
Rectangle to N Range¶
Within each row increasing X is increasing N, and in each column increasing Y is increasing N. So in any rectangle the minimum N is in the lower left corner and the maximum N is in the upper right corner.
| N max
| ----------+
| | ^ |
| | | |
| | ----> |
| +----------
| N min
+-------------------
OEIS¶
The Wythoff array is in Sloane's Online Encyclopedia of Integer Sequences in various forms,
x_start=0,y_start=0 (the defaults)
A035614 X, column numbered from 0
A191360 X-Y, the diagonal containing N
A019586 Y, the row containing N
A083398 max diagonal X+Y+1 for points 1 to N
x_start=1,y_start=1
A035612 X, column numbered from 1
A003603 Y, vertical para-budding sequence
A143299 Zeckendorf bit count in row Y
A185735 left-justified row addition
A186007 row subtraction
A173028 row multiples
A173027 row of n * Fibonacci numbers
A220249 row of n * Lucas numbers
A003622 N on Y axis, odd Zeckendorfs "..1"
A020941 N on X=Y diagonal
A139764 N dropped down to X axis, ie. N value on the X axis,
being lowest Fibonacci used in the Zeckendorf form
A000045 N on X axis, Fibonacci numbers skipping initial 0,1
A000204 N on Y=1 row, Lucas numbers skipping initial 1,3
A001950 N+1 of N on Y axis, anti-spectrum of phi
A022342 N not on Y axis, even Zeckendorfs "..0"
A000201 N+1 of N not on Y axis, spectrum of phi
A003849 bool 1,0 if N on Y axis or not, being the Fibonacci word
A035336 N in second column
A160997 total N along anti-diagonals X+Y=k
A188436 turn 1=right,0=left or straight, skip initial five 0s
A134860 N positions of right turns, Zeckendorf "..101"
A003622 Y coordinate of right turns, Zeckendorf "..1"
A114579 permutation N at transpose Y,X
A083412 permutation N by Diagonals from Y axis downwards
A035513 permutation N by Diagonals from X axis upwards
A064274 inverse permutation
SEE ALSO¶
Math::PlanePath, Math::PlanePath::PowerArray, Math::PlanePath::FibonacciWordFractal
Math::NumSeq::Fibbinary, Math::NumSeq::Fibonacci, Math::NumSeq::LucasNumbers, Math::Fibonacci, Math::Fibonacci::Phi
Ron Knott, "Generalising the Fibonacci Series", <http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibGen.html#wythoff>
OEIS Classic Sequences, "The Wythoff Array and The Para-Fibonacci Sequence", <http://oeis.org/classic.html>
HOME PAGE¶
LICENSE¶
Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021 Kevin Ryde
This file is part of Math-PlanePath.
Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
| 2021-01-20 | perl v5.40.0 |