SYNOPSIS
use Math::PlanePath::CornerReplicate;
my $path = Math::PlanePath::CornerReplicate->new;
my ($x, $y) = $path->n_to_xy (123);
DESCRIPTION
This path is a self-similar 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 | 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
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 sub-parts.
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 base-4 digit values 2<->3. This can be done by a bitwise ``X xor Y''. When Y has a 1-bit 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 bit-pair 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 bit-pairs of N which are 01 or 11. Counting bit positions from 0 for the least significant bit then this is the 1-bits in even positions,
HammingDist(X,Y) = count 1-bits 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.
Level Methods
- "($n_lo, $n_hi) = $path->level_to_n_range($level)"
- Return "(0, 4**$level - 1)".
FORMULAS
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^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
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 anti-diagonal.
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.
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 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
LICENSE
Copyright 2011, 2012, 2013, 2014, 2015, 2016 Kevin RydeThis 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/>.