Install Now
Math::PlanePath::PowerArray -- array by powers
Contents
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
BoundaryLength
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.
Formulas
RectangletoNRange
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
+-------------------
NtoTurnLeftorRight
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<N/2.
N mod 4 turn
------- ------
0 left for radix=2
1 left
2 left
3 right
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.
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
<http://www.gnu.org/licenses/>.
perl v5.32.0 2021-01-23 Math::PlanePath::PowerArray(3pm)
Name
Math::PlanePath::PowerArray -- array by powers
Oeis
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include
<http://oeis.org/A007814> (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.
<http://www.math.umaine.edu/~bradley/papers/JStor002557010X528032.pdf>
Synopsis
use Math::PlanePath::PowerArray;
my $path = Math::PlanePath::PowerArray->new (radix => 2);
my ($x, $y) = $path->n_to_xy (123);
PNG Icons
