Math::PlanePath::DigitGroups(3pm) | User Contributed Perl Documentation | Math::PlanePath::DigitGroups(3pm) |
Math::PlanePath::DigitGroups -- X,Y digits grouped by zeros
use Math::PlanePath::DigitGroups; my $path = Math::PlanePath::DigitGroups->new (radix => 2); my ($x, $y) = $path->n_to_xy (123);
This path splits an N into X,Y by digit groups separated by a 0. The default is binary so for example
N = 110111001011
is split into groups with a leading high 0 bit, and those groups then go to X and Y alternately,
N = 11 0111 0 01 011 X Y X Y X X = 11 0 011 = 110011 Y = 0111 01 = 11101
The result is a one-to-one mapping between numbers N>=0 and pairs X>=0,Y>=0.
The default binary is
11 | 38 77 86 155 166 173 182 311 550 333 342 347 10 | 72 145 148 291 168 297 300 583 328 337 340 595 9 | 66 133 138 267 162 277 282 535 322 325 330 555 8 | 128 257 260 515 272 521 524 1031 320 545 548 1043 7 | 14 29 46 59 142 93 110 119 526 285 302 187 6 | 24 49 52 99 88 105 108 199 280 177 180 211 5 | 18 37 42 75 82 85 90 151 274 165 170 171 4 | 32 65 68 131 80 137 140 263 160 161 164 275 3 | 6 13 22 27 70 45 54 55 262 141 150 91 2 | 8 17 20 35 40 41 44 71 136 81 84 83 1 | 2 5 10 11 34 21 26 23 130 69 74 43 Y=0 | 0 1 4 3 16 9 12 7 64 33 36 19 +------------------------------------------------------------- X=0 1 2 3 4 5 6 7 8 9 10 11
N=0,1,4,3,16,9,etc along the X axis is X with zero bits doubled. For example X=9 is binary 1001, double up the zero bits to 100001 for N=33 at X=9,Y=0. This is because in the digit groups Y=0 so when X is grouped by its zero bits there's an extra 0 from Y in between each group.
Similarly N=0,2,8,6,32,etc along the Y axis is Y with zero bits doubled, plus an extra zero bit at the low end coming from the first X=0 group. For example Y=9 is again binary 1001, doubled zeros to 100001, and an extra zero at the low end 1000010 is N=66 at X=0,Y=9.
The "radix => $r" option selects a different base for the digit split. For example radix 5 gives
radix => 5 12 | 60 301 302 303 304 685 1506 1507 1508 1509 1310 1511 11 | 55 276 277 278 279 680 1381 1382 1383 1384 1305 1386 10 | 250 1251 1252 1253 1254 1275 6256 6257 6258 6259 1300 6261 9 | 45 226 227 228 229 670 1131 1132 1133 1134 1295 1136 8 | 40 201 202 203 204 665 1006 1007 1008 1009 1290 1011 7 | 35 176 177 178 179 660 881 882 883 884 1285 886 6 | 30 151 152 153 154 655 756 757 758 759 1280 761 5 | 125 626 627 628 629 650 3131 3132 3133 3134 675 3136 4 | 20 101 102 103 104 145 506 507 508 509 270 511 3 | 15 76 77 78 79 140 381 382 383 384 265 386 2 | 10 51 52 53 54 135 256 257 258 259 260 261 1 | 5 26 27 28 29 130 131 132 133 134 255 136 Y=0 | 0 1 2 3 4 25 6 7 8 9 50 11 +----------------------------------------------------------- X=0 1 2 3 4 5 6 7 8 9 10 11
This split is inspired by the digit grouping in the proof by Julius König that the real line is the same cardinality as the plane. (Cantor's original proof was a "ZOrderCurve" style digit interleaving.)
In König's proof a bijection between interval n=(0,1) and pairs x=(0,1),y=(0,1) is made by taking groups of digits stopping at a non-zero. Non-terminating fractions like 0.49999... are chosen over terminating 0.5000... so there's always infinitely many non-zero digits going downwards. For the integer form here the groupings are digit going upwards and there's infinitely many zero digits above the top, hence the grouping by zeros instead of non-zeros.
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include
radix=2 (the default) A084471 N on X axis, bit 0->00 A084472 N on X axis, in binary A060142 N on X axis, sorted into ascending order
Math::PlanePath, Math::PlanePath::ZOrderCurve, Math::PlanePath::PowerArray
<http://user42.tuxfamily.org/math-planepath/index.html>
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 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/>.
2021-01-23 | perl v5.32.0 |