.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is turned on, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{ . if \nF \{ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). .\" Fear. Run. Save yourself. No user-serviceable parts. . \" fudge factors for nroff and troff .if n \{\ . ds #H 0 . ds #V .8m . ds #F .3m . ds #[ \f1 . ds #] \fP .\} .if t \{\ . ds #H ((1u-(\\\\n(.fu%2u))*.13m) . ds #V .6m . ds #F 0 . ds #[ \& . ds #] \& .\} . \" simple accents for nroff and troff .if n \{\ . ds ' \& . ds ` \& . ds ^ \& . ds , \& . ds ~ ~ . ds / .\} .if t \{\ . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' .\} . \" troff and (daisy-wheel) nroff accents .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' .ds 8 \h'\*(#H'\(*b\h'-\*(#H' .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] .ds ae a\h'-(\w'a'u*4/10)'e .ds Ae A\h'-(\w'A'u*4/10)'E . \" corrections for vroff .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' . \" for low resolution devices (crt and lpr) .if \n(.H>23 .if \n(.V>19 \ \{\ . ds : e . ds 8 ss . ds o a . ds d- d\h'-1'\(ga . ds D- D\h'-1'\(hy . ds th \o'bp' . ds Th \o'LP' . ds ae ae . ds Ae AE .\} .rm #[ #] #H #V #F C .\" ======================================================================== .\" .IX Title "Math::PlanePath::AlternatePaper 3pm" .TH Math::PlanePath::AlternatePaper 3pm "2014-08-27" "perl v5.20.1" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::PlanePath::AlternatePaper \-\- alternate paper folding curve .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::AlternatePaper; \& my $path = Math::PlanePath::AlternatePaper\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This is an integer version of the alternate paper folding curve (a variation on the DragonCurve paper folding). .PP .Vb 10 \& 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 8 .Ve .PP The curve visits the X axis points and the X=Y diagonal points once each and visits \*(L"inside\*(R" points between there twice each. The first doubled point is X=2,Y=1 which is N=3 and also N=7. The segments N=2,3,4 and N=6,7,8 have touched, but the curve doesn't cross over itself. The doubled vertices are all like this, touching but not crossing, and no edges repeat. .PP The first step N=1 is to the right along the X axis and the path fills the eighth of the plane up to the X=Y diagonal inclusive. .PP The X axis N=0,1,4,5,16,17,etc is the integers which have only digits 0,1 in base 4, or equivalently those which have a 0 bit at each odd numbered bit position. .PP The X=Y diagonal N=0,2,8,10,32,etc is the integers which have only digits 0,2 in base 4, or equivalently those which have a 0 bit at each even numbered bit position. .PP The X axis values are the same as on the ZOrderCurve X axis, and the X=Y diagonal is the same as the ZOrderCurve Y axis, but in between the two are different. (See Math::PlanePath::ZOrderCurve.) .SS "Paper Folding" .IX Subsection "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. .PP The first segment N=0 to N=1 unfolds clockwise, pivoting at the endpoint \&\*(L"1\*(R", .PP .Vb 6 \& 2 \& \-> | \& unfold / | \& ===> | | \& | \& 0\-\-\-\-\-\-1 0\-\-\-\-\-\-\-1 .Ve .PP Then that \*(L"L\*(R" shape unfolds again, pivoting at the end \*(L"2\*(R", but anti-clockwise, on the opposite side to the first unfold, .PP .Vb 6 \& 2\-\-\-\-\-\-\-3 \& 2 | | \& | unfold | ^ | \& | ===> | _/ | \& | | | \& 0\-\-\-\-\-\-1 0\-\-\-\-\-\-\-1 4 .Ve .PP In general after each unfold the shape is a triangle as follows. \*(L"N\*(R" marks the N=2^k endpoint in the shape, either bottom right or top centre. .PP .Vb 3 \& after even number after odd number \& of unfolds, of unfolds, \& N=0 to N=2^even N=0 to N=2^odd \& \& . N \& /| / \e \& / | / \e \& / | / \e \& / | / \e \& / | / \e \& /_\|_\|_\|_\|_N /_\|_\|_\|_\|_\|_\|_\|_\|_\|_\|_\e \& 0,0 0,0 .Ve .PP 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 \*(L">\*(R", \*(L"^\*(R" etc as follows, and with a reversal for parts 1 and 3. .PP .Vb 11 \& + \& /| \& / | \& / | \& / 2>| \& +\-\-\-\-+ \& /|\e 3| \& / | \e v| \& / |^ \e | \& / 0>| 1 \e| \& +\-\-\-\-+\-\-\-\-+ .Ve .SS "Arms" .IX Subsection "Arms" The \f(CW\*(C`arms\*(C'\fR 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 .PP .Vb 1 \& 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 .Ve .PP 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. .PP 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. .PP .Vb 1 \& 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 .Ve .PP 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. .PP 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. .PP .Vb 1 \& 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 \& | | | | | | \& \& ^ \& \-2 \-1 \-2 X=0 1 2 .Ve .SH "FUNCTIONS" .IX Header "FUNCTIONS" See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for behaviour common to all path classes. .ie n .IP """$path = Math::PlanePath::AlternatePaper\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::AlternatePaper\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::AlternatePaper->new ()" .PD 0 .ie n .IP """$path = Math::PlanePath::AlternatePaper\->new (arms => $integer)""" 4 .el .IP "\f(CW$path = Math::PlanePath::AlternatePaper\->new (arms => $integer)\fR" 4 .IX Item "$path = Math::PlanePath::AlternatePaper->new (arms => $integer)" .PD Create and return a new path object. .ie n .IP """($x,$y) = $path\->n_to_xy ($n)""" 4 .el .IP "\f(CW($x,$y) = $path\->n_to_xy ($n)\fR" 4 .IX Item "($x,$y) = $path->n_to_xy ($n)" Return the X,Y coordinates of point number \f(CW$n\fR on the path. Points begin at 0 and if \f(CW\*(C`$n < 0\*(C'\fR then the return is an empty list. .Sp Fractional positions give an X,Y position along a straight line between the integer points. .ie n .IP """@n_list = $path\->xy_to_n_list ($x,$y)""" 4 .el .IP "\f(CW@n_list = $path\->xy_to_n_list ($x,$y)\fR" 4 .IX Item "@n_list = $path->xy_to_n_list ($x,$y)" Return a list of N point numbers for coordinates \f(CW\*(C`$x,$y\*(C'\fR. There may be none, one or two N's for a given \f(CW\*(C`$x,$y\*(C'\fR, and for arms>=2 there are three N's at the starting X,Y points. .ie n .IP """$n = $path\->n_start()""" 4 .el .IP "\f(CW$n = $path\->n_start()\fR" 4 .IX Item "$n = $path->n_start()" Return 0, the first N in the path. .SS "Level Methods" .IX Subsection "Level Methods" .ie n .IP """($n_lo, $n_hi) = $path\->level_to_n_range($level)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->level_to_n_range($level)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->level_to_n_range($level)" Return \f(CW\*(C`(0, 2**$level)\*(C'\fR, or for multiple arms return \f(CW\*(C`(0, $arms * 2**$level + ($arms\-1))\*(C'\fR. .Sp This is the same as \*(L"Level Methods\*(R" in Math::PlanePath::DragonCurve. Each level is an unfold (on alternate sides left or right). .SH "FORMULAS" .IX Header "FORMULAS" .SS "Turn" .IX Subsection "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. .PP .Vb 3 \& 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 .Ve .PP 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. .SS "Next Turn" .IX Subsection "Next Turn" The bits also give the turn after next by looking at the bit above the lowest 0. .PP .Vb 3 \& 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 .Ve .PP 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 \*(L"z\*(R" form above. .PP The inversion at odd bit positions can be applied with an xor 0b1010..1010. If that's done then the turn calculation is the same as the DragonCurve (see \&\*(L"Turn\*(R" in Math::PlanePath::DragonCurve). .SS "Total Turn" .IX Subsection "Total Turn" The total turn can be calculated from the segment replacements resulting from the bits of N. .PP .Vb 1 \& 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) .Ve .PP This is similar to the DragonCurve (see \*(L"Total Turn\*(R" 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. .SS "dX,dY" .IX Subsection "dX,dY" Since there's always a turn either left or right, never straight ahead, the X coordinate changes, then Y coordinate changes, alternately. .PP .Vb 3 \& 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 ... .Ve .PP 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. .PP 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 .PP .Vb 2 \& if N even then dX = (\-1)^(count even length runs of 1 bits in N) \& if N odd then dX = 0 .Ve .PP This (\-1)^count is related to the Golay-Rudin-Shapiro sequence, .PP .Vb 4 \& GRS = (\-1) ^ (count of adjacent 11 bit pairs in N) \& = (\-1) ^ count_1_bits(N & (N>>1)) \& = / +1 if (N & (N>>1)) even parity \& \e \-1 if (N & (N>>1)) odd parity .Ve .PP The \s-1GRS\s0 is +1 on an odd length run of 1 bits, for example a run 111 has two 11 bit pairs. The \s-1GRS\s0 is \-1 on an even length run, for example 1111 has three 11 bit pairs. So modulo 2 the power in the \s-1GRS\s0 is the same as the count of even length runs and therefore .PP .Vb 2 \& dX = / GRS(N) if N even \& \e 0 if N odd .Ve .PP 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 \*(L"plain\*(R" 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 \*(L"negate if even length\*(R" as the rest of the \s-1GRS,\s0 just for a slightly different reason. .PP .Vb 2 \& dY = / 0 if N even \& \e GRS(N) if N odd .Ve .SS "dX,dY Pair" .IX Subsection "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 \s-1GRS\s0(k) as .PP .Vb 2 \& dX = GRS(2k) \& = GRS(k) \& \& dY = GRS(2k+1) \& = GRS(k) * (\-1)^k \& = / GRS(k) if k even \& \e \-GRS(k) if k odd .Ve .PP 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 \*(L"11\*(R" bit pair which is lost from \&\s-1GRS\s0(k). The factor (\-1)^k adjusts for that, being +1 if k even or \-1 if k odd. .SS "dSum" .IX Subsection "dSum" From the dX and dY formulas above it can be seen that their sum is simply \&\s-1GRS\s0(N), .PP .Vb 1 \& dSum = dX + dY = GRS(N) .Ve .PP The sum X+Y is a numbering of anti-diagonal lines, .PP .Vb 8 \& | \e \e \e \& |\e \e \e \e \& | \e \e \e \e \& |\e \e \e \e \e \& | \e \e \e \e \e \& |\e \e \e \e \e \e \& +\-\-\-\-\-\-\-\-\-\-\-\- \& 0 1 2 3 4 5 .Ve .PP The curve steps each time either up to the next or back to the previous according to dSum=GRS(N). .PP 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. .PP The way the coordinate sum s=X+Y occurs s many times is a geometric interpretation to the way the cumulative \s-1GRS\s0 sequence has each value k occurring k many times. (See Math::NumSeq::GolayRudinShapiroCumulative.) .SS "Area" .IX Subsection "Area" The area enclosed by the curve for points N=0 to N=2^k inclusive is .PP .Vb 6 \& A[k] = (2^floor((k\-1)/2) \- 1) * (2^ceil((k\-1)/2) \- 1) \& = / (2^k \- 3*2^h + 2) / 2 if k odd \& \e (2^k \- 4*2^h + 2) / 2 if k even \& where h=floor(k/2) \& = 1/2*0, 0*0, 0*1, 1*1, 1*3, 3*3, 3*7, 7*7, 7*15, 15*15, ... \& = 0, 0, 0, 1, 3, 9, 21, 49, 105, 225, 465, 961, ... (A027556/2) .Ve .PP When k is even the curve is a triangular stack with every second block along the bottom and right sides unfilled. .PP .Vb 10 \& *\-\-* Y=2^h\-1 \& | | where h=k/2 \& *\-\-*\-\-* \& | | \& *\-\-*\-\-*\-\-* \& | | | | \& *\-\-*\-\-*\-\-*\-\-* \& | | | | \& *\-\-*\-\-*\-\-*\-\-*\-\-* \& | | | | | | \& *\-\-*\-\-*\-\-*\-\-*\-\-*\-\-* \& | | | | | | \& *\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-* \& | | | | | | | | \& *\-\-* *\-\-* *\-\-* *\-\-* * Y=0 \& X=1 X=2^h .Ve .PP The area formula can be found by moving the alternating blocks in the right column to fill the gaps in the bottom row, and moving the top half of the triangle down to complete a rectangle .PP .Vb 7 \& *\-\-\-\-\-\-\-\-*\-\-*\-\-*\-\-*\-\-* \& | | | | | | height = 2^(h\-1) \- 1 \& | *\-\-*\-\-*\-\-*\-\-*\-\-* = 2^floor((k\-1)/2) \- 1 \& | | | | | | | \& | *\-\-*\-\-*\-\-*\-\-*\-\-*\-\-* width = 2^h \- 1 \& | | | | | | | | = 2^ceil((k\-1)/2) \- 1 \& *\-\-*_\|_*\-\-*_\|_*\-\-*_\|_*\-\-* .Ve .PP When k is odd the curve is a pyramid stack with every second block along the bottom unfilled. .PP .Vb 10 \& * Y=2^h \& | \& *\-\-*\-\-* Y=2^h\-1 \& | | | where h=floor(k/2) \& *\-\-*\-\-*\-\-*\-\-* \& | | | | | \& *\-\-*\-\-*\-\-*\-\-*\-\-*\-\-* \& | | | | | | | \& *\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-* \& | | | | | | | | | \& *\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-* \& | | | | | | | | | | | \& *\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-* \& | | | | | | | | | | | | | \& *\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-* \& | | | | | | | | | | | | | | | \& *\-\-* *\-\-* *\-\-* *\-\-* *\-\-* *\-\-* *\-\-* *\-\-* \& X=1 X=2^h X=2^(2h)\-1 .Ve .PP This too can be rearranged, this time to make a square. The right hand half of the bottom row fills the gaps in the left. The remaining right hand triangle then goes above the left triangle. .PP .Vb 10 \& * Y=2^h \& | \& *\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-*\-\-* Y=2^h \- 1 \& | | | \& | *\-\-*\-\-* \& | | | | \& | *\-\-*\-\-*\-\-* height = 2^h \- 1 \& | | | | | = 2^floor((k\-1)/2) \& | *\-\-*\-\-*\-\-*\-\-* \& | | | | | | width = 2^h \- 1 \& | *\-\-*\-\-*\-\-*\-\-*\-\-* = 2^ceil((k\-1)/2) \& | | | | | | | \& | *\-\-*\-\-*\-\-*\-\-*\-\-*\-\-* floor((k\-1)/2) = ceil((k\-1)/2) \& | | | | | | | | since (k\-1)/2 is an integer \& *\-\-*\-\-*\-\-*\-\-*\-\-*\-\-*\-\-* when k is odd \& | | | | | | | | \& *\-\-*_\|_*\-\-*_\|_*\-\-*_\|_*\-\-*_\|_* \& X=1 X=2^h .Ve .PP For k=0 through k=2 there are no areas to copy this way but 2^0\-1=0 in the formula gives the desired A[0]=A[1]=A[2]=0. .SS "Area Increment" .IX Subsection "Area Increment" The new area added between N=2^k and N=2^(k+1) is .PP .Vb 4 \& dA[k] = A[k+1] \- A[k] \& = (2^floor(k/2) \- 1) * 2^ceil(k/2) / 2 \& = (2^k \- 2^ceil(k/2)) / 2 \& = 0, 0, 1, 2, 6, 12, 28, 56, 120, 240, 496, 992, ... (A122746) .Ve .SS "Convex Hull Area" .IX Subsection "Convex Hull Area" A convex hull is the smallest convex polygon which contains a given set of points. For the alternate paper the area of the convex hull for points N=0 to N=2^k inclusive is .PP .Vb 1 \& HA[k] = (2^k \- 1)/2 .Ve .PP The hull is a triangle of area 2^k/2 except for an end triangle of area 1/2 at the top for even level or right for odd level. .SS "Right Boundary" .IX Subsection "Right Boundary" The boundary length of the curve from N=0 to N=2^k on its right side is .PP .Vb 5 \& R[k] = / 1 if k=0 \& | 2*2^h if k even >= 2 \& \e 6*2^h \- 4 if k odd >= 1 \& where h=floor(k/2) \& = 1, 2, 4, 8, 8, 20, 16, 44, 32, 92, 64, 188, 128, 380, 256, ... .Ve .PP For k even the right boundary is along the X axis .PP .Vb 4 \& 2^h X axis horizontals \& 2^h X axis indentations, if k >= 2 \& \-\-\-\-\- \& 2*2^h .Ve .PP For k odd the right boundary is along the X axis and then up the right side to the top, .PP .Vb 6 \& 2*2^h \- 1 X axis horizontals \& 2*2^h \- 2 X axis indentations \& 2^h right slope verticals \& 2^h \- 1 right slope horizontals \& \-\-\-\-\-\-\- \& 6*2^h \- 4 .Ve .SS "Left Boundary" .IX Subsection "Left Boundary" The boundary length of the curve from N=0 to N=2^k on its left side is .PP .Vb 5 \& L[k] = / 1 if k=0 \& | 4*2^h \- 4 if k even >= 2 \& \e 2*2^h if k odd >= 1 \& where h=floor(k/2) \& = 1, 2, 4, 4, 12, 8, 28, 16, 60, 32, 124, 64, 252, 128, 508, ... .Ve .PP For k even the left boundary is up the left slope then down the vertical .PP .Vb 6 \& 2^h left slope horizontals \& 2^h \- 1 left slope verticals \& 2^h \- 1 right edge verticals \& 2^h \- 2 right edge indentations \& \-\-\-\-\- \& 4*2^h \- 4 .Ve .PP For k odd the left boundary is the left slope, and this time it includes a final vertical line segment .PP .Vb 4 \& 2^h left slope horizontals \& 2^h left slope verticals \& \-\-\-\-\-\-\- \& 2*2^h .Ve .SS "Boundary" .IX Subsection "Boundary" The total boundary length of the curve from N=0 to N=2^k is .PP .Vb 4 \& B[k] = L[k] + R[k] = / 6*2^h \- 4 if k even \& \e 8*2^h \- 4 if k odd \& where h=floor(k/2) \& = 2, 4, 8, 12, 20, 28, 44, 60, 92, 124, 188, 252, 380, ... (2*A027383) .Ve .PP The special case for k=0 is eliminated since the k even 6*2^h\-4 is the desired 2 when k=0, h=0. .PP Every enclosed unit square has all four sides traversed so by counting inside and outside sides of the segments have 2*N = 4*A + B. This can be verified for A[k] and B[k] .PP .Vb 7 \& 4*A[k] + B[k] = 4* / (2^h/2 \- 1) * (2^h \- 1) if k even \& \e (2^h \- 1) * (2^h \- 1) if k odd \& + / 6*2^h \- 4 if k even \& \e 8*2^h \- 4 if k odd \& = / 2 * 2^h * 2^h if k even \& \e 4 * 2^h * 2^h if k odd \& = 2*2^k .Ve .PP This relation also gives a formula for B[k] using the floor and ceil pair from A[k] .PP .Vb 2 \& B[k] = 2*2^k \- 4*A[k] \& = 2*2^k \- (2^floor((k+1)/2) \- 2) * (2^ceil((k+1)/2) \- 2) .Ve .SS "Single Points" .IX Subsection "Single Points" The number of single-visited points for N=0 to N=2^k inclusive is .PP .Vb 3 \& S[k] = / 3*2^h \- 1 if k even \& \e 4*2^h \- 1 if k odd \& = 2, 3, 5, 7, 11, 15, 23, 31, 47, 63, 95, 127, ... (A052955) .Ve .PP The single points are all on the outer edges and those sides can be counted easily. .PP The singles can also be obtained from the boundary. Each new line segment which increases the area also increases the double points, so area=doubles. Such a segment decreases the singles by \-1 and the boundary by \-2. A new line segment which doesn't enclose new area increases the singles by +1 and the boundary by +2. Starting from singles=1 boundary=0 means .PP .Vb 1 \& S[N] = B[N]/2 + 1 .Ve .PP Or with singles and doubles adding up to N+1 points the doubles=area can give the singles from the area. .PP .Vb 1 \& S + 2*D = N+1 N=number of segments, N+1=number of points .Ve .SH "OEIS" .IX Header "OEIS" The alternate paper folding curve is in Sloane's Online Encyclopedia of Integer Sequences as .Sp .RS 4 (etc) .RE .PP .Vb 12 \& A106665 next turn 1=left,0=right, a(0) is turn at N=1 \& A209615 turn 1=left,\-1=right \& A020985 Golay/Rudin/Shapiro sequence +1,\-1 \& dX and dY alternately \& dSum, change in X+Y \& A020986 Golay/Rudin/Shapiro cumulative \& X coordinate (undoubled) \& X+Y coordinate sum \& A020990 Golay/Rudin/Shapiro * (\-1)^n cumulative \& Y coordinate (undoubled) \& X\-Y diff, starting from N=1 \& A020987 GRS with values 0,1 instead of +1,\-1 .Ve .PP 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 \*(L"undoubled\*(R" X and Y in the sense of just one copy of each of those paired values. .PP .Vb 1 \& A077957 Y at N=2^k, being alternately 0 and 2^(k/2) \& \& A000695 N on X axis, base 4 digits 0,1 only \& A062880 N on diagonal, base 4 digits 0,2 only \& \& A022155 N positions of left or down segment, \& being GRS < 0, \& ie. dSum < 0 so move to previous anti\-diagonal \& A203463 N positions of up or right segment, \& being GRS > 0, \& ie. dSum > 0 so move to next anti\-diagonal \& \& A020991 N\-1 of first time on X+Y=k anti\-diagonal \& A212591 N\-1 of last time on X+Y=k anti\-diagonal \& A093573 N\-1 of points on the anti\-diagonals d=X+Y, \& by ascending N\-1 value within each diagonal .Ve .PP A020991 etc have values N\-1, ie. the numbering differs by 1 from the N here, since they're based on the A020986 cumulative \s-1GRS\s0 starting at n=0 for value \&\s-1\fIGRS\s0\fR\|(0). This matches the turn sequence A106665 starting at n=0 for the first turn, whereas for the path here that's N=1. .PP .Vb 4 \& A027556 area*2 to N=2^k \& A134057 area to N=4^k \& A060867 area to N=2*4^k \& A122746 area increment N=2^k to N=2^(k+1) \& \& A000225 convex hull area*2, being 2^k\-1 \& \& A027383 boundary/2 to N=2^k \& also boundary verticals or horizontals \& (boundary is half verticals half horizontals) \& A131128 boundary to N=4^k \& A028399 boundary to N=2*4^k \& \& A052955 single\-visited points to N=2^k \& A052940 single\-visited points to N=4^k, being 3*2^n\-1 \& \& 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 .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::AlternatePaperMidpoint .PP Math::PlanePath::DragonCurve, Math::PlanePath::CCurve, Math::PlanePath::HIndexing, Math::PlanePath::ZOrderCurve .PP Math::NumSeq::GolayRudinShapiro, Math::NumSeq::GolayRudinShapiroCumulative .PP Michel Mende\*`s France and G. Tenenbaum, \*(L"Dimension des Courbes Planes, Papiers Plies et Suites de Rudin-Shapiro\*(R", Bulletin de la S.M.F., volume 109, 1981, pages 207\-215. .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2011, 2012, 2013, 2014 Kevin Ryde .PP This file is part of Math-PlanePath. .PP Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the \s-1GNU\s0 General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. .PP Math-PlanePath is distributed in the hope that it will be useful, but \&\s-1WITHOUT ANY WARRANTY\s0; without even the implied warranty of \s-1MERCHANTABILITY\s0 or \s-1FITNESS FOR A PARTICULAR PURPOSE. \s0 See the \s-1GNU\s0 General Public License for more details. .PP You should have received a copy of the \s-1GNU\s0 General Public License along with Math-PlanePath. If not, see .