.\" 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::PowerArray 3pm" .TH Math::PlanePath::PowerArray 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::PowerArray \-\- array by powers .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::PowerArray; \& my $path = Math::PlanePath::PowerArray\->new (radix => 2); \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This is a split of N into an odd part and power of 2, .PP .Vb 10 \& 12 | 25 50 100 200 400 800 1600 3200 6400 \& 11 | 23 46 92 184 368 736 1472 2944 5888 \& 10 | 21 42 84 168 336 672 1344 2688 5376 \& 9 | 19 38 76 152 304 608 1216 2432 4864 \& 8 | 17 34 68 136 272 544 1088 2176 4352 \& 7 | 15 30 60 120 240 480 960 1920 3840 \& 6 | 13 26 52 104 208 416 832 1664 3328 \& 5 | 11 22 44 88 176 352 704 1408 2816 \& 4 | 9 18 36 72 144 288 576 1152 2304 \& 3 | 7 14 28 56 112 224 448 896 1792 \& 2 | 5 10 20 40 80 160 320 640 1280 \& 1 | 3 6 12 24 48 96 192 384 768 \& Y=0 | 1 2 4 8 16 32 64 128 256 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 8 .Ve .PP For N=odd*2^k, the coordinates are X=k, Y=(odd\-1)/2. The X coordinate is how many factors of 2 can be divided out. The Y coordinate counts odd integers 1,3,5,7,etc as 0,1,2,3,etc. This is clearer by writing N values in binary, .PP .Vb 1 \& N values in binary \& \& 6 | 1101 11010 110100 1101000 11010000 110100000 \& 5 | 1011 10110 101100 1011000 10110000 101100000 \& 4 | 1001 10010 100100 1001000 10010000 100100000 \& 3 | 111 1110 11100 111000 1110000 11100000 \& 2 | 101 1010 10100 101000 1010000 10100000 \& 1 | 11 110 1100 11000 110000 1100000 \& Y=0 | 1 10 100 1000 10000 100000 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 .Ve .PP Column X=0 is all the odd numbers, column X=1 is exactly one low 0\-bit, and so on. .SS "Radix" .IX Subsection "Radix" The \f(CW\*(C`radix\*(C'\fR parameter can do the same dividing out in a higher base. For example radix 3 divides out factors of 3, .PP .Vb 1 \& radix => 3 \& \& 8 | 13 39 117 351 1053 3159 9477 28431 \& 7 | 11 33 99 297 891 2673 8019 24057 \& 6 | 10 30 90 270 810 2430 7290 21870 \& 5 | 8 24 72 216 648 1944 5832 17496 \& 4 | 7 21 63 189 567 1701 5103 15309 \& 3 | 5 15 45 135 405 1215 3645 10935 \& 2 | 4 12 36 108 324 972 2916 8748 \& 1 | 2 6 18 54 162 486 1458 4374 \& Y=0 | 1 3 9 27 81 243 729 2187 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 .Ve .PP N=1,3,9,27,etc on the X axis is the powers of 3. .PP N=1,2,4,5,7,etc on the Y axis is the integers N = 1or2 mod 3, ie. those not a multiple of 3. Notice if Y = 1or2 mod 4 then the N values in that row are all even, or if Y = 0or3 mod 4 then the N values are all odd. .PP .Vb 1 \& radix => 3, N values in ternary \& \& 6 | 101 1010 10100 101000 1010000 10100000 \& 5 | 22 220 2200 22000 220000 2200000 \& 4 | 21 210 2100 21000 210000 2100000 \& 3 | 12 120 1200 12000 120000 1200000 \& 2 | 11 110 1100 11000 110000 1100000 \& 1 | 2 20 200 2000 20000 200000 \& Y=0 | 1 10 100 1000 10000 100000 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 .Ve .SS "Boundary Length" .IX Subsection "Boundary Length" The points N=1 to N=2^k\-1 inclusive have a boundary length .PP .Vb 1 \& boundary = 2^k + 2k = 4,8,14,24,42,76,... (OEIS A100314) .Ve .PP For example N=1 to N=7 is .PP .Vb 9 \& +\-\-\-+ \& | 7 | \& + + \& | 5 | \& + +\-\-\-+ \& | 3 6 | \& + +\-\-\-+ \& | 1 2 4 | \& +\-\-\-+\-\-\-+\-\-\-+ .Ve .PP The height is the odd numbers, so 2^(k\-1). The width is the power k. So total boundary 2*height+2*width = 2^k + 2k. .PP If N=2^k is included then it's on the X axis and so add 2 for boundary = 2^k + 2k + 2 (\s-1OEIS\s0 2*A052968). .PP For another radix the calculation is similar .PP .Vb 1 \& boundary = 2 * (radix\-1) * radix^(k\-1) + 2*k .Ve .PP For example radix=3, N=1 to N=8 is .PP .Vb 6 \& 8 \& 7 \& 5 \& 4 \& 2 6 \& 1 3 .Ve .PP The height is the non-multiples of the radix, so (radix\-1)/radix * radix^k. The width is the power k. Total boundary = 2*height+2*width. .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::PowerArray\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::PowerArray\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::PowerArray->new ()" Create and return a new path object. .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 < 0\*(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 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 number type such as \&\f(CW\*(C`Math::BigInt\*(C'\fR to preserve 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. Within each column, increasing Y is increasing N. So in a rectangle the lower left corner is the minimum N and the upper right is the maximum N. .PP .Vb 8 \& | N max \& | \-\-\-\-\-\-\-\-\-\-+ \& | | ^ | \& | | | | \& | | \-\-\-\-> | \& | +\-\-\-\-\-\-\-\-\-\- \& | N min \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- .Ve .SS "N to Turn Left or Right" .IX Subsection "N to Turn Left or Right" The turn left or right is given by .PP .Vb 1 \& radix = 2 left at N==0 mod radix and N==1mod4, right otherwise \& \& radix >= 3 left at N==0 mod radix \& right at N=1 or radix\-1 mod radix \& straight otherwise .Ve .PP The points N!=0 mod radix are on the Y axis and those N==0 mod radix are off the axis. For that reason the turn at N==0 mod radix is to the left, .PP .Vb 5 \& | \& C\-\- \& \-\-\- \& A\-\-_\|_ \-\- point B is N=0 mod radix, \& | \-\-\- B turn left A\-B\-C is left .Ve .PP For radix>=3 the turns at A and C are to the right, since the point before A and after C is also on the Y axis. For radix>=4 there's of run of points on the Y axis which are straight. .PP For radix=2 the \*(L"B\*(R" case N=0 mod 2 applies, but for the A,C points in between the turn alternates left or right. .PP .Vb 7 \& 1\-\- N=1 mod 4 3\-\- N=3 mod 4 \& \e \-\- turn left \e \-\- turn right \& \e \-\- \e \-\- \& 2 \-\- 2 \-\- \& \-\- \-\- \& \-\- \-\- \& 0 4 .Ve .PP Points N=2 mod 4 are X=1 and Y=N/2 whereas N=0 mod 4 has 2 or more trailing 0 bits so X>1 and Y (etc) .RE .PP .Vb 3 \& radix=2 \& A007814 X coordinate, count low 0\-bits of N \& A006519 2^X \& \& A025480 Y coordinate of N\-1, ie. seq starts from N=0 \& A003602 Y+1, being k for which N=(2k\-1)*2^m \& A153733 2*Y of N\-1, strip low 1 bits \& A000265 2*Y+1, strip low 0 bits \& \& A094267 dX, change count low 0\-bits \& A050603 abs(dX) \& A108715 dY, change in Y coordinate \& \& A000079 N on X axis, powers 2^X \& A057716 N not on X axis, the non\-powers\-of\-2 \& \& A005408 N on Y axis (X=0), the odd numbers \& A003159 N in X=even columns, even trailing 0 bits \& A036554 N in X=odd columns \& \& A014480 N on X=Y diagonal, (2n+1)*2^n \& A118417 N on X=Y+1 diagonal, (2n\-1)*2^n \& (just below X=Y diagonal) \& \& A054582 permutation N by diagonals, upwards \& A209268 inverse \& A135764 permutation N by diagonals, downwards \& A249725 inverse \& A075300 permutation N\-1 by diagonals, upwards \& A117303 permutation N at transpose X,Y \& \& A100314 boundary length for N=1 to N=2^k\-1 inclusive \& being 2^k+2k \& A131831 same, after initial 1 \& A052968 half boundary length N=1 to N=2^k inclusive \& being 2^(k\-1)+k+1 \& \& radix=3 \& A007949 X coordinate, power\-of\-3 dividing N \& A000244 N on X axis, powers 3^X \& A001651 N on Y axis (X=0), not divisible by 3 \& A016051 N on Y column X=1 \& A051063 N on Y column X=1 \& A007417 N in X=even columns, even trailing 0 digits \& A145204 N in X=odd columns (extra initial 0) \& A141396 permutation, N by diagonals down from Y axis \& A191449 permutation, N by diagonals up from X axis \& A135765 odd N by diagonals, deletes the Y=1,2mod4 rows \& A000975 Y at N=2^k, being binary "10101..101" \& \& radix=4 \& A000302 N on X axis, powers 4^X \& \& radix=5 \& A112765 X coordinate, power\-of\-5 dividing N \& A000351 N on X axis, powers 5^X \& \& radix=6 \& A122841 X coordinate, power\-of\-6 dividing N \& \& radix=10 \& A011557 N on X axis, powers 10^X \& A067251 N on Y axis, not a multiple of 10 \& A151754 Y coordinate of N=2^k, being floor(2^k*9/10) .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::WythoffArray, Math::PlanePath::ZOrderCurve .PP David M. Bradley \*(L"Counting Ordered Pairs\*(R", Mathematics Magazine, volume 83, number 4, October 2010, page 302, \s-1DOI 10.4169/002557010X528032.\s0 .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 .