Math::PlanePath::OneOfEight -- automaton growing to cells with one of eight neighbours
use Math::PlanePath::OneOfEight; my $path = Math::PlanePath::OneOfEight->new; my ($x, $y) = $path->n_to_xy (123);
This a cellular automaton growing into cells which have just 1 of 8 neighbours already "on" as per part 14 "Square Grid with Eight Neighbours" of
David Applegate, Omar E. Pol, N.J.A. Sloane, "The Toothpick Sequence and Other Sequences from Cellular Automata", Congressus Numerantium, volume 206, 2010, pages 157-191. http://www.research.att.com/~njas/doc/tooth.pdf
Points are numbered by a breadth-first tree traversal and anti-clockwise at each node.
121 8 93 92 91 90 89 88 87 86 85 84 83 82 7 94 64 63 60 59 81 6 95 44 43 42 62 61 41 40 39 80 5 45 34 33 38 4 96 46 20 19 18 17 16 15 37 79 3 97 65 66 21 10 9 14 57 58 78 2 98 22 4 3 2 13 77 1 5 0 1 <- Y=0 99 23 6 7 8 32 120 -1 100 68 67 24 11 12 31 76 75 119 -2 101 47 25 26 27 28 29 30 56 118 -3 48 35 36 55 -4 102 49 50 51 71 72 52 53 54 117 -5 103 69 70 73 74 116 -6 104 105 106 107 108 109 110 111 112 113 114 115 -7 ^ -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7
The start is N=0 at the origin X=0,Y=0. Then each cell around it has just one neighbour (that first N=0 cell) and so all are turned on. The rule is applied in a single atomic step, so adjacent prospective new cells don't count towards the 1 of 8.
At the next level only the diagonal cells X=+/-2,Y=+/-2 have a single neighbour, then at the next level five around each of them, and so on.
10 9 \ / 4 3 2 4 3 2 \ | / \ | / 0 5--0--1 5--0--1 / | \ / | \ 6 7 8 6 7 8 / \ 11 12
The children of a given node are numbered anti-clockwise around relative to the direction of the node's parent. For example N=9 has it's parent south-west and so points around N=9 are numbered anti-clockwise around from the south-west to give N=13 through N=17.
The pattern always extends along the X=+/-Y diagonals and grows into the sides in power-of-2 blocks. So for example in the part shown above N=33 at X=4,Y=4 is the only cell growing out of the 4x4 block X=0..3,Y=0..3 at the origin, and likewise N=34,35,36 in the other quadrants. Then N=121 at X=8,Y=8 is the only growth out of the 8x8 block, etc.
In general the first N at a power-of-2 depth is
depth=2^k for k>=0 Ndepth(2^k) = (16*4^k + 24*k - 7) / 9 = (16*depth*depth + 24*k - 7) / 9 eg. k=3 Ndepth=121
Because points are numbered from N=0 this Ndepth is how many cells are "on" in the pattern up to this depth (and not including it). The cells are within -2^k < X,Y < 2^k and so the fraction of the plane covered is
density = Ndepth(2^k) / (2*2^k - 1)^2 = (16*4^k + 24*k - 7) / 9 / (2*2^k-1)^2 -> 4/9 = 0.444... as k -> infinity
This density is approached from above, ie. decreases towards 4/9. The first k=0 is the single origin point which is density=1/1, and k=2 is density=9/9 of the 3x3 at the origin. Then for example k=2 7x7 square has density=33/49=0.673, then k=3 121/225=0.5377, etc.
Option parts => 1 confines the pattern to the first quadrant. This is a single copy of the part repeated in each of the four quadrants of the full pattern.
parts => 1
parts => 1 15 | 117 116 115 114 113 112 111 110 109 108 107 106 14 | 90 89 86 85 105 13 | 91 73 72 71 88 87 70 69 68 104 12 | 92 58 57 67 11 | 59 53 52 51 50 49 48 66 103 10 | 93 60 41 40 47 83 84 102 9 | 94 74 75 42 37 36 35 46 101 8 | 32 34 7 | 31 30 29 28 27 26 33 45 100 6 | 19 18 25 38 39 44 82 81 99 5 | 20 15 14 13 24 43 65 98 4 | 10 12 61 54 55 56 64 3 | 9 8 7 11 23 62 63 97 2 | 4 6 16 17 22 76 77 78 79 80 96 1 | 3 2 5 21 95 Y=0 | 0 1 +---------------------------------------------------------------- X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Option parts => 'octant' confines the pattern to the first eighth of the plane 0<=Y<=X.
parts => 'octant'
parts => "octant" 15 | 66 14 | 54 65 13 | 44 64 12 | 36 43 11 | 32 42 63 10 | 26 31 52 53 62 9 | 23 30 61 8 | 20 22 7 | 19 21 29 60 6 | 13 18 24 25 28 51 50 59 5 | 10 17 27 41 58 4 | 7 9 37 33 34 35 40 3 | 6 8 16 38 39 57 2 | 3 5 11 12 15 45 46 47 48 49 56 1 | 2 4 14 55 Y=0 | 0 1 +------------------------------------------------- X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
In this arrangement N=0,2,3,6,etc on the leading diagonal is the last N of each row (tree_depth_to_n_end()).
tree_depth_to_n_end()
The full pattern is symmetric on each side of the four diagonals X=Y, X=-Y. This octant is one of those eight symmetric parts. It includes the diagonal which is shared if two octants are combined to make a quadrant.
The octant is self similar in blocks
--| -- | -- | -- | -- extend | -- | 2^k,2^k --------------| --| -- upper | -- | -- flip | -- | -- | -- | lower -- | -- base | depth+1 -- | -- | no pow2s --| -----------------------------
"extend" is a direct copy of the "base" block. "upper" likewise a direct copy except flipped vertically.
"lower" is the base pattern rotated by +90 degrees and without the pow2 cells at Y=1 X=3,7,15,etc. These absent cells are easier to see in a bigger picture of the pattern.
The "lower" block is one depth level ahead too. For example in the sample above its last row is N=45,46,47,48 at depth=14 whereas the corresponding end of the "extend" at N=61,62,63,64,65 is depth=15.
The diagonal between the lower and upper looks like a stair-step, but that's not so. It's the same as the X=Y leading diagonal of the whole octant but because the lower block is one depth level ahead of the upper their branches off the diagonal are offset by 1 position. For example N=34,33,37 branching into the lower corresponds to N=40,41,51 branching into the upper.
This offset on the upper/lower diagonal is easier to see by chopping off the leaf nodes of the pattern (one level of leaf nodes).
* octant with leaf nodes pruned * * * * * * * * * * * * * * * * * <- upper,lower parts * * * branch off lower is 1 row sooner * * * * * * * * *
It may look at first as if the square side block comprising the "upper" and "lower" blocks is entirely different from the central symmetric square ("One Quadrant" above), but that's not so, the only difference is the offset branching from the diagonal which occurs in the "lower" part.
Option parts => 'octant_up' confines the pattern to the upper octant 0<=X<=Y of the first quadrant.
parts => 'octant_up'
parts => "octant_up" 15 | 66 65 64 63 62 61 60 59 58 57 56 55 14 | 50 49 46 45 13 | 51 42 41 40 48 47 39 38 37 12 | 52 34 33 11 | 35 32 31 30 29 28 27 10 | 53 36 25 24 9 | 54 43 44 26 23 22 21 8 | 20 7 | 19 18 17 16 15 14 6 | 12 11 5 | 13 10 9 8 4 | 7 3 | 6 5 4 2 | 3 1 | 2 1 Y=0 | 0 +------------------------------------------------- X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
In this arrangement N=0,1,3,4,etc on the leading diagonal is the first N of each row (tree_depth_to_n()).
tree_depth_to_n()
The pattern is a mirror image of parts=octant, mirrored across the X=Y leading diagonal. Points are still numbered anti-clockwise so the effect is to reverse the order. "octant" numbers from the ragged edge to the diagonal, whereas "octant_up" numbers from the diagonal to the ragged edge.
Option parts => "3mid" is the "second corner sequence" of the toothpick paper above. This is the part of the full pattern starting at a point X=2^k,Y=2^k in the full pattern, with the three square blocks there each extended indefinitely.
parts => "3mid"
parts => "3mid" 85 84 83 82 81 80 79 78 77 76 75 74 7 58 57 54 53 73 6 59 41 40 39 56 55 38 37 36 72 5 60 26 25 35 4 27 21 20 19 18 17 16 34 71 3 61 28 9 8 15 51 52 70 2 62 42 43 10 5 4 3 14 69 1 0 2 <- Y=0 1 13 68 -1 6 7 12 50 49 67 -2 11 33 66 -3 29 22 23 24 32 -4 30 31 65 -5 44 45 46 47 48 64 -6 63 -7 ^ -7 -5 -6 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7
The first quadrant X>=0,Y>=0 is the same as in the full pattern, but the other quadrants are a "side" portion (branches off the diagonal offset by 1 above and below).
This pattern can be generated from the 1 of 8 cell rule by starting from N=0 at X=0,Y=0 and then treating all points with X<0,Y<0 as already occupied.
.. .. .. .. 9 8 .. 10 5 4 3 .. 0 2 -------------+ 1 X<0,Y<0 * * * | 6 7 .. considered * * * | all "on" * * * |
Option parts => "3side" is the "first corner sequence" of the toothpick paper above. This is the part of the full pattern starting at a point X=2^k+1,Y=3*2^k-1 and mirrored horizontally, and the three square blocks there each extended indefinitely.
parts => "3side"
parts => "3side" .. 89 88 87 86 85 84 83 82 81 80 79 78 .. 8 70 69 66 65 7 71 51 50 49 68 67 48 47 46 64 6 72 34 33 63 5 35 25 24 23 22 21 20 32 4 73 36 15 14 31 62 3 74 52 53 16 8 7 6 13 44 45 61 2 3 12 60 1 0 2 <- Y=0 1 11 59 -1 4 5 10 43 42 58 -2 9 30 57 -3 26 17 18 19 29 -4 27 28 56 -5 37 38 39 40 41 55 -6 54 -7 .. 75 76 77 .. -8 ^ -7 -6 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 8
The two top quadrants Y>=0 are mirror images across the vertical X=1. The Y<0 bottom quadrant is rotated -90 degrees and is one depth level ahead of the other two, so for example its run N=54,55,56 corresponds to N=78,79,80 in the first quadrant.
This pattern can be generated from the 1 of 8 rule by starting from N=0 at X=0,Y=0 and then treating all points with X<0,Y<=0 as already occupied. Notice parts=3mid above is Y<0 occupied whereas here parts=3side is Y<=0.
.. 8 7 6 .. 3 -------------+ 0 2 X<0,Y<=0 * * * | 1 11 considered * * * | 4 5 10 all "on" * * * | 9 * * * | ..
The 3side pattern is the same as the 3mid but with the portion above the X=Y diagonal shifted up diagonally to X+1,Y+1 and therefore branching off the diagonal 1 depth level later. On that basis the two tree_depth_to_n() total cells are related by
Ndepth3side(depth) = (Ndepth3mid(depth) + Ndepth3mid(depth-1) + 1) / 2
For example depth=4 begins at N=17 in 3side,
Ndepth3side(4) = 17 Ndepth3mid(4) = 22, Ndepth3mid(3) = 11 (22 + 11 + 1)/2 = 17
The interest in the 3mid and 3side "corner" sequences is that a 3mid can be doubled in size by adding a "3mid" and two "3side"s.
+-------------+-------------+ | | | 3mid doubled in size | new 3side | new 3mid | by adding two new 3sides | | | and one new 3mid. | +-------------+ | | | | | | | 3mid | | | | | | +------+------+ |------+ | | | | | | | | | +------+ | | | | new 3side | | | +-------------+
Option parts => 'wedge' confines the pattern to a V-shaped wedge -Y<=X<=Y.
parts => 'wedge'
parts => "wedge" 37 36 35 34 33 32 31 30 29 28 27 26 7 25 24 21 20 6 19 18 17 23 22 16 15 14 5 13 12 4 11 10 9 8 7 6 3 5 4 2 3 2 1 1 0 <- Y=0 -------------------------------------------- -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::OneOfEight->new ()
$path = Math::PlanePath::OneOfEight->new (parts => $str)
Create and return a new path object. The parts option (a string) can be
parts
"4" full pattern (the default) "1" single quadrant "octant" single eighth "octant_up" single eighth upper "wedge" V-shaped wedge "3mid" three quadrants, middle symmetric style "3side" three quadrants, side style
@n_children = $path->tree_n_children($n)
Return the children of $n, or an empty list if $n has no children (including when $n < 1, ie. before the start of the path). The way points are numbered means the children are always consecutive N values.
$n
$n < 1
@nums = $path->tree_num_children_list()
Return a list of the possible number of children at the nodes of $path. This is the set of possible return values from tree_n_num_children(). This varies with the parts option,
$path
tree_n_num_children()
parts tree_num_children_list() ----- ------------------------ 4 0, 1, 2, 3, 5, 8 1 0, 1, 2, 3, 5 octant 0, 1, 2, 3 octant_up 0, 1, 2, 3 wedge 0, 1, 2, 3 3mid 0, 1, 2, 3, 5 3side 0, 2, 3
For parts=4 there's 8 children at the initial N=0 and after that at most 5.
For parts=3side a 1 child never occurs. There's 1 child only on the central diagonal corner X=2^k,Y=2^k and for parts=3side there's no such corner.
parts=4,1,3mid have 5 children growing out of the 1-child of the X=2^k,Y=2^k corner. In an parts=octant, octant_up, and wedge there's only 3 children around that point since that pattern doesn't go above the X=Y diagonal.
($n_lo, $n_hi) = $path->level_to_n_range($level)
Return (0, tree_depth_to_n_end(2**$level - 1), or for parts=3side tree_depth_to_n_end(2**$level).
(0, tree_depth_to_n_end(2**$level - 1)
tree_depth_to_n_end(2**$level)
parts=3side
The first point is N=0 so tree_depth_to_n($depth) is the total number of points up to and not including $depth. For the full pattern this total(depth) follows a recurrence
tree_depth_to_n($depth)
$depth
total(0) = 0 total(pow) = (16*pow^2 + 24*exp - 7) / 9 total(pow + rem) = total(pow) + 2*total(rem) + total(rem+1) - 8*floor(log2(rem+1)) + 1 where depth = pow + rem with pow=2^k the biggest power-of-2 <= depth and rem the remainder
For parts=octant the equivalent total points is
oct(0) = 0 oct(pow) = (4*pow^2 + 9*pow + 6*exp + 14) / 18 oct(pow + rem) = oct(pow) + 2*oct(rem) + oct(rem+1) - floor(log2(rem+1)) - rem - 3
The way this recurrence works can be seen from the self-similar pattern described in "One Octant" above.
oct(pow) # "base" + oct(rem) # "extend" + oct(rem) # "upper" + oct(rem+1) # "lower" - floor(log2(rem+1)) # no pow2 points in lower - rem # unduplicate diagonal upper/lower - 3 # unduplicate centre points
oct(rem)+oct(rem+1) of upper and lower would count their common diagonal twice, hence "-rem" being the length of that diagonal. The "centre" point at X=pow,Y=pow is repeated by each of extend, upper, lower so "-2" to count just once, and the X=pow+1,Y=pow point is repeated by extend and upper, so "-1" to count it just once.
The 2*total(rem)+total(rem+1) in the formula is the same recurrence as the toothpick pattern and the approach there can calculate it as a set of pending depths and pow subtractions. See "Depth to N" in Math::PlanePath::ToothpickTree.
The other patterns can be expressed as combinations of octants,
parts=4 total = 8*oct(n) - 4*n - 7 parts=1 total = 2*oct(n) - n 3mid V2 total = 2*oct(n+1) + 4*oct(n) - 3n - 2*floor(log(n+1)) - 6 3side V1 total = oct(n+1) + 3*oct(n) + 2*oct(n-1) - 3n - floor(log(n+1)) - floor(log(n)) - 4
The depth offsets n,n+1,etc in these formulas become initial pending depth for the toothpick style depth to N algorithm (and with respective initial multipliers).
From the V1,V2 formulas it can be seen that V2(n)+V2(n+1) gives the same combination of 1,3,2 times oct n-1,n,n+1 which is in V1, and that therefore as noted in the Ndepth part of "Three Side" above
V1(n) = (V2(n) + V2(n-1) + 1) / 2
This cellular automaton is in Sloane's Online Encyclopedia of Integer Sequences as
http://oeis.org/A151725 (etc)
parts=4 (the default) A151725 total cells "V", tree_depth_to_n() A151726 added cells "v" parts=1 A151735 total cells, tree_depth_to_n() A151737 added cells parts=3mid A170880 total cells, tree_depth_to_n() A151728 added cells "v2" A151727 added cells "v2" * 4 A151729 (added cells - 1) / 2 parts=3side A170879 total cells, tree_depth_to_n() A151747 added cells "v1"
Math::PlanePath, Math::PlanePath::ToothpickTree, Math::PlanePath::UlamWarburton
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2012, 2013, 2014, 2015 Kevin Ryde
This file is part of Math-PlanePath-Toothpick.
Math-PlanePath-Toothpick 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-Toothpick 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-Toothpick. If not, see <http://www.gnu.org/licenses/>.
To install Math::PlanePath::HTree, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath::HTree
CPAN shell
perl -MCPAN -e shell install Math::PlanePath::HTree
For more information on module installation, please visit the detailed CPAN module installation guide.