--- name: "Math::PlanePath::PowerArray" section: "3pm" platform: "linux" package: "libmath-planepath-perl" version: "129-1" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/Math::PlanePath::PowerArray" --- # Math::PlanePath::PowerArray(3pm) ## NAME Math::PlanePath::PowerArray -- array by powers ## SYNOPSIS ``` use Math::PlanePath::PowerArray; my $path = Math::PlanePath::PowerArray->new (radix => 2); my ($x, $y) = $path->n_to_xy (123); ``` ## DESCRIPTION This is a split of N into an odd part and power of 2, ``` 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 ``` 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, ``` 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 ``` Column X=0 is all the odd numbers, column X=1 is exactly one low 0-bit, and so on. ### Radix The `"radix"` parameter can do the same dividing out in a higher base. For example radix 3 divides out factors of 3, ``` 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 ``` N=1,3,9,27,etc on the X axis is the powers of 3. 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. ``` 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 ``` ### Boundary Length The points N=1 to N=2^k-1 inclusive have a boundary length ``` boundary = 2^k + 2k = 4,8,14,24,42,76,... (OEIS A100314) ``` For example N=1 to N=7 is ``` +---+ | 7 | + + | 5 | + +---+ | 3 6 | + +---+ | 1 2 4 | +---+---+---+ ``` 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. If N=2^k is included then it's on the X axis and so add 2 for boundary = 2^k + 2k + 2 (OEIS 2\*A052968). For another radix the calculation is similar ``` boundary = 2 * (radix-1) * radix^(k-1) + 2*k ``` For example radix=3, N=1 to N=8 is ``` 8 7 5 4 2 6 1 3 ``` 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. ## FUNCTIONS See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes. - "$path = Math::PlanePath::PowerArray-\>new ()" Create and return a new path object. - "($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 < 0"` 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"` then there's no N and the return is `"undef"`. N values grow rapidly with `$x`. Pass in a number type such as `"Math::BigInt"` to preserve 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. 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. ``` | N max | ----------+ | | ^ | | | | | | | ----> | | +---------- | N min +------------------- ``` ### N to Turn Left or Right The turn left or right is given by ``` 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 ``` 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, ``` | C-- --- A--__ -- point B is N=0 mod radix, | --- B turn left A-B-C is left ``` 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. For radix=2 the "B" case N=0 mod 2 applies, but for the A,C points in between the turn alternates left or right. ``` 1-- N=1 mod 4 3-- N=3 mod 4 \ -- turn left \ -- turn right \ -- \ -- 2 -- 2 -- -- -- -- -- 0 4 ``` 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) ``` 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) ``` ## SEE ALSO Math::PlanePath, Math::PlanePath::WythoffArray, Math::PlanePath::ZOrderCurve David M. Bradley "Counting Ordered Pairs", Mathematics Magazine, volume 83, number 4, October 2010, page 302, DOI 10.4169/002557010X528032. \ ## 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 \.