Math::PlanePath::UlamWarburton -- growth of a 2-D cellular automaton
use Math::PlanePath::UlamWarburton; my $path = Math::PlanePath::UlamWarburton->new; my ($x, $y) = $path->n_to_xy (123);
This is the pattern of a cellular automaton studied by Ulam and Warburton, numbering cells by growth level and anti-clockwise within their level.
94 9 95 87 93 8 63 7 64 42 62 6 65 30 61 5 66 43 31 23 29 41 60 4 69 67 14 59 57 3 70 44 68 15 7 13 58 40 56 2 96 71 32 16 3 12 28 55 92 1 97 88 72 45 33 24 17 8 4 1 2 6 11 22 27 39 54 86 91 <- Y=0 98 73 34 18 5 10 26 53 90 -1 74 46 76 19 9 21 50 38 52 ... -2 75 77 20 85 51 -3 78 47 35 25 37 49 84 -4 79 36 83 -5 80 48 82 -6 81 -7 99 89 101 -8 100 -9 ^ -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 8 9
The rule is that a given cell grows up, down, left and right, but only if the new cell has no neighbours (up, down, left or right). So the initial cell "a" is N=1,
a initial level 0 cell
The next level "b" cells are numbered N=2 to N=5 anti-clockwise from the right,
b b a b level 1 b
Likewise the next level "c" cells N=6 to N=9. The "b" cells only grow outwards as 4 "c"s since the other positions would have neighbours in the existing "b"s.
c b c b a b c level 2 b c
The "d" cells are then N=10 to N=21, numbered following the previous level "c" cell order and then anti-clockwise around each.
d d c d d b d d c b a b c d level 3 d b d d c d d
There's only 4 "e" cells since among the "d"s only the X,Y axes won't have existing neighbours (the "b"s and "d"s).
e d d c d d b d e d c b a b c d e level 4 d b d d c d d e
In general each level always grows by 1 along the X and Y axes and travels into the quarter planes between with a sort of diamond shaped tree pattern which fills 11 cells of each 4x4 square block.
Counting level 0 as the N=1 at the origin and level 1 as the next N=2,3,4,5 generation, the number of new cells added in a growth level is
levelcells(0) = 1 then levelcells(level) = 4 * 3^((count 1 bits in level) - 1)
So level 1 has 4*3^0=4 cells, as does level 2 N=6,7,8,9. Then level 3 has 4*3^1=12 cells N=10 to N=21 because 3=0b11 has two 1 bits in binary. The N start and end for a level is the cumulative total of those before it,
Nstart(level) = 1 + (levelcells(0) + ... + levelcells(level-1)) Nend(level) = levelcells(0) + ... + levelcells(level)
For example level 3 ends at N=(1+4+4)=9.
level Nstart levelcells Nend 0 1 1 1 1 2 4 5 2 6 4 9 3 10 12 21 4 22 4 25 5 26 12 37 6 38 12 49 7 50 36 85 8 86 4 89 9 90 12 101
For a power-of-2 level the Nstart is
Nstart(2^a) = 2 + 4*(4^a-1)/3
For example level=4=2^2 starts at N=2+4*(4^2-1)/3=22, or level=8=2^3 starts N=2+4*(4^3-1)/3=86.
Further bits in the level value contribute powers-of-4 with a tripling for each bit above. So if the level number has bits a,b,c,d,etc in descending order,
level = 2^a + 2^b + 2^c + 2^d ... a>b>c>d... Nstart = 2 + 4*(4^a-1)/3 + 4^(b+1) + 3 * 4^(c+1) + 3^2 * 4^(d+1) + ...
For example level=6 = 2^2+2^1 is Nstart = 1 + (1+4*(4^2-1)/3) + 4^(1+1) = 38. Or level=7 = 2^2+2^1+2^0 is Nstart = 1 + (1+4*(4^2-1)/3) + 4^(1+1) + 3*4^(0+1) = 50.
The diamond shape growth up to a level 2^a repeats three times. For example an "a" part going to the right,
d d d d a d c a a a * c c c ... a b c b b b b
The 2x2 diamond shaped "a" repeats pointing up, down and right as "b", "c" and "d". This resulting 4x4 diamond then likewise repeats up, down and right. The points in the path here are numbered by growth level rather than in this sort of replication, but the replication helps to see the structure of the pattern.
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::UlamWarburton->new ()
Create and return a new path object.
($x,$y) = $path->n_to_xy ($n)
Return the X,Y coordinates of point number $n on the path. Points begin at 1 and if $n < 0 then the return is an empty list.
$n
$n < 0
@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).
$n < 1
The children are the cells turned on adjacent to $n at the next level. This can be none, one or three points; or four at the initial N=1. The way points are numbered means that when there's multiple children they're consecutive N values, for example at N=6 the children are 10,11,12.
$num = $path->tree_n_num_children($n)
Return the number of children of $n, or 0 if $n has no children.
$n_parent = $path->tree_n_parent($n)
Return the parent node of $n, or undef if $n <= 1 (the start of the path).
undef
$n <= 1
This cellular automaton is in Sloane's Online Encyclopedia of Integer Sequences as
http://oeis.org/A147582 (etc) A147562 - cumulative total cells to level n, being Nend(level) A147582 - number of new cells in level n
The A147582 new cells sequence starts from n=1, so takes the innermost N=1 single cell as level n=1, then N=2,3,4,5 as level n=2 with 5 cells, etc. This makes the formula a binary 1-bits count on n-1 rather than on N the way levelcells() above is expressed.
The 1bits-count power 3^(count 1 bits in level) part of the levelcells() is also separately in A048883, and as n-1 in A147610.
Math::PlanePath, Math::PlanePath::CellularRule
Math::PlanePath::SierpinskiTriangle (a similar binary ones-count related level calculation)
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2011, 2012 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/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.