1Math::PlanePath::PowerAUrsreary(C3o)ntributed Perl DocumMeanttha:t:iPolnanePath::PowerArray(3)
2
6 Math::PlanePath::PowerArray -- array by powers
7
9 use Math::PlanePath::PowerArray;
10 my $path = Math::PlanePath::PowerArray->new (radix => 2);
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This is a split of N into an odd part and power of 2,
15 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 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 N values in binary
38 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 Column X=0 is all the odd numbers, column X=1 is exactly one low 0-bit,
50 and so on.
51 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 radix => 3
57 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 N=1,3,9,27,etc on the X axis is the powers of 3.
71 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 radix => 3, N values in ternary
78 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 Boundary Length
90 The points N=1 to N=2^k-1 inclusive have a boundary length
91 boundary = 2^k + 2k = 4,8,14,24,42,76,... (OEIS A100314)
93 For example N=1 to N=7 is
95 +---+
97 | 7 |
98 + +
99 | 5 |
100 + +---+
101 | 3 6 |
102 + +---+
103 | 1 2 4 |
104 +---+---+---+
105 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 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 For another radix the calculation is similar
113 boundary = 2 * (radix-1) * radix^(k-1) + 2*k
115 For example radix=3, N=1 to N=8 is
117 8
119 7
120 5
121 4
122 2 6
123 1 3
124 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
129 See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
130 classes.
131 "$path = Math::PlanePath::PowerArray->new ()"
133 Create and return a new path object.
134 "($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 "$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 N values grow rapidly with $x. Pass in a number type such as
144 "Math::BigInt" to preserve precision.
145 "($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
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 | N max
157 | ----------+
158 | | ^ |
159 | | | |
160 | | ----> |
161 | +----------
162 | N min
163 +-------------------
164 N to Turn Left or Right
166 The turn left or right is given by
167 radix = 2 left at N==0 mod radix and N==1mod4, right otherwise
169 radix >= 3 left at N==0 mod radix
171 right at N=1 or radix-1 mod radix
172 straight otherwise
173 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 |
179 C--
180 ---
181 A--__ -- point B is N=0 mod radix,
182 | --- B turn left A-B-C is left
183 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 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 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 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 N mod 4 turn
203 ------- ------
204 0 left for radix=2
205 1 left
206 2 left
207 3 right
208
210 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
211 this path include
212 <http://oeis.org/A007814> (etc)
214 radix=2
216 A007814 X coordinate, count low 0-bits of N
217 A006519 2^X
218 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 A094267 dX, change count low 0-bits
225 A050603 abs(dX)
226 A108715 dY, change in Y coordinate
227 A000079 N on X axis, powers 2^X
229 A057716 N not on X axis, the non-powers-of-2
230 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 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 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 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 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 radix=4
266 A000302 N on X axis, powers 4^X
267 radix=5
269 A112765 X coordinate, power-of-5 dividing N
270 A000351 N on X axis, powers 5^X
271 radix=6
273 A122841 X coordinate, power-of-6 dividing N
274 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
281 Math::PlanePath, Math::PlanePath::WythoffArray,
282 Math::PlanePath::ZOrderCurve
283 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
289 <http://user42.tuxfamily.org/math-planepath/index.html>
290
292 Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021
293 Kevin Ryde
294 This file is part of Math-PlanePath.
296 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 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 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/>.
309perl v5.34.0 2021-07-22 Math::PlanePath::PowerArray(3)