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

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

Dependencies

Annotate this POD

Website

View/Report Bugs
Module Version: 13   Source  

NAME ^

Math::PlanePath::ToothpickTree -- toothpick pattern by growth levels

SYNOPSIS ^

 use Math::PlanePath::ToothpickTree;
 my $path = Math::PlanePath::ToothpickTree->new;
 my ($x, $y) = $path->n_to_xy (123);

DESCRIPTION ^

This is the "toothpick" sequence expanding through the plane by non-overlapping line segments as per

David Applegate, Omar E. Pol, N.J.A. Sloane, "The Toothpick Sequence and Other Sequences from Cellular Automata", Congressus Numerantium, volume 206 (2010), 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.

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

                       ^
      -4   -3 -2  -1  X=0  1   2   3   4

Each X,Y is the centre of a toothpick of length 2. The first toothpick is vertical at the origin X=0,Y=0.

A toothpick is added at each exposed end, perpendicular to that end. So N=1 and N=2 are added to the two ends of the initial N=0 toothpick. Then points N=3,4,5,6 are added at the four ends of those.

                                               ---8--- ---7---
                              |       |           |       |
             ---1---          4---1---3           4---1---3
    |           |             |   |   |           |   |   |
    0   ->      0       ->        0        ->         0
    |           |             |   |   |           |   |   |
             ---2---          5---2---6           5---2---6
                              |       |           |       |
                                               ---9--- --10---

Toothpicks are not added if they would overlap. This means no toothpick at X=1,Y=0 where the ends of N=3 and N=6 meet, and likewise not at X=-1,Y=0 where N=4 and N=5 meet.

The end of a new toothpick is allowed to touch an existing toothpick. The first time this happens is N=15 where its left end touches N=3.

The way each toothpick is perpendicular to the previous means that at even depth the toothpicks are all vertical and on "even" points X==Y mod 2. Conversely at odd depth all toothpicks are horizontal and on "odd" points X!=Y mod 2. (The initial N=0 is depth=0.)

The children at a given depth are numbered in order of their parents, and anti-clockwise around when there's two children.

            |       |
            4---1---3         points 3,4 numbered
            |   |   |         anti-clockwise around
                0
                |

Anti-clockwise here is relative to the direction of the grandparent node. So for example at N=1 its parent N=0 is downwards and the children of N=1 are then anti-clockwise around from there, hence first the right side for N=3 and then the left for N=4.

Cellular Automaton

The toothpick rule can also be expressed as growing into a cell which has just one of its two vertical or horizontal neighbours "ON", using either vertical or horizontal neighbours according to X+Y odd or even.

          Point            Grow
    ------------------   ------------------------------------------
    "even", X==Y mod 2   turn ON if 1 of 2 horizontal neighbours ON
    "odd",  X!=Y mod 2    turn ON if 1 of 2 vertical neighbours ON

For example X=0,Y=1 which is N=1 turns ON because it has a single vertical neighbour (the origin X=0,Y=0). But the cell X=1,Y=0 never turns ON because initially its two vertical neighbours are OFF and then later at depth=3 they're both ON. Only when there's exactly one of the two neighbours ON in the relevant direction does the cell turn ON.

In the paper section 10 above this variation between odd and even points is reckoned as an automaton on a directed graph where even X,Y points have edges directed out horizontally, and conversely odd X,Y points are directed out vertically.

         v          ^         v          ^         v
    <- -2,2  ---> -1,2  <--- 0,2  --->  1,2 <---  2,2 --
         ^          |         ^          |         ^
         |          v         |          v         |
    -> -2,1  <--- -1,1  ---> 0,1  <---  1,1 --->  2,1 <-
         |          ^         |          ^         |
         v          |         v          |         v
    <- -2,0  ---> -1,0  <--- 0,0  --->  1,0 <---  2,0 ->
         ^          |         ^          |         ^
         |          v         |          v         |
    -> -2,-1 <--- -1,-1 ---> 0,1  <--- 1,-1 ---> 2,-1 <-
         |          ^         |          ^         |
         v          |         v          |         v
    <- -2,-2 ---> -1,-2 <--- 0,-2 ---> 1,-2 <--- 2,-2 ->
         ^          v         ^          v         ^

The rule on this graph is then that a cell turns ON if precisely one of it's neighbours is ON, looking along the outward directed edges. For example X=0,Y=0 starts as ON then the cell above X=0,Y=1 considers its two outward-edge neighbours 0,0 and 0,2, of which just 0,0 is ON and so 0,1 turns ON.

Replication

Within each quadrant the pattern repeats in blocks of a power-of-2 size, with an extra two toothpicks "A" and "B" in the middle.

    |
    |------------+------------A
    |            |            |
    |  block 3       block 2  |      in each quadrant
    |   mirror        same    |
    |     ^            ^      |
    |      \   --B--  /       |
    |       \    |   /        |
    |----------  A         ---+
    |            |            |
    |  block 0       block 1  |
    |     ^      |  \ rot +90 |
    |    /       |   \        |
    |   /        |    v       |
    +----------------------------

Toothpick "A" is at a power-of-2 position X=2^k,Y=2^k and toothpick "B" is above it. The B toothpick leading to blocks 2 and 3 means block 1 is one growth level ahead of blocks 2 and 3.

In the first quadrant of the diagram above, N=3,N=7 is block 0 and those two repeat as N=15,N=23 block 1, and N=24,N=35 block 2, and N=25,36 block 3. The rotation for block 1 can be seen. The mirroring for block 3 can be seen at the next level (the diagram of the "One Quadrant" form below extends to there).

The initial N=3,N=7 can be thought of as an "A,B" middle pair with empty blocks before and surrounding.

See Math::PlanePath::ToothpickReplicate for a digit-based replication instead of by growth levels.

Level Ranges

Each "A" toothpick is at a power-of-2 position,

   "A" toothpick
   -------------
   X=2^k, Y=2^k
   depth = 4^k              counting from depth=0 at the origin
   N = (8*4^k + 1)/3        N=3,11,43, etc
     = 222...223 in base4

N=222..223 in base-4 arises from the replication described above. Each replication is 4*N+2 of the previous, after the initial N=0,1,2.

The "A" toothpick coming out of corner of block 2 is the only growth from a depth=4^k level. The sides of blocks 1 and 2 and blocks 2 and 3 have all endpoints meeting and so stop by the no-overlap rule, as can be seen for example N=35,36,37,38 across the top above.

The number of points visited approaches 2/3 of the plane. This be seen by expressing the count of points up to "A" as a fraction of the area (in all four quadrants) to there,

    N to "A"   (8*4^k + 1)/3      8/3 * 4^k
    -------- = -------------   -> --------- = 2/3
    Area X*Y   (2*2^k)*(2*2^k)    4   * 4^k

One Quadrant

Option parts => 1 confines the pattern to the first quadrant, starting from N=0 at X=1,Y=1 which is the first toothpick wholly within that first quadrant. This is a single copy of the repeating part in each of the four quadrants of the full pattern.

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

The "A" toothpick at X=2^k,Y=2^k is

    N of "A" = (2*4^k - 2)/3 = 2,10,42,etc
             = "222...222" in base 4

The repeating part starts from N=0 here so there's no initial centre toothpicks like the full pattern. This means the repetition is a plain 4*N+2 and hence a N="222..222" in base 4. It also means the depth is 2 smaller, since N=0 depth=0 at X=1,Y=1 corresponds to depth=2 in the full pattern.

Half Plane

Option parts => 2 confines the tree to the upper half plane Y>=1, giving two symmetric parts above the X axis. N=0 at X=0,Y=1 is the first toothpick of the full pattern which is wholly within this half plane.

    parts => 2

    ...                             ...           5
     |                               |
    22--20--  --19--  --18--  --17--21            4
     |   |       |       |       |   |
    ... 15---9--14      13---8--12  ...           3
         |   |               |   |
             6---4--  ---3---5                    2
         |   |   |       |   |   |
        16--10-  2---0---1 --7--11                1
         |       |       |       |
                                             <- Y=0
    -----------------------------------
                     ^
    -4  -3  -2  -1  X=0  1   2   3   4

Three Parts

Option parts => 3 is the three replications which occur from an X=2^k,Y=2^k point, continued on indefinitely confined to the upper and right three quadrants.

    parts => 3

    ..--32--  --31--  --30--  --29--..           4
         |       |       |       |
        26--18--25      24--17--23               3
         |   |               |   |
            12---8--  ---7--11                   2
         |   |   |       |   |   |
        27--19-  5---2---4 -16--22               1
         |       |   |   |       |
                     0                      <- Y=0
                     |   |       |
                  ---1---3 -15--21              -1
                         |   |   |
                     9---6--10                  -2
                     |       |   |
                  --13--  --14--20              -3
                                 |
                            ..--28--..          -4

                     ^
    -4  -3  -2  -1  X=0  1   2   3   4

The bottom right quarter is rotated by 90 degrees as per the "block 1" growth from a power-of-2 corner. This means it's not the same as the bottom right of parts=4. But the two upper parts are the same as in parts=4 and parts=2.

As noted by David Applegate and Omar Pol in OEIS A153006, the three parts replication means that N at the last level of a power-of-2 block is a triangular number,

    depth=2^k-1
    N(depth) = (2^k-1)*2^k/2
             = triangular number depth*(depth+1)/2
    at X=(depth-1)/2, Y=-(depth+1)/2

For example depth=2^3-1=7 begins at N=7*8/2=28 and is at the lower right corner X=(7-1)/2=3, Y=-(7+1)/2=-4. If the depth is not such a 2^k-1 then N(depth) is less than the triangular depth*(depth+1)/2.

One Octant

Option parts => 'octant' confines the quadrant pattern to the first octant 0<=Y<=X+1. This means the stairstep diagonal spine and everything below.

    parts => "octant"

      9 |                                30-..
        |                                 |
      8 |                            27--28
        |                             |   |
      7 |                        22--26  29-..
        |                         |
      6 |                    14--17
        |                     |   |
      5 |                10--12  21--25
        |                 |
      4 |             7---8
        |             |   |
      3 |         4---6   9--11  20--24
        |         |           |   |
      2 |     1---2      15--13--16
        |     |   |       |       |
      1 |     0   3---5  18      19--23
        |
    Y=0 |
        +-----------------------------------
         X=0  1   2   3   4   5   6   7   8

In this arrangement N=0,1,2,4,6,7,8,10,etc on the stairstep diagonal is the last N of each row (tree_depth_to_n_end()). The lines show the parent to child descents.

The octant is self similar in blocks

                              --|
                            --  |
                          --    |
                        --      |
                      -- extend |
                    --          |
          2^k,2^k --------------|
                --| --   upper  |
              --  |   --  flip  |
            --    |     --      |
          --      | lower --    |
        --  base  | depth+1 --  |
      --          |           --|
    -----------------------------

"Upper" and "extend" are mirror images vertically. "Lower" is one depth level ahead of the other parts.

In the sample points shown above N=9 is the start of the "lower" copy of N=0. N=11 is the "upper" copy, which is 1 depth level later. Then N=12 is the "extend" copy. The points N=7,8,10 are extras in between the replications.

"Upper" and "lower" together make a square the same as the parts=1 style quadrant, though here it stops at the X axis to be just a 2^k size block. A quadrant consists of two octants with 1 depth level offset.

Upper Octant

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

    parts => "octant_up"

      9 |    90 76    77 42 37 30 28 29
      8 |    26    25    24    23 27
      7 |    21 16 20    19 15 18
      6 |       14 12    11 13
      5 |    22 17 10  8  9
      4 |     6     5  7
      3 |     4  2  3
      2 |     0  1
      1 |
    Y=0 |
        +-------------------------------
         X=0  1  2  3  4  5  6  7  8  9

In this arrangement N=0,1,2,3,5,7,8,9,etc on stairstep diagonal is the first N of each row (tree_depth_to_n()).

The pattern is a mirror image of parts=octant, mirrored across a line Y=X+0.5 which is the middle of the stairstep 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.

Wedge

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

    parts => "wedge"

    59 57    56    55    54    53    52    51    50 58        8
       49 39 48    47 38 46    43 35 42    41 34 40           7
          33 29    28 32          31 27    26 30              6
             25 21 24 37 45    44 36 23 20 22                 5
                19 17    16    15    14 18                    4
                   13  9 12    11  8 10                       3
                       7  5     4  6                          2
                          3  1  2                             1
                             0                          <-   Y=0
    ---------------------------------------------------
    -8 -7 -6 -5 -4 -3 -2 -1 X=0 1  2  3  4  5  6  7  8

This is two copies of the parts=octant_up, plus initial points N=0 and N=1. In terms of toothpicks the wedge restriction is toothpicks which are wholly within a wedge -Y-1<=X<=Y+1.

       |                               |
      19--17--  --16--  --15--  --14--18               4
       |   |       |       |       |   |
          13---9--12      11---8--10                   3
           |   |               |   |
               7---5--- ---4---6                       2
               |   |       |   |
                   3---1---2                           1
                   |   |   |
                       0                          <- Y=0
                       |

Two Horizontal

Option parts => 'two_horiz' starts the pattern from two horizontal toothpicks in the style of OEIS A160158 by Omar Pol. The two initial N=0 and N=1 are the roots of two trees extending to the right and left. Points are numbered breadth-wise anti-clockwise starting from N=0 on the right.

    parts => "two_horiz"

                   |               |
    --53      52--60              59--51      50--           4
       |       |   |               |   |       |
      43--32--42  72--92      91--71  41--31--40             3
           |                               |
          26--21      20      19      18--25                 2
           |   |       |       |       |   |
      44--33  13---6--12      11---5--10  30--39             1
                   |               |
                   3---1   .   0---2                    <- Y=0
                   |               |
      45--34  14---7--15       8---4---9  29--38            -1
           |   |       |       |       |   |
          27--22      23      16      17--24                -2
           |                               |
      46--35--47  79-103      80--64  36--28--37            -3
       |       |   |               |   |       |
    --54      55--63              56--48      49--          -4
                   |               |
                           ^
      -5  -4  -3  -2  -1  X=0  1   2   3   4   5

The effect is to make octants branching off the central stair-step diagonal spine in each quadrant.

                \   oct | oct   /
                  \     |     /
    oct 2 behind    \   |   /   oct 2 behind
                      \ | /
                --------+--------
                      / | \
    oct 2 behind    /   |   \   oct 2 behind
                  /     |     \
                /  oct  |  oct  \

The four octants near the Y axis begin immediately. The N=0 and N=2 points are shared by the central octants going up and down on the right, and likewise N=1,N=3 on the left.

The four octants near the X axis begin 3 depth levels later. This is not the same as the quadrants of the full pattern (their opposite octants are 1 depth level offset). For example the point N=10 at depth=3 is the start of the lower octant in that quarter. A bigger picture than what's shown above makes this easier to see.

Octant Vertical or Horizontal

The parts=octant pattern is half a parts=1 quadrant across the diagonal. It's also interesting to note that an octant is half a quadrant by taking just the vertical or horizontal toothpicks in the quadrant (taking vertical or horizontal according to the orientation of the last level in the octant).

    oct(d) = quad_verticals(d) + floor(d/2)    if d odd
             quad_horizontals(d) + floor(d/2)  if d even

    d = depth starting from 0 per tree_depth_to_n()

This works because in a quadrant the vertical toothpicks above the X=Y diagonal can be folded down across the diagonal to become horizontal and complete the lower octant.

     quadrant verticals                 octant made by quadrant
   numbered by depth level            upper verticals fold down
                                      to become horizontals

    |       |       |       |                                  |
   12      12      12      12                           ......12
    |   |   |       |   |   |                              |   |
       10              10                           ......10
    |   |   |       |   |   |                          |   |   |
   12       8       8      12                    ......8 -12--12
    |       |   |   |       |                      |   |       |
                6                            ......6
    |       |   |   |       |                  |   |   |       |
    4       4       8      12            ......4 --8---8 -12--12
    |   |   |   |   |   |   |              |   |       |   |   |
        2      10      10             .....2      10--10--10
    |   |   |   |       |   |          |   |   |   |       |   |
    0       4              12          0 --4---4 -12--   -12--12
    |       |               |          |       |               |

For example the vertical level "4" toothpick which is above the X=Y diagonal folds down to become the horizontal "4" in the lower octant. Similarly the block of five 8,10,12,12,12 above the diagonal fold down to make five horizontals. And the final 12 above becomes the horizontal 12.

However the horizontals which are on the central diagonal spine don't have corresponding verticals above. These are marked "....." in the octant shown above. This means 1 toothpick missing at every second depth level and therefore the floor(depth/2) in the oct() formula above.

The key is that a quadrant has the upper octant running 1 depth level behind the lower. So the horizontals in the lower correspond to the verticals in the upper (and vice-versa).

The correspondence can be seen algebraically in the formula for a quadrant,

    quad(d) = oct(d) + oct(d-1) + d

reversed to

    oct(d) = quad(d) - oct(d-1)

and the oct(d-1) term repeatedly expanded

    oct(d) = quad(d) - (quad(d-1) - oct(d-2) + d-1) + d
           = quad(d)-quad(d-1)+1 + oct(d-2)
           = ...
           = quad(d)-quad(d-1)+1 + quad(d-2)-quad(d-3)+1 + ...
           = quad(d)-quad(d-1) + quad(d-2)-quad(d-3) + ... + floor(d/2)

The difference quad(d)-quad(d-1) is the number of toothpicks added to make depth level d, and similarly quad(d-2)-quad(d-3) the number added to make depth d-2. This means the number added at every second level, so if d is even then this counts only the vertical toothpicks added. Or if d is odd then only the horizontals.

The +d, +(d-1), +(d-2) additions from the quad(d) formula have alternating signs and so cancel out to be +1 per pair, giving floor(d/2).

The parts=wedge pattern is two octants and therefore the wedge corresponds to the horizontals or verticals of parts=2 which is two quadrants. But there's an adjustment to make there though since parts=2 doesn't have a toothpick at the origin the way the wedge does.

Quadrant and 2^k-1 Sums

In OEIS A168002 (http://oeis.org/A168002) Omar Pol observed that the quadrant(d) total cells taken mod 2 gives the number of ways d can be expressed as a sum of terms 2^k-1.

    d = (2^a - 1) + (2^b - 1) + (2^c - 1) + ...
    distinct a,b,c,...

There's only ever 0 or 1 way to write d as a sum of 2^k-1 terms, ie. d either is or is not such a sum. For example,

     d      ways
    ---     ----
     8       1     8 = 7+1
     9       0     no sum possible
     10      1     10 = 7+3
     11      1     11 = 7+3+1
     12      0     no sum possible

The sum can be formed by taking the highest possible 2^k-1 from d repeatedly. This works because smaller 2^k-1 terms are not big enough to add up to that highest term. The result is a recurrence

    ways(2^k-1)       = 1
    ways(2^k-1 + rem) = ways(rem)       1 <= rem < 2^k-1
    ways(2*(2^k-1))   = 0)

The quadrant total cells follows a similar recurrence when taken mod 2. Using the quadrant count Q(d) in the paper by Applegate, Pol, Sloane above

    Q(d) = (T(d) - 3)/4

    numbered same as T,
    so Q(2)=0 then first quadrant toothpick Q(3)=1

Substituting the recurrences for T in the paper gives

    Q(2^k) = (4^k-4)/6
    Q(2^k+1) = Q(2^k) + 1
    Q(2^k + rem) = Q(2^k) + Q(rem+1) + 2*Q(rem) + 2
       for 2 <= rem < 2^k

Taking these modulo 2

    Q(2^k)   == 0 mod 2     since (4^k-4)/6 always even
    Q(2^k+1) == 1 mod 2
    Q(2^k + rem) == Q(rem+1) mod 2       2 <= rem < 2^k

    Q(2^k-1 + rem) == Q(rem) mod 2       1 <= rem < 2^k-1

The last formula is the key, being the same as the ways(2^k-1 + rem) recurrence above. Then Q(2^k)=0 corresponds to ways(2^k-2)=0, and Q(2^k+1)=1 corresponding to ways(2^k-1)=1. And therefore

    Q(d-2) == ways(d) mod 2

FUNCTIONS ^

See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.

$path = Math::PlanePath::ToothpickTree->new ()
$path = Math::PlanePath::ToothpickTree->new (parts => $integer)

Create and return a new path object. parts can be 1, 2, 3 or 4.

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 < 0, ie. before the start of the path).

The children are the new toothpicks added at the ends of $n at the next level. This can be 0, 1 or 2 points. For example in the parts=4 default N=24 has no children, N=8 has a single child N=12, and N=2 has two children N=4,N=5. The way points are numbered means that if there are two children then they're consecutive N values.

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

Return the parent node of $n, or undef if no parent due to $n <= 0 (the start of the path).

$depth = $path->tree_n_to_depth($n)
$n = $path->tree_depth_to_n($depth)

Return the depth of point $n, or first $n at given $depth, respectively.

The first point N=0 is depth=0 in all "parts" forms. The way parts=1 and parts=2 don't start at the origin means their depth at a given X,Y differs by 2 or 1 respectively from the full pattern at the same point.

Tree Descriptive Methods

$num = $path->tree_num_roots ()

Return the number of root nodes in $path. This is 1 except for parts=two_horiz which is 2.

$num = $path->tree_num_children_minimum()
$num = $path->tree_num_children_maximum()

Return minimum 0 and maximum 2 since each node has 0, 1 or 2 children.

FORMULAS ^

Depth to N

The first N at given depth is the total count of toothpicks in the preceding levels. The paper by Applegate, Pol and Sloane above gives formulas for parts=4 and parts=1. A similar formula can be made for parts=octant.

The depth in all the following is per the full pattern, which means the octant starts at depth=2. So oct(2)=0 then oct(3)=1. This reckoning keeps the replications on 2^k boundaries and is convenient for relating an octant to the full pattern. Note though that tree_depth_to_n() always counts from $depth = 0 so an adjustment +1 or +2 is applied there.

    for depth >= 2
    depth = pow + rem    where pow=2^k is the high bit of depth
                         so 0 <= rem < 2^k

    oct(2) = 0
    oct(pow) = (pow*pow - 16)/12 + pow/2
    oct(pow+1) = oct(pow) + 1
    oct(pow+rem) = oct(pow) + oct(rem+1) + 2*oct(rem) - rem + 4
                   for 2 <= rem < pow

The other parts patterns can be expressed in terms of an octant. It's convenient to make an octant the unit and have the others as multiples and depth offsets from it.

    quad(d)    = oct(d) + oct(d-1) - d + 3
    half(d)    = 2*quad(d) + 1
    full(d)    = 4*quad(d) + 3
    3corner(d) = quad(d+1) + 2*quad(d) + 2
                = oct(d+1) + 3*oct(d) + 2*oct(d-1) - 3*d + 10
    wedge(d)   = 2*oct(d-1) + 4

In quad(d) the "-d" term adjusts for the stairstep diagonal spine being counted twice by the oct(d)+oct(d-1).

The oct() recurrence corresponds to the sub-block breakdown shown under "One Octant" above.

    oct(pow+rem) = oct(pow)        "base"
                 + oct(rem+1)      "lower"
                 + 2*oct(rem)      "upper" and "extend"
                 - rem + 4         unduplicate diagonal

The stairstep diagonal between the "upper" and "lower" parts is duplicated by those two parts, hence "-(rem-1)" to subtract one copy of it. A further +3 is the points in-between the replications, ie. the "A", "B" and one further toothpick not otherwise counted by the replications.

oct(rem+1) + 2*oct(rem) is the important part of the recurrence. It removes the high bit of depth and spreads rem to an adjacent pair of smaller depths rem+1 and rem. A list of pending depth values can be maintained and compared to a pow=2^k for reduction.

    for each pending depth
      if depth == 2^k or 2^k+1 then oct(pow) or oct(pow+1)
      if depth >= 2^k+2 then reduce by recurrence
    repeat for 2^(k-1)

rem+1,rem are adjacent so successive reductions make a list growing by one further value each time, like

    d
    d+1, d
    d+2, d+1, d
    d+3, d+2, d+1, d

But when the list crosses a 2^k boundary some of these depths are reduced and others unchanged. When that happens the list is no longer successive values, only mostly successive. When accumulating rem+1 and rem it's enough to check whether the current "rem+1" is equal to the "rem" of the previous breakdown and if so then coalesce with that previously entry.

The factor of "2" in 2*oct(rem) is handled by keeping a desired multiplier with each pending depth. oct(rem+1) is the current multiplier unchanged. 2*oct(rem) doubles the current multiplier. If rem+1 coalesces with the previous rem then add to its multiplier. Those additions mean the multipliers are not powers-of-2.

If the pending list is successive integers then them rem+1,rem breakdown and coalescing increases that list by just one value for each 1-bit of depth, keeping the list to at most log2(depth) many entries. But that's not so when the list crosses a 2^k boundary. It then behaves like two lists each growing by one entry per bit. In any case the list doesn't become huge.

N to Depth

The current tree_n_to_depth() does a binary search for depth by calling tree_depth_to_n() on a successively narrower range. Is there a better approach?

Some intermediate values in the depth-to-N might be re-used by such repeated calls, but it's not clear how many would be re-used and how many would be needed only once. The current code doesn't retain any such intermediates, so large N can be handled without using a lot of memory.

OEIS ^

This cellular automaton is in Sloane's Online Encyclopedia of Integer Sequences as follows, and images by Omar Pol.

http://oeis.org/A139250 (etc)

    parts=4
      A139250   total cells to given depth
      A139251    added cells at given depth
      A139253   total cells which are primes

      A147614   grid points covered at given depth
                 (including toothpick endpoints)

      A139252   line segments at given depth,
                 coalescing touching ends horiz or vert
      A139560   added segments, net of any new joins

      A162795   total cells parallel to initial (at X==Y mod 2)
      A162793    added parallel to initial
      A162796   total cells opposite to initial (at X!=Y mod 2)
      A162794    added opposite to initial
      A162797   difference total cells parallel - opposite

      http://www.polprimos.com/imagenespub/poltp4d4.jpg
      http://www.polprimos.com/imagenespub/poltp283.jpg

    parts=3
      A153006   total cells to given depth
      A152980    added cells at given depth
      A153009   total cells values which are primes

      A153007   difference depth*(depth+1)/2 - total cells,
                 which is 0 at depth=2^k-1
      A153001   added cells as "infinite row" beginning at depth=2^k

      http://www.polprimos.com/imagenespub/poltp028.jpg

    parts=2
      A152998   total cells to given depth
      A152968    added cells at given depth
      A152999   total cells values which are primes

    parts=1
      A153000   total cells to given depth
      A152978    added cells at given depth
      A153002   total cells values which are primes
      A168002   total cells mod 2, equals A079559 which is 0 or 1
                 according to n representable as sum of 2^k-1

      http://www.polprimos.com/imagenespub/poltp016.jpg

    parts=wedge
      A160406   total cells to given depth
      A160407    added cells at given depth

      http://www.polprimos.com/imagenespub/poltp406.jpg

    parts=two_horiz
      A160158   total cells to given depth
      A160159    added cells at given depth

Further sequences A153003, A153004, A153005 are another toothpick form clipped to 3 quadrants. They're not the same as the parts=3 corner pattern here. A153003 would have its X=1,Y=-1 cell as a 3rd child of X=0,Y=1. Allowing the X=0,Y=0 and X=0,Y=-1 cells to be included would be a joined-up pattern, but then the depth totals would be 2 bigger than those OEIS entries.

SEE ALSO ^

Math::PlanePath, Math::PlanePath::ToothpickReplicate, Math::PlanePath::LCornerTree, 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/>.

syntax highlighting: