NAME
Math::PlanePath::MathImageUlamWarburton -- points in quater-imaginary base 2i
SYNOPSIS
use Math::PlanePath::MathImageUlamWarburton;
my $path = Math::PlanePath::MathImageUlamWarburton->new;
my ($x, $y) = $path->n_to_xy (123);DESCRIPTION
In progress.
This is the pattern of a cellular automaton studied by Ulam and Warburton with cells numbered by growth level and anti-clockwise within the 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 9The rule is that a given cell grows up, down, left and/or right, but only if the new cell has no neighbours (up, down, left or right). So,
a initial level 0 cell
b
b a b level 1
b
c
b
c b a b c level 2
b
c
d
d c d
d b d
d c b a b c d level 3
d b d
d c d
d
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
eThe initial cell "a" is N=1, then the "b" cells are numbered N=2 to N=5 anti-clockwise from the right, and likewise the "c" cells N=6 to N=9. The "b" cells can only grow outwards for 4 "c"s, since the other up/down etc would have a neighbour in the existing "b"s.
The "d" cells are then N=10 to N=21, numbered following the previous level "c" cell order and anti-clockwise around each. Notice that there's only 4 "e" cells since the "d"s can only grow along the X,Y axes as all other up/down etc have neighbours (the existing "b"s and "d"s).
In general each level always grows by 1 along the X and Y axes and the plane in between is filled in a sort of diamond shaped tree pattern which ends up with 11 cells in each 4x4 square block.
Level Ranges
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 through N=21 because 3=0b11 has two 1 bits in binary. The N start for a level is the cumulative total of those before it,
Nstart(level) = 1 + (levelcells(0) + ... + levelcells(level-1))For example level 3 starts at N=1+(1+4+4)=10.
level Nstart levelcells
0 1 1
1 2 4
2 6 4
3 10 12
4 22 4
5 26 12
6 38 12
7 50 36
8 86 4
9 90 ...For a power-of-2 level the Nstart sum is
Nstart(2^a) = 2 + 4*(4^a-1)/3For example level=4=2^2 starts at N=2+4*(4^2-1)/3=22, or level=4=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 has bits a,b,c,d,etc in descending order,
level = 2^a + 2^b + 2^c + 2^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.
OEIS
This automaton is in Sloane's Online Encyclopedia of Integer Sequences as
A147582 - new cells in level n
A147562 - cumulative total cells to level n
http://oeis.org/A147582 etcThe A147582 new cells sequence starts from n=1, so has the innermost N=1 single cell as level n=1, then N=2 to N=5 as level n=2, etc. This makes the formula a binary ones count of n-1 rather than n the way levelcells() above has it.
The 3^(count 1 bits in level) part of the levelcells() is separately in A048883, and in A147610 with n-1.
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.
$path = Math::PlanePath::MathImageUlamWarburton->new ()-
Create and return a new path object.
($x,$y) = $path->n_to_xy ($n)-
Return the X,Y coordinates of point number
$non the path. Points begin at 1 and if$n < 0then the return is an empty list.