1Math::PlanePath::PowerAUrsreary(C3o)ntributed Perl DocumMeanttha:t:iPolnanePath::PowerArray(3)
2
3
4

NAME

6       Math::PlanePath::PowerArray -- array by powers
7

SYNOPSIS

9        use Math::PlanePath::PowerArray;
10        my $path = Math::PlanePath::PowerArray->new (radix => 2);
11        my ($x, $y) = $path->n_to_xy (123);
12

DESCRIPTION

14       This is a split of N into an odd part and power of 2,
15
16            12  |   25    50   100   200   400   800  1600  3200  6400
17            11  |   23    46    92   184   368   736  1472  2944  5888
18            10  |   21    42    84   168   336   672  1344  2688  5376
19             9  |   19    38    76   152   304   608  1216  2432  4864
20             8  |   17    34    68   136   272   544  1088  2176  4352
21             7  |   15    30    60   120   240   480   960  1920  3840
22             6  |   13    26    52   104   208   416   832  1664  3328
23             5  |   11    22    44    88   176   352   704  1408  2816
24             4  |    9    18    36    72   144   288   576  1152  2304
25             3  |    7    14    28    56   112   224   448   896  1792
26             2  |    5    10    20    40    80   160   320   640  1280
27             1  |    3     6    12    24    48    96   192   384   768
28           Y=0  |    1     2     4     8    16    32    64   128   256
29                +------------------------------------------------------
30                   X=0     1     2     3     4     5     6     7     8
31
32       For N=odd*2^k, the coordinates are X=k, Y=(odd-1)/2.  The X coordinate
33       is how many factors of 2 can be divided out.  The Y coordinate counts
34       odd integers 1,3,5,7,etc as 0,1,2,3,etc.  This is clearer by writing N
35       values in binary,
36
37           N values in binary
38
39             6  |  1101     11010    110100   1101000  11010000 110100000
40             5  |  1011     10110    101100   1011000  10110000 101100000
41             4  |  1001     10010    100100   1001000  10010000 100100000
42             3  |   111      1110     11100    111000   1110000  11100000
43             2  |   101      1010     10100    101000   1010000  10100000
44             1  |    11       110      1100     11000    110000   1100000
45           Y=0  |     1        10       100      1000     10000    100000
46                +---------------------------------------------------------
47                    X=0         1         2         3         4         5
48
49       Column X=0 is all the odd numbers, column X=1 is exactly one low 0-bit,
50       and so on.
51
52   Radix
53       The "radix" parameter can do the same dividing out in a higher base.
54       For example radix 3 divides out factors of 3,
55
56            radix => 3
57
58             8  |   13    39   117   351  1053  3159  9477 28431
59             7  |   11    33    99   297   891  2673  8019 24057
60             6  |   10    30    90   270   810  2430  7290 21870
61             5  |    8    24    72   216   648  1944  5832 17496
62             4  |    7    21    63   189   567  1701  5103 15309
63             3  |    5    15    45   135   405  1215  3645 10935
64             2  |    4    12    36   108   324   972  2916  8748
65             1  |    2     6    18    54   162   486  1458  4374
66           Y=0  |    1     3     9    27    81   243   729  2187
67                +------------------------------------------------
68                   X=0     1     2     3     4     5     6     7
69
70       N=1,3,9,27,etc on the X axis is the powers of 3.
71
72       N=1,2,4,5,7,etc on the Y axis is the integers N = 1or2 mod 3, ie. those
73       not a multiple of 3.  Notice if Y = 1or2 mod 4 then the N values in
74       that row are all even, or if Y = 0or3 mod 4 then the N values are all
75       odd.
76
77           radix => 3,  N values in ternary
78
79             6  |   101     1010    10100   101000  1010000 10100000
80             5  |    22      220     2200    22000   220000  2200000
81             4  |    21      210     2100    21000   210000  2100000
82             3  |    12      120     1200    12000   120000  1200000
83             2  |    11      110     1100    11000   110000  1100000
84             1  |     2       20      200     2000    20000   200000
85           Y=0  |     1       10      100     1000    10000   100000
86                +----------------------------------------------------
87                    X=0        1        2        3        4        5
88
89   Boundary Length
90       The points N=1 to N=2^k-1 inclusive have a boundary length
91
92           boundary = 2^k + 2k   = 4,8,14,24,42,76,...   (OEIS A100314)
93
94       For example N=1 to N=7 is
95
96           +---+
97           | 7 |
98           +   +
99           | 5 |
100           +   +---+
101           | 3   6 |
102           +       +---+
103           | 1   2   4 |
104           +---+---+---+
105
106       The height is the odd numbers, so 2^(k-1).  The width is the power k.
107       So total boundary 2*height+2*width = 2^k + 2k.
108
109       If N=2^k is included then it's on the X axis and so add 2 for boundary
110       = 2^k + 2k + 2 (OEIS 2*A052968).
111
112       For another radix the calculation is similar
113
114           boundary = 2 * (radix-1) * radix^(k-1) + 2*k
115
116       For example radix=3, N=1 to N=8 is
117
118           8
119           7
120           5
121           4
122           2  6
123           1  3
124
125       The height is the non-multiples of the radix, so (radix-1)/radix *
126       radix^k.  The width is the power k.  Total boundary = 2*height+2*width.
127

FUNCTIONS

129       See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
130       classes.
131
132       "$path = Math::PlanePath::PowerArray->new ()"
133           Create and return a new path object.
134
135       "($x,$y) = $path->n_to_xy ($n)"
136           Return the X,Y coordinates of point number $n on the path.  Points
137           begin at 1 and if "$n < 0" then the return is an empty list.
138
139       "$n = $path->xy_to_n ($x,$y)"
140           Return the N point number at coordinates "$x,$y".  If "$x<0" or
141           "$y<0" then there's no N and the return is "undef".
142
143           N values grow rapidly with $x.  Pass in a number type such as
144           "Math::BigInt" to preserve precision.
145
146       "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
147           The returned range is exact, meaning $n_lo and $n_hi are the
148           smallest and biggest in the rectangle.
149

FORMULAS

151   Rectangle to N Range
152       Within each row, increasing X is increasing N.  Within each column,
153       increasing Y is increasing N.  So in a rectangle the lower left corner
154       is the minimum N and the upper right is the maximum N.
155
156           |               N max
157           |     ----------+
158           |    |  ^       |
159           |    |  |       |
160           |    |   ---->  |
161           |    +----------
162           |   N min
163           +-------------------
164
165   N to Turn Left or Right
166       The turn left or right is given by
167
168           radix = 2     left at N==0 mod radix and N==1mod4, right otherwise
169
170           radix >= 3    left at N==0 mod radix
171                         right at N=1 or radix-1 mod radix
172                         straight otherwise
173
174       The points N!=0 mod radix are on the Y axis and those N==0 mod radix
175       are off the axis.  For that reason the turn at N==0 mod radix is to the
176       left,
177
178           |
179           C--
180              ---
181           A--__ --        point B is N=0 mod radix,
182           |    --- B      turn left A-B-C is left
183
184       For radix>=3 the turns at A and C are to the right, since the point
185       before A and after C is also on the Y axis.  For radix>=4 there's of
186       run of points on the Y axis which are straight.
187
188       For radix=2 the "B" case N=0 mod 2 applies, but for the A,C points in
189       between the turn alternates left or right.
190
191           1--     N=1 mod 4             3--      N=3 mod 4
192            \ --   turn left              \ --    turn right
193             \  --                         \  --
194              2   --                        2   --
195                    --                            --
196                      --                            --
197                        0                             4
198
199       Points N=2 mod 4 are X=1 and Y=N/2 whereas N=0 mod 4 has 2 or more
200       trailing 0 bits so X>1 and Y<N/2.
201
202           N mod 4      turn
203           -------     ------
204              0        left         for radix=2
205              1         left
206              2        left
207              3         right
208

OEIS

210       Entries in Sloane's Online Encyclopedia of Integer Sequences related to
211       this path include
212
213           <http://oeis.org/A007814> (etc)
214
215           radix=2
216             A007814    X coordinate, count low 0-bits of N
217             A006519    2^X
218
219             A025480    Y coordinate of N-1, ie. seq starts from N=0
220             A003602    Y+1, being k for which N=(2k-1)*2^m
221             A153733    2*Y of N-1, strip low 1 bits
222             A000265    2*Y+1, strip low 0 bits
223
224             A094267    dX, change count low 0-bits
225             A050603    abs(dX)
226             A108715    dY, change in Y coordinate
227
228             A000079    N on X axis, powers 2^X
229             A057716    N not on X axis, the non-powers-of-2
230
231             A005408    N on Y axis (X=0), the odd numbers
232             A003159    N in X=even columns, even trailing 0 bits
233             A036554    N in X=odd columns
234
235             A014480    N on X=Y diagonal, (2n+1)*2^n
236             A118417    N on X=Y+1 diagonal, (2n-1)*2^n
237                          (just below X=Y diagonal)
238
239             A054582    permutation N by diagonals, upwards
240             A209268      inverse
241             A135764    permutation N by diagonals, downwards
242             A249725      inverse
243             A075300    permutation N-1 by diagonals, upwards
244             A117303    permutation N at transpose X,Y
245
246             A100314    boundary length for N=1 to N=2^k-1 inclusive
247                          being  2^k+2k
248             A131831      same, after initial 1
249             A052968    half boundary length N=1 to N=2^k inclusive
250                          being  2^(k-1)+k+1
251
252           radix=3
253             A007949    X coordinate, power-of-3 dividing N
254             A000244    N on X axis, powers 3^X
255             A001651    N on Y axis (X=0), not divisible by 3
256             A016051    N on Y column X=1
257             A051063    N on Y column X=1
258             A007417    N in X=even columns, even trailing 0 digits
259             A145204    N in X=odd columns (extra initial 0)
260             A141396    permutation, N by diagonals down from Y axis
261             A191449    permutation, N by diagonals up from X axis
262             A135765    odd N by diagonals, deletes the Y=1,2mod4 rows
263             A000975    Y at N=2^k, being binary "10101..101"
264
265           radix=4
266             A000302    N on X axis, powers 4^X
267
268           radix=5
269             A112765    X coordinate, power-of-5 dividing N
270             A000351    N on X axis, powers 5^X
271
272           radix=6
273             A122841    X coordinate, power-of-6 dividing N
274
275           radix=10
276             A011557    N on X axis, powers 10^X
277             A067251    N on Y axis, not a multiple of 10
278             A151754    Y coordinate of N=2^k, being floor(2^k*9/10)
279

SEE ALSO

281       Math::PlanePath, Math::PlanePath::WythoffArray,
282       Math::PlanePath::ZOrderCurve
283
284       David M. Bradley "Counting Ordered Pairs", Mathematics Magazine, volume
285       83, number 4, October 2010, page 302, DOI 10.4169/002557010X528032.
286       <http://www.math.umaine.edu/~bradley/papers/JStor002557010X528032.pdf>
287

HOME PAGE

289       <http://user42.tuxfamily.org/math-planepath/index.html>
290

LICENSE

292       Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021
293       Kevin Ryde
294
295       This file is part of Math-PlanePath.
296
297       Math-PlanePath is free software; you can redistribute it and/or modify
298       it under the terms of the GNU General Public License as published by
299       the Free Software Foundation; either version 3, or (at your option) any
300       later version.
301
302       Math-PlanePath is distributed in the hope that it will be useful, but
303       WITHOUT ANY WARRANTY; without even the implied warranty of
304       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
305       General Public License for more details.
306
307       You should have received a copy of the GNU General Public License along
308       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
309
310
311
312perl v5.34.0                      2021-07-22    Math::PlanePath::PowerArray(3)
Impressum