NAME
Math::PlanePath::CornerReplicate  replicating U parts
SYNOPSIS
use Math::PlanePath::CornerReplicate;
my $path = Math::PlanePath::CornerReplicate>new;
my ($x, $y) = $path>n_to_xy (123);
DESCRIPTION
This path is a selfsimilar replicating corner fill with 2x2 blocks. It's sometimes called a "U order" since the base N=0 to N=3 is like a "U" (sideways).
7  6362 5958 4746 4342
    
6  6061 5657 4445 4041
  
5  5150 5554 3534 3938
    
4  4849 5253 3233 3637
 
3  1514 1110 3130 2726
    
2  1213 8 9 2829 2425
  
1  3 2 7 6 1918 2322
    
Y=0  0 1 4 5 1617 2021
+
X=0 1 2 3 4 5 6 7
The pattern is the initial N=0 to N=3 section,
+++
  
 3  2 
  
+++
  
 0  1 
  
+++
It repeats as 2x2 blocks arranged in the same pattern, then 4x4 blocks, etc. There's no rotations or reflections within subparts.
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.
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.
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.
The X axis is the same as the ZOrderCurve
. The Y axis here is the X=Y diagonal of the ZOrderCurve
, and conversely the X=Y diagonal here is the Y axis of the ZOrderCurve
.
The N value at a given X,Y is converted to or from the ZOrderCurve
by transforming base4 digit values 2<>3. This can be done by a bitwise "X xor Y". When Y has a 1bit the xor swaps 2<>3 in N.
ZOrder X = CRep X xor CRep Y
ZOrder Y = CRep Y
CRep X = ZOrder X xor ZOrder Y
CRep Y = ZOrder Y
Level Ranges
A given replication extends to
Nlevel = 4^level  1
0 <= X < 2^level
0 <= Y < 2^level
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 bitpair of N becomes a bit of X and a bit of Y,
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
So the Hamming distance is the number of base4 bitpairs of N which are 01 or 11. Counting bit positions from 0 for the least significant bit then this is the 1bits in even positions,
HammingDist(X,Y) = count 1bits at even bit positions in N
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::CornerReplicate>new ()

Create and return a new path object.
($x,$y) = $path>n_to_xy ($n)

Return the X,Y coordinates of point number
$n
on the path. Points begin at 0 and if$n < 0
then the return is an empty list. ($n_lo, $n_hi) = $path>rect_to_n_range ($x1,$y1, $x2,$y2)

The returned range is exact, meaning
$n_lo
and$n_hi
are the smallest and biggest in the rectangle.
FORMUALS
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.
N = ...[d]333...333 base 4
\exp/
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.
N, N+1 X Y dX dY dSum dDiffXY
      
033..33 0 2^k1 2^k (2^k1) +1 2*2^k1
100..00 2^k 0
133..33 2^k 2^k1 0 +1 +1 1
200..00 2^k 2^k
133..33 2^k 2*2^k1 2^k 12^k (2^k1) 1
200..00 0 2^k
133..33 0 2*2^k1 2*2^k (2*2^k1) +1 4*2^k1
200..00 2*2^k 0
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="233" to N=48="300". Everywhere else it advances by +1 antidiagonal.
The difference dDiffXY=dXdY the change in XY decreases at most 1, taking similar values 1, 1, 3, 7, 15, etc but in a different order to dSum.
OEIS
This path is in Sloane's Online Encyclopedia of Integer Sequences as
http://oeis.org/A000695 (etc)
A059906 Y coordinate
A059905 X xor Y, being ZOrderCurve X
A139351 HammingDist(X,Y), count 1bits 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 base4 flip 2<>3,
converts N to ZOrderCurve N, and back
A048647 permutation N at transpose Y,X
base4 digits 1<>3
SEE ALSO
Math::PlanePath, Math::PlanePath::LTiling, Math::PlanePath::SquareReplicate, Math::PlanePath::GosperReplicate, Math::PlanePath::ZOrderCurve, Math::PlanePath::GrayCode
HOME PAGE
http://user42.tuxfamily.org/mathplanepath/index.html
LICENSE
Copyright 2011, 2012, 2013, 2014 Kevin Ryde
This file is part of MathPlanePath.
MathPlanePath 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.
MathPlanePath 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 MathPlanePath. If not, see <http://www.gnu.org/licenses/>.