++ed by:
EGOR BHANN

2 PAUSE users

Kevin Ryde

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 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.

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

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

http://user42.tuxfamily.org/math-planepath/index.html

LICENSE

Copyright 2012, 2013, 2014 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/>.