Math::...licate(3pm)

📦
version 129 · 3 versions
, in debian bookworm, debian trixie, ubuntu jammy, ubuntu noble, ubuntu resolute, ubuntu stonking

💖 NAME 💖

Math::PlanePath::CornerReplicate — replicating U parts, and that is the entire name, no notes. 🌸

(Also hi bestie, this is the page that shows up as Math::...licate(3pm) in the User Contributed Perl Documentation section, in case your terminal was truncating it and you were like "???" — it's section 3pm, she's just being dramatic. 💅)

✨ SYNOPSIS ✨

use Math::PlanePath::CornerReplicate;
my $path = Math::PlanePath::CornerReplicate->new;
my ($x, $y) = $path->n_to_xy (123);

🌀 DESCRIPTION 🌀

Okay so this path is a self-similar replicating corner fill made of 2x2 blocks, and it is lowkey gorgeous. Sometimes it gets called a "U order" because the base chunk from N=0 to N=3 is literally shaped like a "U" — sideways, but we support her. 🎀

     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 starts as the initial N=0 to N=3 section:

    +-------+-------+
    |       |       |
    |   3   |   2   |
    |       |       |
    +-------+-------+
    |       |       |
    |   0   |   1   |
    |       |       |
    +-------+-------+

Then it repeats as 2x2 blocks arranged in that same pattern, then 4x4 blocks, and so on forever, main character energy. There's no rotations or reflections within the sub-parts — none, zero, she does not rotate. 🙅

The 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. Slay.

The 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. Obsessed.

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". It's giving sibling energy fr fr.

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

See Math::PlanePath::LCornerReplicate for a rotating corner form, if you want the spinny version. 🦋

📏 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. It's basically a vibe check but for bits. ✨

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 least significant bit, this is the 1-bits in even positions:

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)

🛠 FUNCTIONS 🛠

See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes — that's the shared lore, iykyk. 💜

  • $path = Math::PlanePath::CornerReplicate->new () — makes you a brand new path object and hands it back. Fresh out the box, no cap.
  • ($x,$y) = $path->n_to_xy ($n) — gives you 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. Not a vibe, just 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. No rounding, no guessing, she ate. 👑

🧁 Level Methods

  • ($n_lo, $n_hi) = $path->level_to_n_range($level) — returns (0, 4**$level - 1). That's the whole thing, that's the method. 💅

🧮 FORMULAS 🧮

🔄 N to dX,dY

The change dX,dY is given by N in base 4: count trailing 3s, and look at 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. Not the same lineup, bestie, don't get it twisted.

🔍 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

👀 SEE ALSO 👀

Go read these next, bestie, they're all in the family:

  • Math::PlanePath
  • Math::PlanePath::LTiling
  • Math::PlanePath::SquareReplicate
  • Math::PlanePath::GosperReplicate
  • Math::PlanePath::ZOrderCurve
  • Math::PlanePath::GrayCode

🏠 HOME PAGE 🏠

<http://user42.tuxfamily.org/math-planepath/index.html>

📜 LICENSE 📜

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/>.

💀 no warranty bestie, she said what she said, read the GPL for the details.

and that's the whole page, you're welcome 🫶 — this little legend was rendered by perl v5.32.0 on 2021-01-23, mwah, bye bestie 💖✨🎀

📦 where this page comes from