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

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

Dependencies

Annotate this POD

Website

View/Report Bugs
Module Version: 14   Source  

NAME ^

Math::PlanePath::ToothpickReplicate -- toothpick pattern by replication

SYNOPSIS ^

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

DESCRIPTION ^

This is the "toothpick" pattern of the ToothpickTree path numbered as a self-similar replicating pattern.

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

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

One Quadrant

Option parts => 1 selects a single quadrant of replications.

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

Replication

The points visited are the same as Math::PlanePath::ToothpickTree, but in a self-similar order. The pattern within each quarter repeats at 2^level size blocks.

    +------------+------------+
    |            |            |
    |  block 3       block 2  |
    |   mirror        same    |
    |                         |
    |          --B--          |
    |            |            |
    +----------  A         ---+
    |            |            |
    |  block 0       block 1  |
    |            |   rot +90  |
    |            |            |
    |            |            |
    +------------+------------+

In the parts=1 above ("One Quadrant"),

    N=1 to N=10     "0" block
    N=11            "A" middle point
    N=12            "B" middle point
    N=13 to N=22    "1" block, rotated +90 degrees
    N=23 to N=32    "2" block, same layout as the "0" block
    N=33 to N=42    "3" block, mirror image of "0" block

The very first points N=1 and N=2 are effectively the "A" and "B" middle toothpicks with no points at all for the 0,1,2,3 sub-blocks.

The full parts=4 form (the default) is four quarters, each advancing by a replication level each time.

The initial N=0,1,2 make the centre, and then each quadrant is extended in turn by blocks.

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

Block 0 is the existing part. Then toothpick A and B are counted, followed by replications of block 0 in blocks 1,2,3. For example in the first quadrant

    N=11      toothpick "A"
    N=12      toothpick "B"
    N=13,14   block 1 \
    N=15,16   block 2 |  replicating block 0 N=3,N=4
    N=17,18   block 3 /

Each such replication doubles the size in a quadrant, so the "A" toothpick is on a power-of-2 X=2^k,Y=2^k. For example N=11 at X=2,Y=2 and N=43 at X=4,Y=4.

Half Plane

Option parts => 2 confines the pattern 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.

     ...                             ...          5
      |                               |
     53--18--  --20--  --12--  --10--21           4
      |   |       |       |       |   |
     ... 17--14--19      11---6---9  ...          3
          |   |               |   |
             13---4--  ---2---5                   2
          |   |   |       |   |   |
         16--15-  3---0---1 --7---8               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, but continued on indefinitely confined to the upper and right three quadrants.

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

N=1,4,5,6,7,16,etc above the X axis have an odd number of bits when written in binary. For example N=6 is binary "110" which is 3 digits. Conversely N=0,2,3,8,etc below the X axis have an even number of digits. For example N=8 is "1000" which is 4 digits.

   odd bit       odd bit
   length     |  length     
              |
     "11"     |  "10"            high two bits of N,
              |                  at odd bit position
    ----------+----------
              |
              |  "01" 
              |
              |  even bit length

This occurs because each quadrant contains (4^k-1)*2/3 many points on each doubling. Three of them plus A and B make 3*(4^k-1)*2/3+2 = 2*4^k at each doubling, so with the origin as N=0 each replication level starts

    Nlevel_start = 2*4^k
    Nlast_below  = 2*4^k + 3*(4^k-1)*2/3+2 - 1
                 = 2*4^k + 2*4^k-1

For example k=1 has Nlevel_start = 2*4^1 = 8 and runs through to Nlast_below = 2*4^1 + 2*4^1-1 = 15. In binary this is "1000" through "1111" which are all length 4. The first quadrant then runs 32 to 47 which is binary "10000" to 101111", and the second quadrant 48 to 63 "110000" to "111111".

FUNCTIONS ^

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

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

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

OEIS ^

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include

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

    parts=3
      A053738   N of points with Y>0, being odd bit length
                 also N of parts=3 when taking X,Y points by parts=2 order
      A053754   N of points with Y<=0, being even bit length

SEE ALSO ^

Math::PlanePath, Math::PlanePath::ToothpickTree, Math::PlanePath::LCornerReplicate, 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: