.\" 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::UlamWarburtonQuarter 3pm" .TH Math::PlanePath::UlamWarburtonQuarter 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::UlamWarburtonQuarter \-\- growth of a 2\-D cellular automaton .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::UlamWarburtonQuarter; \& my $path = Math::PlanePath::UlamWarburtonQuarter\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This is the pattern of a cellular automaton studied by Ulam and Warburton, confined to a quarter of the plane and oriented diagonally. Cells are numbered by growth tree row and anti-clockwise within the row. .IX Xref "Ulam, Stanislaw Warburton" .PP .Vb 10 \& 14 | 81 80 79 78 75 74 73 72 \& 13 | 57 56 55 54 \& 12 | 82 48 47 77 76 46 45 71 \& 11 | 40 39 \& 10 | 83 49 36 35 34 33 44 70 \& 9 | 58 28 27 53 \& 8 | 84 85 37 25 24 32 68 69 \& 7 | 22 \& 6 | 20 19 18 17 23 31 67 66 \& 5 | 12 11 26 52 \& 4 | 21 9 8 16 29 30 43 65 \& 3 | 6 38 \& 2 | 5 4 7 15 59 41 42 64 \& 1 | 2 10 50 51 \& Y=0| 1 3 13 14 60 61 62 63 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 .Ve .PP The growth rule is a given cell grows diagonally \s-1NE, NW, SE\s0 and \s-1SW,\s0 but only if the new cell has no neighbours and is within the first quadrant. So the initial cell \*(L"a\*(R" is N=1, .PP .Vb 3 \& | \& | a initial cell, depth=0 \& +\-\-\-\- .Ve .PP It's confined to the first quadrant so can only grow \s-1NE\s0 as \*(L"b\*(R", .PP .Vb 3 \& | b \& | a "b" depth=1 \& +\-\-\-\-\-\- .Ve .PP Then the next row \*(L"c\*(R" cells can go in three directions \s-1SE, NE, NW. \s0 These cells are numbered anti-clockwise around from the \s-1SE\s0 as N=3,N=4,N=5. .PP .Vb 4 \& | c c \& | b \& | a c "c" depth=2 \& +\-\-\-\-\-\-\-\-\- .Ve .PP The \*(L"d\*(R" cell is then only a single on the leading diagonal, since the other diagonals all already have neighbours (the existing \*(L"c\*(R" cells). .PP .Vb 5 \& | d \& | c c depth=3 \& | b \& | a c \& +\-\-\-\-\-\-\-\-\- \& \& | e e \& | d \& | c c e depth=4 \& | b \& | a c \& +\-\-\-\-\-\-\-\-\-\-\- \& \& | f f \& | e e \& | d \& | c c e depth=5 \& | b f \& | a c \& +\-\-\-\-\-\-\-\-\-\-\-\-\- \& \& | g g g g \& | f f \& | g e e g \& | d \& | c c e g depth=6 \& | b f \& | a c g g \& +\-\-\-\-\-\-\-\-\-\-\-\-\- .Ve .PP In general the pattern always always grows by 1 along the X=Y leading diagonal. The point on that diagonal is the middle of row depth=X. The pattern expands into the sides with a self-similar diamond shaped pattern filling 6 of 16 cells in any 4x4 square block. .SS "Tree Row Ranges" .IX Subsection "Tree Row Ranges" Counting depth=0 as the N=1 at the origin, depth=1 as the next N=2, etc, the number of new cells added in the tree row is .PP .Vb 1 \& rowwidth(depth) = 3^(count_1_bits(depth+1) \- 1) .Ve .PP So depth=0 has 3^(1\-1)=1 cells, as does depth=1 which is N=2. Then depth=2 has 3^(2\-1)=3 cells N=3,N=4,N=5 because depth+1=3=0b11 has two 1 bits in binary. The N row start and end is the cumulative total of those before it, .PP .Vb 1 \& Ndepth(depth) = 1 + rowwidth(0) + ... + rowwidth(depth\-1) \& \& Nend(depth) = rowwidth(0) + ... + rowwidth(depth) .Ve .PP For example depth=2 ends at N=(1+1+3)=5. .PP .Vb 10 \& depth Ndepth rowwidth Nend \& 0 1 1 1 \& 1 2 1 2 \& 2 3 3 5 \& 3 6 1 6 \& 4 7 3 9 \& 5 10 3 12 \& 6 13 9 21 \& 7 22 1 22 \& 8 23 3 25 .Ve .PP At row depth+1 = power\-of\-2 the Ndepth sum is .PP .Vb 1 \& Ndepth(depth) = 1 + (4^a\-1)/3 for depth+1 = 2^a .Ve .PP For example depth=3 is depth+1=2^2 starts at N=1+(4^2\-1)/3=6, or depth=7 is depth+1=2^3 starts N=1+(4^3\-1)/3=22. .PP Further bits in the depth+1 contribute powers\-of\-4 with a tripling for each bit above it. So if depth+1 has bits a,b,c,d,etc from high to low then .PP .Vb 6 \& depth+1 = 2^a + 2^b + 2^c + 2^d ... a>b>c>d... \& Ndepth = 1 + (\-1 \& + 4^a \& + 3 * 4^b \& + 3^2 * 4^c \& + 3^3 * 4^d + ...) / 3 .Ve .PP For example depth=5 is depth+1=6 = 2^2+2^1 is Ndepth = 1+(4^2\-1)/3 + 4^1 = 10. Or depth=6 is depth+1=7 = 2^2+2^1+2^0 is Ndepth = 1+(4^2\-1)/3 + 4^1 + 3*4^0 = 13. .SS "Self-Similar Replication" .IX Subsection "Self-Similar Replication" The square shape growth to depth=2^level\-2 repeats the pattern to the preceding depth=2^(level\-1)\-2 three times. For example, .PP .Vb 8 \& | d d c c depth=6 = 2^3\-2 \& | d c triplicates \& | d d c c depth=2 = 2^2\-2 \& | * \& | a a b b \& | a b \& | a a b b \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- .Ve .PP The 3x3 square \*(L"a\*(R" repeats, pointing \s-1SE, NE\s0 and \s-1NW\s0 as \*(L"b\*(R", \*(L"c\*(R" and \*(L"d\*(R". This resulting 7x7 square then likewise repeats. The points in the path here are numbered by tree rows rather than by this sort of replication, but the replication helps to see the structure of the pattern. .SS "Octant" .IX Subsection "Octant" Option \f(CW\*(C`parts => \*(Aqoctant\*(Aq\*(C'\fR confines the pattern to the first eighth of the plane 0<=Y<=X. .PP .Vb 1 \& parts => "octant" \& \& 14 | 50 \& 13 | 36 \& 12 | 31 49 \& 11 | 26 \& 10 | 24 30 48 \& 9 | 19 35 \& 8 | 17 23 46 47 \& 7 | 15 \& 6 | 14 16 22 45 44 \& 5 | 9 18 34 \& 4 | 7 13 20 21 29 43 \& 3 | 5 25 \& 2 | 4 6 12 37 27 28 42 \& 1 | 2 8 32 33 \& Y=0 | 1 3 10 11 38 39 40 41 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 .Ve .PP In this arrangement N=1,2,4,5,7,etc on the leading diagonal is the last N of each row (\f(CW\*(C`tree_depth_to_n_end()\*(C'\fR). .SS "Upper Octant" .IX Subsection "Upper Octant" Option \f(CW\*(C`parts => \*(Aqoctant_up\*(Aq\*(C'\fR confines the pattern to the upper octant 0<=X<=Y of the first quadrant. .PP .Vb 1 \& parts => "octant_up" \& \& 14 | 46 45 44 43 40 39 38 37 \& 13 | 35 34 33 32 \& 12 | 47 30 29 42 41 28 27 \& 11 | 26 25 \& 10 | 48 31 23 22 21 20 \& 9 | 36 19 18 \& 8 | 49 50 24 17 16 \& 7 | 15 \& 6 | 13 12 11 10 \& 5 | 9 8 \& 4 | 14 7 6 \& 3 | 5 \& 2 | 4 3 \& 1 | 2 \& Y=0 | 1 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 .Ve .PP In this arrangement N=1,2,3,5,6,etc on the leading diagonal is the first N of each row (\f(CW\*(C`tree_depth_to_n()\*(C'\fR). .SS "N Start" .IX Subsection "N Start" The default is to number points starting N=1 as shown above. An optional \&\f(CW\*(C`n_start\*(C'\fR can give a different start, in the same pattern. For example to start at 0, .PP .Vb 1 \& n_start => 0 \& \& 7 | 21 \& 6 | 19 18 17 16 \& 5 | 11 10 \& 4 | 20 8 7 15 \& 3 | 5 \& 2 | 4 3 6 14 \& 1 | 1 9 \& Y=0| 0 2 12 13 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 .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::UlamWarburtonQuarter\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::UlamWarburtonQuarter\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::UlamWarburtonQuarter->new ()" .PD 0 .ie n .IP """$path = Math::PlanePath::UlamWarburtonQuarter\->new (parts => $str, n_start => $n)""" 4 .el .IP "\f(CW$path = Math::PlanePath::UlamWarburtonQuarter\->new (parts => $str, n_start => $n)\fR" 4 .IX Item "$path = Math::PlanePath::UlamWarburtonQuarter->new (parts => $str, n_start => $n)" .PD Create and return a new path object. \f(CW\*(C`parts\*(C'\fR can be .Sp .Vb 3 \& 1 first quadrant, the default \& "octant" first eighth \& "octant_up" upper eighth .Ve .SS "Tree Methods" .IX Subsection "Tree Methods" .ie n .IP """@n_children = $path\->tree_n_children($n)""" 4 .el .IP "\f(CW@n_children = $path\->tree_n_children($n)\fR" 4 .IX Item "@n_children = $path->tree_n_children($n)" Return the children of \f(CW$n\fR, or an empty list if \f(CW$n\fR has no children (including when \f(CW\*(C`$n < 1\*(C'\fR, ie. before the start of the path). .Sp The children are the cells turned on adjacent to \f(CW$n\fR at the next row. The way points are numbered means that when there's multiple children they're consecutive N values, for example at N=12 the children 19,20,21. .ie n .IP """$n_parent = $path\->tree_n_parent($n)""" 4 .el .IP "\f(CW$n_parent = $path\->tree_n_parent($n)\fR" 4 .IX Item "$n_parent = $path->tree_n_parent($n)" Return the parent node of \f(CW$n\fR, or \f(CW\*(C`undef\*(C'\fR if \f(CW\*(C`$n <= 1\*(C'\fR (the start of the path). .SS "Tree Descriptive Methods" .IX Subsection "Tree Descriptive Methods" .ie n .IP """@nums = $path\->tree_num_children_list()""" 4 .el .IP "\f(CW@nums = $path\->tree_num_children_list()\fR" 4 .IX Item "@nums = $path->tree_num_children_list()" Return a list of the possible number of children at the nodes of \f(CW$path\fR. This is the set of possible return values from \f(CW\*(C`tree_n_num_children()\*(C'\fR. .Sp .Vb 5 \& parts tree_num_children_list() \& \-\-\-\-\- \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& 1 0, 1, 3 \& octant 0, 1, 2, 3 \& octant_up 0, 1, 2, 3 .Ve .Sp The octant forms have 2 children when branching from the leading diagonal, otherwise 0,1,3. .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`($n_start, tree_depth_to_n_end(2**($level+1) \- 2))\*(C'\fR. .SH "OEIS" .IX Header "OEIS" Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path includes .Sp .RS 4 (etc) .RE .PP .Vb 3 \& parts=1 (the default) \& A147610 num cells in row, tree_depth_to_width() \& A151920 total cells to depth, tree_depth_to_n_end() \& \& parts=octant,octant_up \& A079318 num cells in row, tree_depth_to_width() .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::UlamWarburton, Math::PlanePath::LCornerTree, Math::PlanePath::CellularRule .PP Math::PlanePath::SierpinskiTriangle (a similar binary ones-count related calculation) .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 .