.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  \*(C+ will
.\" give a nicer C++.  Capital omega is used to do unbreakable dashes and
.\" therefore won't be available.  \*(C` and \*(C' expand to `' in nroff,
.\" nothing in troff, for use with C<>.
.tr \(*W-
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is turned on, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.nr rF 0
.if \n(.g .if rF .nr rF 1
.if (\n(rF:(\n(.g==0)) \{
.    if \nF \{
.        de IX
.        tm Index:\\$1\t\\n%\t"\\$2"
..
.        if !\nF==2 \{
.            nr % 0
.            nr F 2
.        \}
.    \}
.\}
.rr rF
.\"
.\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
.\" Fear.  Run.  Save yourself.  No user-serviceable parts.
.    \" fudge factors for nroff and troff
.if n \{\
.    ds #H 0
.    ds #V .8m
.    ds #F .3m
.    ds #[ \f1
.    ds #] \fP
.\}
.if t \{\
.    ds #H ((1u-(\\\\n(.fu%2u))*.13m)
.    ds #V .6m
.    ds #F 0
.    ds #[ \&
.    ds #] \&
.\}
.    \" simple accents for nroff and troff
.if n \{\
.    ds ' \&
.    ds ` \&
.    ds ^ \&
.    ds , \&
.    ds ~ ~
.    ds /
.\}
.if t \{\
.    ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
.    ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
.    ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
.    ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
.    ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
.    ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
.\}
.    \" troff and (daisy-wheel) nroff accents
.ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
.ds 8 \h'\*(#H'\(*b\h'-\*(#H'
.ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
.ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
.ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
.ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
.ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
.ds ae a\h'-(\w'a'u*4/10)'e
.ds Ae A\h'-(\w'A'u*4/10)'E
.    \" corrections for vroff
.if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
.if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
.    \" for low resolution devices (crt and lpr)
.if \n(.H>23 .if \n(.V>19 \
\{\
.    ds : e
.    ds 8 ss
.    ds o a
.    ds d- d\h'-1'\(ga
.    ds D- D\h'-1'\(hy
.    ds th \o'bp'
.    ds Th \o'LP'
.    ds ae ae
.    ds Ae AE
.\}
.rm #[ #] #H #V #F C
.\" ========================================================================
.\"
.IX Title "Math::PlanePath::WythoffArray 3pm"
.TH Math::PlanePath::WythoffArray 3pm "2014-06-14" "perl v5.20.1" "User Contributed Perl Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH "NAME"
Math::PlanePath::WythoffArray \-\- table of Fibonacci recurrences
.SH "SYNOPSIS"
.IX Header "SYNOPSIS"
.Vb 3
\& use Math::PlanePath::WythoffArray;
\& my $path = Math::PlanePath::WythoffArray\->new;
\& my ($x, $y) = $path\->n_to_xy (123);
.Ve
.SH "DESCRIPTION"
.IX Header "DESCRIPTION"
This path is the Wythoff array by David
R. Morrison
.IX Xref "Morrison, David R. Wythoff array"
.Sp
.RS 4
\&\*(L"A Stolarsky Array of Wythoff Pairs\*(R", in Collection of Manuscripts Related
to the Fibonacci Sequence, pages 134 to 136, The Fibonacci Association,
1980.  <http://www.math.ucsb.edu/~drm/papers/stolarsky.pdf>
.RE
.PP
It's an array of Fibonacci recurrences which positions each N according to
Zeckendorf base trailing zeros.
.PP
.Vb 10
\&     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
.Ve
.PP
All rows have the Fibonacci style recurrence
.PP
.Vb 2
\&    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
.Ve
.PP
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.
.IX Xref "Fibonacci numbers Lucas numbers"
.PP
Y axis N=1,4,6,9,12,etc is the \*(L"spectrum\*(R" of the golden
ratio, meaning its multiples rounded down to an integer.
.IX Xref "Golden Ratio"
.PP
.Vb 3
\&    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
.Ve
.PP
The recurrence in each row starts as if the row was preceded by two values Y
and 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.
.PP
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.
.PP
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.
.SS "Zeckendorf Base"
.IX Subsection "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
.IX Xref "Zeckendorf Base"
.PP
.Vb 1
\&    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
.Ve
.PP
The Wythoff array written in Zeckendorf base bits is
.PP
.Vb 11
\&      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
.Ve
.PP
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.
.PP
The Y coordinate is formed by removing the trailing \*(L"0100..00\*(R", ie. all
trailing zeros plus the \*(L"01\*(R" above them.  For example,
.PP
.Vb 3
\&    N = 45 = Zeck 10010100
\&                      ^^^^ strip low zeros and "01" above them
\&    Y = Zeck(1001) = F[3]+F[0] = 5+1 = 6
.Ve
.PP
The Zeckendorf form never has consecutive \*(L"11\*(R" bits, because after
subtracting an F[k] the remainder is smaller than the next lower F[k\-1].
Numbers with no concecutive \*(L"11\*(R" bits are sometimes called the fibbinary
numbers (see Math::NumSeq::Fibbinary).
.PP
Stripping low zeros is similar to what the \f(CW\*(C`PowerArray\*(C'\fR 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.
.SS "Turn Sequence"
.IX Subsection "Turn Sequence"
The path turns
.PP
.Vb 3
\&    straight     at N=2 and N=10
\&    right        N="...101" in Zeckendorf base
\&    left         otherwise
.Ve
.PP
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.
.PP
.Vb 7
\&      4  | 12
\&      3  | 
\&      2  | 
\&      1  |       11   
\&    Y=0  |                13
\&         +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-
\&          X=0  1  2  3  4  5
.Ve
.PP
This happens because N=12 is Zeckendorf \*(L"10101\*(R" which ends \*(L"..101\*(R".  For
such an ending N\-1 is \*(L"..100\*(R" and N+1 is \*(L"..1000\*(R".  So N+1 has more trailing
zeros and hence bigger X smaller Y than N\-1 has.  The way the curve grows in
a \*(L"concave\*(R" fashion means that therefore N+1 is on the right-hand side.
.PP
.Vb 6
\&    | N                        N ending "..101"
\&    |  
\&    |                          N+1 bigger X smaller Y
\&    |      N\-1                     than N\-1
\&    |               N+1   
\&    +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-
.Ve
.PP
Cases for N ending \*(L"..000\*(R", \*(L"..010\*(R" and \*(L"..100\*(R" can be worked through to see
that everything else turns left (or the initial N=2 and N=10 go straight
ahead).
.PP
On the Y axis all N values end \*(L"..01\*(R", with no trailing 0s.  As noted above
stripping that \*(L"01\*(R" from N gives the Y coordinate.  Those N ending \*(L"..101\*(R"
are therefore at Y coordinates which end \*(L"..1\*(R", meaning \*(L"odd\*(R" Y in
Zeckendorf base.
.SS "X,Y Start"
.IX Subsection "X,Y Start"
Options \f(CW\*(C`x_start => $x\*(C'\fR and \f(CW\*(C`y_start => $y\*(C'\fR give a starting
position for the array.  For example to start at X=1,Y=1
.PP
.Vb 7
\&      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
.Ve
.PP
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.
.SH "FUNCTIONS"
.IX Header "FUNCTIONS"
See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for the behaviour common to all path
classes.
.ie n .IP """$path = Math::PlanePath::WythoffArray\->new ()""" 4
.el .IP "\f(CW$path = Math::PlanePath::WythoffArray\->new ()\fR" 4
.IX Item "$path = Math::PlanePath::WythoffArray->new ()"
.PD 0
.ie n .IP """$path = Math::PlanePath::WythoffArray\->new (x_start => $x, y_start => $y)""" 4
.el .IP "\f(CW$path = Math::PlanePath::WythoffArray\->new (x_start => $x, y_start => $y)\fR" 4
.IX Item "$path = Math::PlanePath::WythoffArray->new (x_start => $x, y_start => $y)"
.PD
Create and return a new path object.  The default \f(CW\*(C`x_start\*(C'\fR and \f(CW\*(C`y_start\*(C'\fR
are 0.
.ie n .IP """($x,$y) = $path\->n_to_xy ($n)""" 4
.el .IP "\f(CW($x,$y) = $path\->n_to_xy ($n)\fR" 4
.IX Item "($x,$y) = $path->n_to_xy ($n)"
Return the X,Y coordinates of point number \f(CW$n\fR on the path.  Points begin
at 1 and if \f(CW\*(C`$n < 1\*(C'\fR then the return is an empty list.
.ie n .IP """$n = $path\->xy_to_n ($x,$y)""" 4
.el .IP "\f(CW$n = $path\->xy_to_n ($x,$y)\fR" 4
.IX Item "$n = $path->xy_to_n ($x,$y)"
Return the N point number at coordinates \f(CW\*(C`$x,$y\*(C'\fR.  If \f(CW\*(C`$x<0\*(C'\fR or
\&\f(CW\*(C`$y<0\*(C'\fR (or the \f(CW\*(C`x_start\*(C'\fR or \f(CW\*(C`y_start\*(C'\fR options) then there's no N and
the return is \f(CW\*(C`undef\*(C'\fR.
.Sp
N values grow rapidly with \f(CW$x\fR.  Pass in a bignum type such as
\&\f(CW\*(C`Math::BigInt\*(C'\fR for full precision.
.ie n .IP """($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)""" 4
.el .IP "\f(CW($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)\fR" 4
.IX Item "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
The returned range is exact, meaning \f(CW$n_lo\fR and \f(CW$n_hi\fR are the smallest
and biggest in the rectangle.
.SH "FORMULAS"
.IX Header "FORMULAS"
.SS "Rectangle to N Range"
.IX Subsection "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.
.PP
.Vb 8
\&    |               N max
\&    |     \-\-\-\-\-\-\-\-\-\-+
\&    |    |  ^       |
\&    |    |  |       |
\&    |    |   \-\-\-\->  |
\&    |    +\-\-\-\-\-\-\-\-\-\-
\&    |   N min
\&    +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-
.Ve
.SH "OEIS"
.IX Header "OEIS"
The Wythoff array is in Sloane's Online Encyclopedia of Integer Sequences
in various forms,
.Sp
.RS 4
<http://oeis.org/A035614> (etc)
.RE
.PP
.Vb 5
\&    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
.Ve
.SH "SEE ALSO"
.IX Header "SEE ALSO"
Math::PlanePath,
Math::PlanePath::PowerArray,
Math::PlanePath::FibonacciWordFractal
.PP
Math::NumSeq::Fibbinary,
Math::NumSeq::Fibonacci,
Math::NumSeq::LucasNumbers,
Math::Fibonacci,
Math::Fibonacci::Phi
.PP
Ron Knott, \*(L"Generalising the Fibonacci Series\*(R",
<http://www.maths.surrey.ac.uk/hosted\-sites/R.Knott/Fibonacci/fibGen.html#wythoff>
.PP
\&\s-1OEIS\s0 Classic Sequences, \*(L"The Wythoff Array and The Para-Fibonacci Sequence\*(R",
<http://oeis.org/classic.html>
.SH "HOME PAGE"
.IX Header "HOME PAGE"
<http://user42.tuxfamily.org/math\-planepath/index.html>
.SH "LICENSE"
.IX Header "LICENSE"
Copyright 2012, 2013, 2014 Kevin Ryde
.PP
This file is part of Math-PlanePath.
.PP
Math-PlanePath is free software; you can redistribute it and/or modify it
under the terms of the \s-1GNU\s0 General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
.PP
Math-PlanePath is distributed in the hope that it will be useful, but
\&\s-1WITHOUT ANY WARRANTY\s0; without even the implied warranty of \s-1MERCHANTABILITY\s0
or \s-1FITNESS FOR A PARTICULAR PURPOSE. \s0 See the \s-1GNU\s0 General Public License for
more details.
.PP
You should have received a copy of the \s-1GNU\s0 General Public License along with
Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.