1Math::PlanePath::DigitGUrsoeurpsC(o3n)tributed Perl DocuMmaetnht:a:tPiloannePath::DigitGroups(3)
2
6 Math::PlanePath::DigitGroups -- X,Y digits grouped by zeros
7
9 use Math::PlanePath::DigitGroups;
10 my $path = Math::PlanePath::DigitGroups->new (radix => 2);
12 my ($x, $y) = $path->n_to_xy (123);
13
15 This path splits an N into X,Y by digit groups separated by a 0. The
16 default is binary so for example
17 N = 110111001011
19 is split into groups with a leading high 0 bit, and those groups then
21 go to X and Y alternately,
22 N = 11 0111 0 01 011
24 X Y X Y X
25 X = 11 0 011 = 110011
27 Y = 0111 01 = 11101
28 The result is a one-to-one mapping between numbers N>=0 and pairs
30 X>=0,Y>=0.
31 The default binary is
33 11 | 38 77 86 155 166 173 182 311 550 333 342 347
35 10 | 72 145 148 291 168 297 300 583 328 337 340 595
36 9 | 66 133 138 267 162 277 282 535 322 325 330 555
37 8 | 128 257 260 515 272 521 524 1031 320 545 548 1043
38 7 | 14 29 46 59 142 93 110 119 526 285 302 187
39 6 | 24 49 52 99 88 105 108 199 280 177 180 211
40 5 | 18 37 42 75 82 85 90 151 274 165 170 171
41 4 | 32 65 68 131 80 137 140 263 160 161 164 275
42 3 | 6 13 22 27 70 45 54 55 262 141 150 91
43 2 | 8 17 20 35 40 41 44 71 136 81 84 83
44 1 | 2 5 10 11 34 21 26 23 130 69 74 43
45 Y=0 | 0 1 4 3 16 9 12 7 64 33 36 19
46 +-------------------------------------------------------------
47 X=0 1 2 3 4 5 6 7 8 9 10 11
48 N=0,1,4,3,16,9,etc along the X axis is X with zero bits doubled. For
50 example X=9 is binary 1001, double up the zero bits to 100001 for N=33
51 at X=9,Y=0. This is because in the digit groups Y=0 so when X is
52 grouped by its zero bits there's an extra 0 from Y in between each
53 group.
54 Similarly N=0,2,8,6,32,etc along the Y axis is Y with zero bits
56 doubled, plus an extra zero bit at the low end coming from the first
57 X=0 group. For example Y=9 is again binary 1001, doubled zeros to
58 100001, and an extra zero at the low end 1000010 is N=66 at X=0,Y=9.
59 Radix
61 The "radix => $r" option selects a different base for the digit split.
62 For example radix 5 gives
63 radix => 5
65 12 | 60 301 302 303 304 685 1506 1507 1508 1509 1310 1511
67 11 | 55 276 277 278 279 680 1381 1382 1383 1384 1305 1386
68 10 | 250 1251 1252 1253 1254 1275 6256 6257 6258 6259 1300 6261
69 9 | 45 226 227 228 229 670 1131 1132 1133 1134 1295 1136
70 8 | 40 201 202 203 204 665 1006 1007 1008 1009 1290 1011
71 7 | 35 176 177 178 179 660 881 882 883 884 1285 886
72 6 | 30 151 152 153 154 655 756 757 758 759 1280 761
73 5 | 125 626 627 628 629 650 3131 3132 3133 3134 675 3136
74 4 | 20 101 102 103 104 145 506 507 508 509 270 511
75 3 | 15 76 77 78 79 140 381 382 383 384 265 386
76 2 | 10 51 52 53 54 135 256 257 258 259 260 261
77 1 | 5 26 27 28 29 130 131 132 133 134 255 136
78 Y=0 | 0 1 2 3 4 25 6 7 8 9 50 11
79 +-----------------------------------------------------------
80 X=0 1 2 3 4 5 6 7 8 9 10 11
81 Real Line and Plane
83 This split is inspired by the digit grouping in the proof by Julius
84 König that the real line is the same cardinality as the plane.
85 (Cantor's original proof was a "ZOrderCurve" style digit interleaving.)
86 In König's proof a bijection between interval n=(0,1) and pairs
88 x=(0,1),y=(0,1) is made by taking groups of digits stopping at a non-
89 zero. Non-terminating fractions like 0.49999... are chosen over
90 terminating 0.5000... so there's always infinitely many non-zero digits
91 going downwards. For the integer form here the groupings are digit
92 going upwards and there's infinitely many zero digits above the top,
93 hence the grouping by zeros instead of non-zeros.
94
96 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
97 classes.
98 "$path = Math::PlanePath::DigitGroups->new ()"
100 "$path = Math::PlanePath::DigitGroups->new (radix => $r)"
101 Create and return a new path object. The optional "radix"
102 parameter gives the base for digit splitting (the default is
103 binary, radix 2).
104 "($x,$y) = $path->n_to_xy ($n)"
106 Return the X,Y coordinates of point number $n on the path. Points
107 begin at 0 and if "$n < 0" then the return is an empty list.
108
110 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
111 this path include
112 <http://oeis.org/A084471> (etc)
114 radix=2 (the default)
116 A084471 N on X axis, bit 0->00
117 A084472 N on X axis, in binary
118 A060142 N on X axis, sorted into ascending order
119
121 Math::PlanePath, Math::PlanePath::ZOrderCurve,
122 Math::PlanePath::PowerArray
123
125 <http://user42.tuxfamily.org/math-planepath/index.html>
126
128 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
129 Kevin Ryde
130 This file is part of Math-PlanePath.
132 Math-PlanePath is free software; you can redistribute it and/or modify
134 it under the terms of the GNU General Public License as published by
135 the Free Software Foundation; either version 3, or (at your option) any
136 later version.
137 Math-PlanePath is distributed in the hope that it will be useful, but
139 WITHOUT ANY WARRANTY; without even the implied warranty of
140 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
141 General Public License for more details.
142 You should have received a copy of the GNU General Public License along
144 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
145perl v5.38.0 2023-07-20 Math::PlanePath::DigitGroups(3)