Kevin Ryde > Math-PlanePath-Toothpick > Math::PlanePath::OneOfEight

Download:
Math-PlanePath-Toothpick-14.tar.gz

Dependencies

Annotate this POD

Website

View/Report Bugs
Module Version: 14   Source  

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 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.

Level Ranges

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 level 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 level (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.

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  15

One Octant

Option parts => 'octant' confines the pattern to the first eighth of the plane 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 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()).

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 level 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.

Upper Octant

Option parts => 'octant_up' confines the pattern to the upper octant 0<=X<=Y of the first quadrant.

    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()).

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.

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 the full pattern, with the three square blocks there each 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  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"      *  *  *  |

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 square blocks there each 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  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

Three Growth

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 |
                  |             |
                  +-------------+

Wedge

Option parts => 'wedge' confines the pattern to a V-shaped wedge -Y<=X<=Y.

    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 

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 parts option (a string) can be

    "4"           full pattern (the default)
    "1"           single quadrant
    "octant"      single octant
    "octant_up"   single octant upper
    "wedge"       V-shaped 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 $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.

Tree Descriptive Methods

@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,

    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.

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 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

OEIS ^

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"

SEE ALSO ^

Math::PlanePath, Math::PlanePath::ToothpickTree, Math::PlanePath::UlamWarburton

HOME PAGE ^

http://user42.tuxfamily.org/math-planepath/index.html

LICENSE ^

Copyright 2012, 2013, 2014 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/>.

syntax highlighting: