.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.40) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is >0, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{\ . if \nF \{\ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{\ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" ======================================================================== .\" .IX Title "Math::PlanePath::CornerReplicate 3pm" .TH Math::PlanePath::CornerReplicate 3pm "2021-01-23" "perl v5.32.0" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::PlanePath::CornerReplicate \-\- replicating U parts .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::CornerReplicate; \& my $path = Math::PlanePath::CornerReplicate\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This path is a self-similar replicating corner fill with 2x2 blocks. It's sometimes called a \*(L"U order\*(R" since the base N=0 to N=3 is like a \*(L"U\*(R" (sideways). .IX Xref "U Order" .PP .Vb 10 \& 7 | 63\-\-62 59\-\-58 47\-\-46 43\-\-42 \& | | | | | \& 6 | 60\-\-61 56\-\-57 44\-\-45 40\-\-41 \& | | | \& 5 | 51\-\-50 55\-\-54 35\-\-34 39\-\-38 \& | | | | | \& 4 | 48\-\-49 52\-\-53 32\-\-33 36\-\-37 \& | | \& 3 | 15\-\-14 11\-\-10 31\-\-30 27\-\-26 \& | | | | | \& 2 | 12\-\-13 8\-\- 9 28\-\-29 24\-\-25 \& | | | \& 1 | 3\-\- 2 7\-\- 6 19\-\-18 23\-\-22 \& | | | | | \& Y=0 | 0\-\- 1 4\-\- 5 16\-\-17 20\-\-21 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 .Ve .PP The pattern is the initial N=0 to N=3 section, .PP .Vb 9 \& +\-\-\-\-\-\-\-+\-\-\-\-\-\-\-+ \& | | | \& | 3 | 2 | \& | | | \& +\-\-\-\-\-\-\-+\-\-\-\-\-\-\-+ \& | | | \& | 0 | 1 | \& | | | \& +\-\-\-\-\-\-\-+\-\-\-\-\-\-\-+ .Ve .PP It repeats as 2x2 blocks arranged in the same pattern, then 4x4 blocks, etc. There's no rotations or reflections within sub-parts. .PP X axis N=0,1,4,5,16,17,etc is all the integers which use only digits 0 and 1 in base 4. For example N=17 is 101 in base 4. .PP Y axis N=0,3,12,15,48,etc is all the integers which use only digits 0 and 3 in base 4. For example N=51 is 303 in base 4. .PP The X=Y diagonal N=0,2,8,10,32,34,etc is all the integers which use only digits 0 and 2 in base 4. .PP The X axis is the same as the \f(CW\*(C`ZOrderCurve\*(C'\fR. The Y axis here is the X=Y diagonal of the \f(CW\*(C`ZOrderCurve\*(C'\fR, and conversely the X=Y diagonal here is the Y axis of the \f(CW\*(C`ZOrderCurve\*(C'\fR. .PP The N value at a given X,Y is converted to or from the \f(CW\*(C`ZOrderCurve\*(C'\fR by transforming base\-4 digit values 2<\->3. This can be done by a bitwise \*(L"X xor Y\*(R". When Y has a 1\-bit the xor swaps 2<\->3 in N. .PP .Vb 2 \& ZOrder X = CRep X xor CRep Y \& ZOrder Y = CRep Y \& \& CRep X = ZOrder X xor ZOrder Y \& CRep Y = ZOrder Y .Ve .PP See Math::PlanePath::LCornerReplicate for a rotating corner form. .SS "Level Ranges" .IX Subsection "Level Ranges" A given replication extends to .PP .Vb 3 \& Nlevel = 4^level \- 1 \& 0 <= X < 2^level \& 0 <= Y < 2^level .Ve .SS "Hamming Distance" .IX Subsection "Hamming Distance" The Hamming distance between two integers X and Y is the number of bit positions where the two values differ when written in binary. In this corner replicate each bit-pair of N becomes a bit of X and a bit of Y, .PP .Vb 6 \& N X Y \& \-\-\-\-\-\- \-\-\- \-\-\- \& 0 = 00 0 0 \& 1 = 01 1 0 <\- difference 1 bit \& 2 = 10 1 1 \& 3 = 11 0 1 <\- difference 1 bit .Ve .PP So the Hamming distance is the number of base4 bit-pairs of N which are 01 or 11. Counting bit positions from 0 for least significant bit, this is the 1\-bits in even positions, .PP .Vb 2 \& HammingDist(X,Y) = count 1\-bits at even bit positions in N \& = 0,1,0,1, 1,2,1,2, 0,1,0,1, 1,2,1,2, ... (A139351) .Ve .SH "FUNCTIONS" .IX Header "FUNCTIONS" See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for behaviour common to all path classes. .ie n .IP """$path = Math::PlanePath::CornerReplicate\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::CornerReplicate\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::CornerReplicate->new ()" Create and return a new path object. .ie n .IP """($x,$y) = $path\->n_to_xy ($n)""" 4 .el .IP "\f(CW($x,$y) = $path\->n_to_xy ($n)\fR" 4 .IX Item "($x,$y) = $path->n_to_xy ($n)" Return the X,Y coordinates of point number \f(CW$n\fR on the path. Points begin at 0 and if \f(CW\*(C`$n < 0\*(C'\fR then the return is an empty list. .ie n .IP """($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)" The returned range is exact, meaning \f(CW$n_lo\fR and \f(CW$n_hi\fR are the smallest and biggest in the rectangle. .SS "Level Methods" .IX Subsection "Level Methods" .ie n .IP """($n_lo, $n_hi) = $path\->level_to_n_range($level)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->level_to_n_range($level)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->level_to_n_range($level)" Return \f(CW\*(C`(0, 4**$level \- 1)\*(C'\fR. .SH "FORMULAS" .IX Header "FORMULAS" .SS "N to dX,dY" .IX Subsection "N to dX,dY" The change dX,dY is given by N in base 4 count trailing 3s and the digit above those trailing 3s. .PP .Vb 2 \& N = ...[d]333...333 base 4 \& \e\-\-exp\-\-/ .Ve .PP When N to N+1 crosses between 4^k blocks it goes as follows. Within a block the pattern is the same, since there's no rotations or transposes etc. .PP .Vb 4 \& N, N+1 X Y dX dY dSum dDiffXY \& \-\-\-\-\-\-\-\- \-\-\-\-\- \-\-\-\-\-\-\- \-\-\-\-\- \-\-\-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\-\- \& 033..33 0 2^k\-1 2^k \-(2^k\-1) +1 2*2^k\-1 \& 100..00 2^k 0 \& \& 133..33 2^k 2^k\-1 0 +1 +1 \-1 \& 200..00 2^k 2^k \& \& 133..33 2^k 2*2^k\-1 \-2^k 1\-2^k \-(2^k\-1) \-1 \& 200..00 0 2^k \& \& 133..33 0 2*2^k\-1 2*2^k \-(2*2^k\-1) +1 4*2^k\-1 \& 200..00 2*2^k 0 .Ve .PP It can be noted dSum=dX+dY the change in X+Y is at most +1, taking values 1, \&\-1, \-3, \-7, \-15, etc. The crossing from block 2 to 3 drops back, such as at N=47=\*(L"233\*(R" to N=48=\*(L"300\*(R". Everywhere else it advances by +1 anti-diagonal. .PP The difference dDiffXY=dX\-dY the change in X\-Y decreases at most \-1, taking similar values \-1, 1, 3, 7, 15, etc but in a different order to dSum. .SH "OEIS" .IX Header "OEIS" This path is in Sloane's Online Encyclopedia of Integer Sequences as .Sp .RS 4 (etc) .RE .PP .Vb 3 \& A059906 Y coordinate \& A059905 X xor Y, being ZOrderCurve X \& A139351 HammingDist(X,Y), count 1\-bits at even positions in N \& \& A000695 N on X axis, base 4 digits 0,1 only \& A001196 N on Y axis, base 4 digits 0,3 only \& A062880 N on diagonal, base 4 digits 0,2 only \& A163241 permutation base\-4 flip 2<\->3, \& converts N to ZOrderCurve N, and back \& \& A048647 permutation N at transpose Y,X \& base4 digits 1<\->3 .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::LTiling, Math::PlanePath::SquareReplicate, Math::PlanePath::GosperReplicate, Math::PlanePath::ZOrderCurve, Math::PlanePath::GrayCode .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde .PP This file is part of Math-PlanePath. .PP Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the \s-1GNU\s0 General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. .PP Math-PlanePath is distributed in the hope that it will be useful, but \&\s-1WITHOUT ANY WARRANTY\s0; without even the implied warranty of \s-1MERCHANTABILITY\s0 or \s-1FITNESS FOR A PARTICULAR PURPOSE.\s0 See the \s-1GNU\s0 General Public License for more details. .PP You should have received a copy of the \s-1GNU\s0 General Public License along with Math-PlanePath. If not, see .