Math::...tePaper(3pm)
💖 Math::...tePaper(3pm) 💖
okay bestie, gather round 🫶 this one's from the User Contributed Perl Documentation collection, and the manual page name is literally Math::...tePaper(3pm) — yes it's giving truncated-but-iconic, we move 💅
✨ NAME ✨
Math::PlanePath::AlternatePaper — the alternate paper folding curve 🎀
✨ SYNOPSIS ✨
use Math::PlanePath::AlternatePaper;
my $path = Math::PlanePath::AlternatePaper->new;
my ($x, $y) = $path->n_to_xy (123);✨ DESCRIPTION ✨
so this is the integer version of the alternate paper folding curve — basically a little remix of the DragonCurve paper folding situation 💖
8 | 128
| |
7 | 42---43/127
| | |
6 | 40---41/45--44/124
| | | |
5 | 34---35/39--38/46--47/123
| | | | |
4 | 32---33/53--36/52--37/49--48/112
| | | | | |
3 | 10---11/31--30/54--51/55--50/58--59/111
| | | | | | |
2 | 8----9/13--12/28--29/25--24/56--57/61--60/108
| | | | | | | |
1 | 2----3/7---6/14--15/27--26/18--19/23---22/62--63/107
| | | | | | | | |
Y=0 | 0-----1 4-----5 16-----17 20-----21 64---..
|
+------------------------------------------------------------
X=0 1 2 3 4 5 6 7 8okay so here's the tea on what this curve is doing 👑
- it visits the X axis points and the X=Y diagonal points once each
- it visits the "inside" points in between twice each
- the very first doubled point is
X=2,Y=1, which isN=3and alsoN=7😳 - the segments
N=2,3,4andN=6,7,8have touched, but the curve does not cross over itself — not messy, just affectionate 💅 - all the doubled vertices are like this: touching but not crossing, and no edges repeat — periodt
the first step N=1 goes to the right along the X axis, and the path fills the eighth of the plane up to the X=Y diagonal inclusive ✨
X axis — N=0,1,4,5,16,17,etc — those are the integers that have only the digits 0,1 in base 4. equivalently: the ones that have a 0 bit at each odd numbered bit position 🧚
X=Y diagonal — N=0,2,8,10,32,etc — those are the integers that have only the digits 0,2 in base 4. equivalently: the ones that have a 0 bit at each even numbered bit position 🌸
and here's the crossover moment: the X axis values are the same as the ZOrderCurve X axis, and the X=Y diagonal is the same as the ZOrderCurve Y axis — but in between the two, they're different 💀 (see Math::PlanePath::ZOrderCurve.)
🦋 Paper Folding 🦋
so where does this curve even come from?? the whole vibe is: picture a strip of paper folded in half, alternately one way and then the other, and then unfolded so that every crease is a 90 degree angle. the effect? 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-------1then that little "L" shape unfolds again, pivoting at the end "2", but this time anti-clockwise, on the opposite side to the first unfold:
2-------3
2 | |
| unfold | ^ |
| ===> | _/ |
| | |
0------1 0-------1 4okay so in general, after each unfold the shape is a triangle, like this. the "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,0for an even number of unfolds, the triangle is made of 4 sub-parts, numbered by the high digit of N in base 4. those sub-parts are self-similar in the direction ">", "^" etc like so — and with a reversal for parts 1 and 3 💫
+
/|
/ |
/ |
/ 2>|
+----+
/|\ 3|
/ | \ v|
/ |^ \ |
/ 0>| 1 \|
+----+----+👑 Arms 👑
the "arms" parameter lets you pick 1 to 8 curve arms that successively advance 🎀 each one 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 4here the even N=0,2,4,6,etc is the plain curve below the X=Y diagonals, and the 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 is what makes sure each edge between integer points gets 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 2so 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 one 💫
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 🧚 and with a full 8 arms, each point is visited twice... except for the four start points, which get visited 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✨ FUNCTIONS ✨
first things first bestie: check "FUNCTIONS" in Math::PlanePath for the behaviour that's common to all the path classes 🫶
$path = Math::PlanePath::AlternatePaper->new ()$path = Math::PlanePath::AlternatePaper->new (arms => $integer)— build a brand new path object and hand it back to you 💖($x,$y) = $path->n_to_xy ($n)— gives you the X,Y coordinates of point number$non the path. points start at0, and if"$n < 0"then you get back an empty list. fractional positions give you an X,Y position along a straight line between the integer points ✨@n_list = $path->xy_to_n_list ($x,$y)— gives you a list of N point numbers for the coordinates"$x,$y"🎀- for
arms=1there may be none, one or two N's for a given"$x,$y". - for multiple arms, the origin points
X=0or1andY=0or-1have up to 3 Ns, because those are the starting points of the arms. - for
arms=8those 4 points have 3 N and every other"$x,$y"has exactly two Ns.
- for
$n = $path->n_start()— returns0, the first N in the path 👑
🎀 Level Methods 🎀
($n_lo, $n_hi) = $path->level_to_n_range($level)— returns(0, 2**$level), or for multiple arms it returns(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) 💅
okay and that's not even close to all of it bestie — there's a whole part 2 waiting for you, so don't go anywhere 🫶💖
💖 Turn 💖
okay so at every single point N, the curve always turns — left or right, never straight ahead. never. it's giving main character who refuses to be boring ✨
the turn is decided by the bit above the lowest 1 bit in N, plus 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 leftso like, for example, N=10 binary 0b1010 has its lowest 1 bit at 0b__1_, and the bit above that one is a 0 sitting at an even number, pos=2, so we turn right. slay 💅
🌈 Next Turn 🌈
the bits can also tell you the turn after next, bestie — you just look at the bit above the lowest 0 instead:
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 leftfor 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 we turn right. 🦋
and the reason this works is honestly so elegant: w011..11 when you increment it becomes w100..00, which is exactly that "z" form from up above. it's the same thing wearing a different outfit, periodt.
the inversion at odd bit positions can be applied with an xor 0b1010..1010. once you've done that, 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 here is either left or right according to an odd or even bit position of the transition, instead of always left like the DragonCurve does. little difference, big consequences 💀
🎀 dX,dY 🎀
since there's always a turn either left or right and never straight ahead, the X coordinate changes, then the Y coordinate changes, alternately. iconic behaviour.
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 one it is follows the Golay-Rudin-Shapiro sequence, which is parity odd or even of the count of adjacent 11 bit pairs. no cap.
in the total turn above you can see that if the 0->1 transition is at an odd position and the 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 = 0this (-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 paritythe 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 oddfor 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 oddfor 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 you can see 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 5the 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. obsessed with the symmetry ngl 😭
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.)
👑 OEIS 👑
the alternate paper folding curve is in Sloane's Online Encyclopedia of Integer Sequences as
<http://oeis.org/A106665> (etc)A020986— X coordinate unduplicated, X+Y coordinate sum being Golay/Rudin/Shapiro cumulativeA020990— Y coordinate unduplicated, X-Y diff starting from N=1 being Golay/Rudin/Shapiro * (-1)^n cumulativeA068915— Y when N even, X when N odd
since the X and Y coordinates each change alternately, each coordinate appears twice — for instance X=0,1,1,2,2,3,3,2,2,etc. A020986 and A020990 are "undoubled" X and Y in the sense of just one copy of each of those paired values.
A209615— turn 1=left,-1=rightA292077— turn 0=left,1=rightA106665— next turn 1=left,0=right, a(0) is turn at N=1A020985— dX and dY alternately, dSum change in X+Y being Golay/Rudin/Shapiro sequence +1,-1A020987— GRS with values 0,1 instead of +1,-1A077957— Y at N=2^k, being alternately 0 and 2^(k/2)A000695— N on X axis, being base 4 digits 0,1 onlyA007088— in base-4
A151666— predicate 0,1 for N on X axisA062880— N on diagonal, being base 4 digits 0,2 onlyA169965— in base-4
A126684— N single-visited points, either X axis or diagonalA176237— N double-visited pointsA270804— N segments of X=Y diagonal stair-stepA270803— 0,1 predicate for these segments
A022155— N positions of West or South segments, being GRS < 0, ie. dSum < 0 so move to previous anti-diagonalA203463— N positions of East or North segments, being GRS > 0, ie. dSum > 0 so move to next anti-diagonalA212591— N-1 of first time on X+Y=s anti-diagonalA047849— N of first time on X+Y=2^k anti-diagonalA020991— N-1 of last time on X+Y=s anti-diagonalA053644— X of last time on X+Y=s anti-diagonalA053645— Y of last time on X+Y=s anti-diagonalA080079— X-Y of last time on X+Y=s anti-diagonalA093573— N-1 of points on the anti-diagonals d=X+Y, by ascending N-1 value within each diagonalA004277— num visits in column X
A020991 etc have values N-1, ie. the numbering differs by 1 from the N here, since they're based on the A020986 cumulative GRS starting at n=0 for value GRS(0). this matches the turn sequence A106665 starting at n=0 for the first turn, whereas for the path here that's N=1. 🫶
A274230— area to N=2^k = double-visited points to N=2^kA027556— 2*area to N=2^kA134057— area to N=4^kA060867— area to N=2*4^kA122746— area increment N=2^k to N=2^(k+1) = num segments West N=0 to 2^k-1A005418— num segments East N=0 to 2^k-1A051437— num segments North N=0 to 2^k-1A007179— num segments South N=0 to 2^k-1A097038— num runs of 8 consecutive segments within N=0 to 2^k-1 each segment enclosing a new unit squareA000225— convex hull area * 2, being 2^k-1A027383— boundary/2 to N=2^k, also boundary verticals or horizontals (boundary is half verticals half horizontals)A131128— boundary to N=4^kA028399— boundary to N=2*4^kA052955— single-visited points to N=2^kA052940— single-visited points to N=4^k, being 3*2^n-1A181666— n XOR other(n) occurring at double-visited pointsA086341— graph diameter of level N=0 to 2^k (for k>=3)
arms=2
A062880— N on X axis, base 4 digits 0,2 only
arms=3
A001196— N on X axis, base 4 digits 0,3 only
🏰 HOUSE OF GRAPHS 🏰
House of Graphs entries for the alternate paperfolding curve as a graph include
<https://hog.grinvin.org/ViewGraphInfo.action?id=19655> etc19655— level=0 (1-segment path)32234— level=1 (2-segment path)286— level=2 (4-segment path)27008— level=327010— level=427012— level=533778— level=633780— level=733782— level=8
🔥 SEE ALSO 🔥
- Math::PlanePath, Math::PlanePath::AlternatePaperMidpoint
- Math::PlanePath::DragonCurve, Math::PlanePath::CCurve, Math::PlanePath::HIndexing, Math::PlanePath::ZOrderCurve
- Math::NumSeq::GolayRudinShapiro, Math::NumSeq::GolayRudinShapiroCumulative
- Michel Mendès France and G. Tenenbaum, "Dimension des Courbes Planes, Papiers Plies et Suites de Rudin-Shapiro", Bulletin de la S.M.F., volume 109, 1981, pages 207-215.
<http://www.numdam.org/item?id=BSMF_1981__109__207_0>🏠 HOME PAGE 🏠
okay bestie, if you wanna come hang out where this whole thing lives, the door's right here:
that's the home page, that's the vibe, that's where the lore is ✨
📜 LICENSE 📜
okay so legal stuff, but make it cute 🎀 — this part matters, so read it fr fr.
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021 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 cap, that WITHOUT ANY WARRANTY bit is in all caps for a reason 💀 — no implied warranty of merchantability, no fitness for a particular purpose, none of it. it's giving "you're on your own if it breaks" energy, and that's the actual license saying that, not me.
and that's a wrap on the whole page bestie, we ate 🍓💅 this one's from perl v5.32.0, dated 2021-01-23, and it's the Math::...tePaper(3pm) page under User Contributed Perl Documentation. go forth and plot some planes, ily 🫶🌸
📦 where this page comes from
- debian bookworm: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- debian trixie: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu jammy: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu noble: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu resolute: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu stonking: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- 💖 girlified by deepseek-ai/DeepSeek-V4.1-Flash on : a language model's rewrite of the original, under its terms