NAME
Math::PlanePath::OneOfEight -- automaton growing to cells with one of eight neighbours
SYNOPSIS
use Math::PlanePath::OneOfEight;
my $path = Math::PlanePath::OneOfEight->new;
my ($x, $y) = $path->n_to_xy (123);DESCRIPTION
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 growth levels and anti-clockwise on each cell within the level.
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 7The 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 any adjacent prospective new cells don't count.
At the next level only the diagonal cells X=+/-2,Y=+/-2 have a single neighbour, 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 12The children of a given node are numbered anti-clockwise relative to the position of the parent of that node. So for example N=9 has it's parent south-west and points are numbered anti-clockwise around from there to give N=13 through N=17.
Level Ranges
The pattern always extends along the X=+/-Y diagonals, and extends to 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=0to3,Y=0to3 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 depth=2^k for k>=0 is
Ndepth(2^k) = (16*4^k + 24*k - 7) / 9
= (16*depth*depth + 24*k - 7) / 9
eg. k=3 Ndepth=121Because points are numbered from N=0 this is how many cells are "on" in the pattern before this depth level. 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 -> infinityThis density is approached from above, ie. density(k) decreases towards 4/9 as k increases. The first k=0 is the single origin point which is 1/1, and k=2 is 9/9 of the 3x3 at the origin. Then for example k=2 7x7 square has 33/49=0.673, then k=3 121/225=0.5377, etc.
One Quadrant
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
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 15One Octant
Option parts => 'octant' confines the pattern to the first octant 0<=Y<=X.
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 15The full pattern is symmetric on each size 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 |
-- |
--------------|
--| -- upper |
-- | -- flip |
-- | -- |
-- | lower -- |
-- base | depth+1 -- |
-- | no pow2s --|
-----------------------------"extend" is a direct copy of the "base" block and the "upper" likewise except flipped vertically.
The "lower" block 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. It ends at N=45,46,47,48 depth=14 whereas the corresponding N=62,63,64,65 in the "extend" is at 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 the branches off the diagonal are offset by 1 position. For example N=34,33,37 branching off to the lower corresponds to N=40,41,51 branching into the upper.
This offset on the upper/lower diagonal becomes easier to see by chopping off one level of leaf nodes.
*
*
*
* octant with leaf nodes pruned
* *
* *
*
*
* *
* * *
* * * <- upper,lower parts
* * * branch off lower is 1 level sooner
* * * *
* * *
*
* It may look at first as if the square side block comprising "upper" and "lower" is entirely different from the central symmetric square (of "One Quadrant" above), but that's not so, it's just the offset of the branching from the diagonal.
Three Mid
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 that pattern, with the three parts there extended indefinitely.
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 7The first quadrant X>=0,Y>=0 is the same as in the full pattern, but the other quadrants are a "side" portion of the pattern.
This pattern can be generated from the automaton rule by starting from N=0 at X=0,Y=0 and then treating all points with X<0,Y<0 as if already occupied.
.. .. .. ..
9 8 ..
10 5 4 3 ..
0 2
-------------+ 1
X<0,Y<0 * * * | 6 7 ..
considered * * * |
all "on" * * * |Three Side
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 parts there extended indefinitely.
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 8The Y negative 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 automaton 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 3mid above is Y<0 whereas here 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
N3side(depth) = (N3mid(depth) + N3mid(depth-1) + 1) / 2For example depth=4 begins at N=17 in 3side,
N3side(4) = 17
N3mid(4) = 22, N3mid(3) = 11
(22 + 11 + 1)/2 = 17Three Growth
The interest in the 3mid and 3side "corner" sequences is that a base 3mid can be doubled in size by adding one "3mid" and two "3side"s.
+-------------+-------------+
| | | 3mid doubled in size
| new 3side | new 3mid | by adding two new 3sides
| | | and one new 3mid.
| +-------------+ |
| | | |
| | start 3mid | |
| | | |
+------+------+ |------+
| | |
| | |
| | |
+------+ |
| |
| new 3side |
| |
+-------------+FUNCTIONS
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
partsoption (a string) can be"4" full pattern (the default) "1" single quadrant "octant" single octant wedge "3mid" three quadrants, middle symmetric style "3side" three quadrants, side style
Tree Methods
@n_children = $path->tree_n_children($n)-
Return the children of
$n, or an empty list if$nhas 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.The children are the new cells turned "on" adjacent to
$nat the next depth level. The possible number of children varies with the parts,parts possible num children ----- --------------------- 4 0, 1, 2, 3, 5, 8 1 0, 1, 2, 3, 5 octant 0, 1, 2, 3 3mid 0, 1, 2, 3, 5 3side 0, 2, 3For parts=4 there's 8 children at the initial N=0 and after that at most 5.
1 child only occurs at X=2^k,Y=2^k of the central diagonal In parts=3side there's no such corner and never a single child, only 2 or 3 children.
5 children occurs around the 1-child of X=2^k,Y=2^k in parts=4,1,3mid. In an octant there's only 3 children around that point since that pattern doesn't go above the X=Y diagonal.
FORMULAS
Depth to N
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
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 remainderFor 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 - 3The way this recurrence formula 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 pointsThe oct(rem)+oct(rem+1) of upper+lower parts 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 little 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)) - 4The set of depth offsets n,n+1,etc become initial depth values in the list for the recurrence reduction algorithm, 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 octants as V1, and that therefore as noted in the Ndepth part of "Three Side" above
V1(n) = (V2(n) + V2(n-1) + 1) / 2OEIS
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"
parts=3side
A170879 total cells (tree_depth_to_n())
A151747 added cells "v1"SEE ALSO
Math::PlanePath, Math::PlanePath::ToothpickTree, Math::PlanePath::UlamWarburton
HOME PAGE
http://user42.tuxfamily.org/math-planepath/index.html
LICENSE
Copyright 2012, 2013 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/>.