.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.40) .\" .\" 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 >0, 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 .\" ======================================================================== .\" .IX Title "Math::PlanePath::WythoffArray 3pm" .TH Math::PlanePath::WythoffArray 3pm "2021-01-23" "perl v5.32.0" "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. .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,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 Here F[] is indexed by bit positions starting 0 for the least signficiant (which would be \fBFibonacci\fR\|(2) in the usual Fibonacci indexing). .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 (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", .PP \&\s-1OEIS\s0 Classic Sequences, \*(L"The Wythoff Array and The Para-Fibonacci Sequence\*(R", .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021 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 .