Paper Folding¶

The curve arises from thinking of a strip of paper folded in half alternately one way and the other, and then unfolded so each crease is a 90 degree angle. The effect is that the curve repeats in successive doublings turned 90 degrees and reversed.

The first segment N=0 to N=1 unfolds clockwise, pivoting at the endpoint "1",

                                    2
                               ->   |
                 unfold       /     |
                  ===>       |      |
                                    |
    0------1                0-------1

Then that "L" shape unfolds again, pivoting at the end "2", but anti-clockwise, on the opposite side to the first unfold,

                                    2-------3
           2                        |       |
           |     unfold             |   ^   |
           |      ===>              | _/    |
           |                        |       |
    0------1                0-------1       4

In general after each unfold the shape is a triangle as follows. "N" marks the N=2^k endpoint in the shape, either bottom right or top centre.

    after even number          after odd number
       of unfolds,                of unfolds,
     N=0 to N=2^even            N=0 to N=2^odd
               .                       N
              /|                      / \
             / |                     /   \
            /  |                    /     \
           /   |                   /       \
          /    |                  /         \
         /_____N                 /___________\
        0,0                     0,0

For an even number of unfolds the triangle consists of 4 sub-parts numbered by the high digit of N in base 4. Those sub-parts are self-similar in the direction ">", "^" etc as follows, and with a reversal for parts 1 and 3.

              +
             /|
            / |
           /  |
          / 2>|
         +----+
        /|\  3|
       / | \ v|
      /  |^ \ |
     / 0>| 1 \|
    +----+----+

Arms¶

The "arms" parameter can choose 1 to 8 curve arms successively advancing. Each fills an eighth of the plane. The second arm is mirrored across the X=Y leading diagonal, so

      arms => 2
        |   |     |       |       |       |
      4 |  33---31/55---25/57---23/63---64/65--
        |         |       |       |       |
      3 |  11---13/29---19/27---20/21---22/62--
        |   |     |       |       |       |
      2 |   9----7/15---16/17---18/26---24/56--
        |         |       |       |       |
      1 |   3----4/5-----6/14---12/28---30/54--
        |   |     |       |       |       |
    Y=0 |  0/1----2       8------10      32---
        |
        +------------- -------------------------
          X=0     1       2       3       4

Here the even N=0,2,4,6,etc is the plain curve below the X=Y diagonals and odd N=1,3,5,7,9,etc is the mirrored copy.

Arms 3 and 4 are the same but rotated +90 degrees and starting from X=0,Y=1. That start point ensures each edge between integer points is traversed just once.

    arms => 4
        |       |       |      |        |
    --34/35---14/30---18/21--25/57----37/53--        3
        |       |       |      |        |
    --15/31---10/11----6/17--13/29----32/33--        2
        |       |       |      |        |
     --19       7-----2/3/5---8/9-----12/28--        1
                        |      |        |
                       0/1-----4        16--     <- Y=0
    -----------------------------------------
       -1      -2      X=0     1        2

Points N=0,4,8,12,etc is the plain curve, N=1,5,9,13,etc the second mirrored arm, N=2,6,10,14,etc is arm 3 which is the plain curve rotated +90, and N=3,7,11,15,etc the rotated and mirrored.

Arms 5 and 6 start at X=-1,Y=1, and arms 7 and 8 start at X=-1,Y=0 so they too traverse each edge once. With a full 8 arms each point is visited twice except for the four start points which are three times.

    arms => 8
        |       |       |       |       |       |
    --75/107--66/67---26/58---34/41---49/113--73/105--        3
        |       |       |       |       |       |
    --51/115---27/59---18/19--10/33---25/57---64/65--         2
        |       |       |       |       |       |
    --36/43---12/35---4/5/11---2/3/9--16/17---24/56--         1
        |       |       |       |       |       |
    --28/60---20/21---6/7/13--0/1/15---8/39---32/47--     <- Y=0
        |       |       |       |       |       |
    --68/69---29/61----14/37---22/23--31/63---55/119--       -1
        |       |       |       |       |       |
    --77/109--53/117---38/45---30/62--70/71---79/111--       -2
        |       |       |       |       |       |
                                ^
       -3      -2      -1      X=0     1        2

Level Methods¶

"($n_lo, $n_hi) = $path->level_to_n_range($level)"

Return "(0, 2**$level)", or for multiple arms return "(0, $arms * 2**$level + ($arms-1))".

This is the same as "Level Methods" in Math::PlanePath::DragonCurve. Each level is an unfold (on alternate sides left or right).

Turn¶

At each point N the curve always turns either left or right, it never goes straight ahead. The turn is given by the bit above the lowest 1 bit in N and whether that position is odd or even.

    N = 0b...z100..00   (including possibly no trailing 0s)
             ^
             pos, counting from 0 for least significant bit
    (z bit) XOR (pos&1)   Turn
    -------------------   ----
             0            right
             1            left

For example N=10 binary 0b1010 has lowest 1 bit at 0b__1_ and the bit above that is a 0 at even number pos=2, so turn to the right.

Next Turn¶

The bits also give the turn after next by looking at the bit above the lowest 0.

    N = 0b...w011..11    (including possibly no trailing 1s)
             ^
             pos, counting from 0 for least significant bit
    (w bit) XOR (pos&1)    Next Turn
    -------------------    ---------
             0             right
             1             left

For example at N=10 binary 0b1010 the lowest 0 is the least significant bit, and above that is a 1 at odd pos=1, so at N=10+1=11 turn right. This works simply because w011..11 when incremented becomes w100..00 which is the "z" form above.

The inversion at odd bit positions can be applied with an xor 0b1010..1010. With that done the turn calculation is then the same as the DragonCurve (see "Turn" in Math::PlanePath::DragonCurve).

Total Turn¶

The total turn can be calculated from the segment replacements resulting from the bits of N.

    each bit of N from high to low
      when plain state
       0 -> no change
       1 -> turn left if even bit pos or turn right if odd bit pos
              and go to reversed state
      when reversed state
       1 -> no change
       0 -> turn left if even bit pos or turn right if odd bit pos
              and go to plain state
    (bit positions numbered from 0 for the least significant bit)

This is similar to the DragonCurve (see "Total Turn" in Math::PlanePath::DragonCurve) except the turn is either left or right according to an odd or even bit position of the transition, instead of always left for the DragonCurve.

dX,dY¶

Since there's always a turn either left or right, never straight ahead, the X coordinate changes, then Y coordinate changes, alternately.

        N=0
    dX   1  0  1  0  1  0 -1  0  1  0  1  0 -1  0  1  0  ...
    dY   0  1  0 -1  0  1  0  1  0  1  0 -1  0 -1  0 -1  ...

X changes when N is even, Y changes when N is odd. Each change is either +1 or -1. Which it is follows the Golay-Rudin-Shapiro sequence which is parity odd or even of the count of adjacent 11 bit pairs.

In the total turn above it can be seen that if the 0->1 transition is at an odd position and 1->0 transition at an even position then there's a turn to the left followed by a turn to the right for no net change. Likewise an even and an odd. This means runs of 1 bits with an odd length have no effect on the direction. Runs of even length on the other hand are a left followed by a left, or a right followed by a right, for 180 degrees, which negates the dX change. Thus

    if N even then dX = (-1)^(count even length runs of 1 bits in N)
    if N odd  then dX = 0

This (-1)^count is related to the Golay-Rudin-Shapiro sequence,

    GRS = (-1) ^ (count of adjacent 11 bit pairs in N)
        = (-1) ^ count_1_bits(N & (N>>1))
        = /  +1 if (N & (N>>1)) even parity
          \  -1 if (N & (N>>1)) odd parity

The GRS is +1 on an odd length run of 1 bits, for example a run 111 is two 11 bit pairs. The GRS is -1 on an even length run, for example 1111 is three 11 bit pairs. So modulo 2 the power in the GRS is the same as the count of even length runs and therefore

    dX = /  GRS(N)  if N even
         \  0       if N odd

For dY the total turn and odd/even runs of 1s is the same 180 degree changes, except N is odd for a Y change so the least significant bit is 1 and there's no return to "plain" state. If this lowest run of 1s starts on an even position (an odd number of 1s) then it's a turn left for +1. Conversely if the run started at an odd position (an even number of 1s) then a turn right for -1. The result for this last run is the same "negate if even length" as the rest of the GRS, just for a slightly different reason.

    dY = /  0       if N even
         \  GRS(N)  if N odd

dX,dY Pair¶

At a consecutive pair of points N=2k and N=2k+1 the dX and dY can be expressed together in terms of GRS(k) as

    dX = GRS(2k)
       = GRS(k)
    dY = GRS(2k+1)
       = GRS(k) * (-1)^k
       = /  GRS(k) if k even
         \  -GRS(k) if k odd

For dY reducing 2k+1 to k drops a 1 bit from the low end. If the second lowest bit is also a 1 then they were a "11" bit pair which is lost from GRS(k). The factor (-1)^k adjusts for that, being +1 if k even or -1 if k odd.

dSum¶

From the dX and dY formulas above it can be seen that their sum is simply GRS(N),

    dSum = dX + dY = GRS(N)

The sum X+Y is a numbering of anti-diagonal lines,

   | \ \ \
   |\ \ \ \
   | \ \ \ \
   |\ \ \ \ \
   | \ \ \ \ \
   |\ \ \ \ \ \
   +------------
     0 1 2 3 4 5

The curve steps each time either up to the next or back to the previous according to dSum=GRS(N).

The way the curve visits outside edge X,Y points once each and inner X,Y points twice each means an anti-diagonal s=X+Y is visited a total of s many times. The diagonal has floor(s/2)+1 many points. When s is odd the first is visited once and the rest visited twice. When s is even the X=Y point is only visited once. In each case the total is s many visits.

The way the coordinate sum s=X+Y occurs s many times is a geometric interpretation to the way the cumulative GRS sequence has each value k occurring k many times. (See Math::NumSeq::GolayRudinShapiroCumulative.)