Tree Row Ranges¶

Counting depth=0 as the N=1 at the origin, depth=1 as the next N=2, etc, the number of new cells added in the tree row is

    rowwidth(depth) = 3^(count_1_bits(depth+1) - 1)

So depth=0 has 3^(1-1)=1 cells, as does depth=1 which is N=2. Then depth=2 has 3^(2-1)=3 cells N=3,N=4,N=5 because depth+1=3=0b11 has two 1 bits in binary. The N row start and end is the cumulative total of those before it,

    Ndepth(depth) = 1 + rowwidth(0) + ... + rowwidth(depth-1)
    Nend(depth) = rowwidth(0) + ... + rowwidth(depth)

For example depth=2 ends at N=(1+1+3)=5.

    depth    Ndepth    rowwidth      Nend
      0          1         1           1
      1          2         1           2
      2          3         3           5
      3          6         1           6
      4          7         3           9
      5         10         3          12
      6         13         9          21
      7         22         1          22
      8         23         3          25

At row depth+1 = power-of-2 the Ndepth sum is

    Ndepth(depth) = 1 + (4^a-1)/3       for depth+1 = 2^a

For example depth=3 is depth+1=2^2 starts at N=1+(4^2-1)/3=6, or depth=7 is depth+1=2^3 starts N=1+(4^3-1)/3=22.

Further bits in the depth+1 contribute powers-of-4 with a tripling for each bit above it. So if depth+1 has bits a,b,c,d,etc from high to low then

    depth+1 = 2^a + 2^b + 2^c + 2^d ...       a>b>c>d...
    Ndepth = 1 + (-1
                  +       4^a
                  +   3 * 4^b
                  + 3^2 * 4^c
                  + 3^3 * 4^d + ...) / 3

For example depth=5 is depth+1=6 = 2^2+2^1 is Ndepth = 1+(4^2-1)/3 + 4^1 = 10. Or depth=6 is depth+1=7 = 2^2+2^1+2^0 is Ndepth = 1+(4^2-1)/3 + 4^1 + 3*4^0 = 13.

Self-Similar Replication¶

The square shape growth to depth=2^level-2 repeats the pattern to the preceding depth=2^(level-1)-2 three times. For example,

    |  d   d   c   c             depth=6 = 2^3-2
    |    d       c               triplicates
    |  d   d   c   c             depth=2 = 2^2-2
    |        *
    |  a   a   b   b
    |    a       b
    |  a   a   b   b
    +--------------------

The 3x3 square "a" repeats, pointing SE, NE and NW as "b", "c" and "d". This resulting 7x7 square then likewise repeats. The points in the path here are numbered by tree rows rather than by this sort of replication, but the replication helps to see the structure of the pattern.

Octant¶

Option "parts => 'octant'" confines the pattern to the first eighth of the plane 0<=Y<=X.

    parts => "octant"
     14 |                                           50
     13 |                                        36
     12 |                                     31    49
     11 |                                  26
     10 |                               24    30    48
      9 |                            19          35
      8 |                         17    23    46    47
      7 |                      15
      6 |                   14    16    22    45    44
      5 |                 9          18          34
      4 |              7    13    20    21    29    43
      3 |           5                      25
      2 |        4     6    12    37    27    28    42
      1 |     2           8          32          33
    Y=0 |  1     3    10    11    38    39    40    41
        +-------------------------------------------------
         X=0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15

In this arrangement N=1,2,4,5,7,etc on the leading diagonal is the last N of each row (tree_depth_to_n_end()).

Upper Octant¶

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

    parts => "octant_up"
     14 | 46    45    44    43    40    39    38    37
     13 |    35          34          33          32
     12 | 47    30    29    42    41    28    27
     11 |          26                      25
     10 | 48    31    23    22    21    20
      9 |    36          19          18
      8 | 49    50    24    17    16
      7 |                      15
      6 | 13    12    11    10
      5 |     9           8
      4 | 14     7     6
      3 |           5
      2 |  4     3
      1 |     2
    Y=0 |  1
        +----------------------------------------------
          X=0 1  2  3  4  5  6  7  8  9 10 11 12 13 14

In this arrangement N=1,2,3,5,6,etc on the leading diagonal is the first N of each row (tree_depth_to_n()).

N Start¶

The default is to number points starting N=1 as shown above. An optional "n_start" can give a different start, in the same pattern. For example to start at 0,

    n_start => 0
     7 |                      21
     6 | 19    18    17    16
     5 |    11          10
     4 | 20     8     7    15
     3 |           5
     2 |  4     3     6    14
     1 |     1           9
    Y=0|  0     2    12    13
       +-------------------------
        X=0  1  2  3  4  5  6  7

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 children are the cells turned on adjacent to $n at the next row. The way points are numbered means that when there's multiple children they're consecutive N values, for example at N=12 the children 19,20,21.

"$n_parent = $path->tree_n_parent($n)"

Return the parent node of $n, or "undef" if "$n <= 1" (the start of the path).

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

    parts        tree_num_children_list()
    -----        ------------------------
      1              0, 1,    3
    octant           0, 1, 2, 3
    octant_up        0, 1, 2, 3
    

The octant forms have 2 children when branching from the leading diagonal, otherwise 0,1,3.

Level Methods¶

"($n_lo, $n_hi) = $path->level_to_n_range($level)"

Return "($n_start, tree_depth_to_n_end(2**($level+1) - 2))".