The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Math-PlanePath-84
River stage one • 3 direct dependents • 4 total dependents
2 ++
/ Math::PlanePath::PowerArray

NAME

Math::PlanePath::PowerArray -- array by powers

SYNOPSIS

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

DESCRIPTION

This is a split of N into an odd part and power of 2,

     14  |   29    58   116   232   464   928  1856  3712  7424 14848
     13  |   27    54   108   216   432   864  1728  3456  6912 13824
     12  |   25    50   100   200   400   800  1600  3200  6400 12800
     11  |   23    46    92   184   368   736  1472  2944  5888 11776
     10  |   21    42    84   168   336   672  1344  2688  5376 10752
      9  |   19    38    76   152   304   608  1216  2432  4864  9728
      8  |   17    34    68   136   272   544  1088  2176  4352  8704
      7  |   15    30    60   120   240   480   960  1920  3840  7680
      6  |   13    26    52   104   208   416   832  1664  3328  6656
      5  |   11    22    44    88   176   352   704  1408  2816  5632
      4  |    9    18    36    72   144   288   576  1152  2304  4608
      3  |    7    14    28    56   112   224   448   896  1792  3584
      2  |    5    10    20    40    80   160   320   640  1280  2560
      1  |    3     6    12    24    48    96   192   384   768  1536
    Y=0  |    1     2     4     8    16    32    64   128   256   512
         +-----------------------------------------------------------
            X=0     1     2     3     4     5     6     7     8     9

For N=odd*2^k the coordinates are X=k, Y=(odd-1)/2. The X coordinate is how many factors of 2 can be divided out. The Y coordinate counts odd integers 1,3,5,7,etc as 0,1,2,3,etc.

Radix

The radix parameter can do the same dividing out in a higher base. For example radix 3 divides out factors of 3,

     radix => 3

      9  |   14    42   126   378  1134  3402 10206 30618
      8  |   13    39   117   351  1053  3159  9477 28431
      7  |   11    33    99   297   891  2673  8019 24057
      6  |   10    30    90   270   810  2430  7290 21870
      5  |    8    24    72   216   648  1944  5832 17496
      4  |    7    21    63   189   567  1701  5103 15309
      3  |    5    15    45   135   405  1215  3645 10935
      2  |    4    12    36   108   324   972  2916  8748
      1  |    2     6    18    54   162   486  1458  4374
    Y=0  |    1     3     9    27    81   243   729  2187
         +------------------------------------------------
            X=0     1     2     3     4     5     6     7

N=1,3,9,27,etc along the X axis is the powers of 3. N=1,2,4,5,7,etc on the Y axis is the integers N=1mod3 and N=2mod3, ie. those not a multiple of 3. Notice when Y=1or2 mod 4 the N values in that row are all even, and when Y=0or3 mod 4 the N values are all odd.

FUNCTIONS

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

$path = Math::PlanePath::PowerArray->new ()

Create and return a new path object.

($x,$y) = $path->n_to_xy ($n)

Return the X,Y coordinates of point number $n on the path. Points begin at 1 and if $n < 0 then the return is an empty list.

$n = $path->xy_to_n ($x,$y)

Return the N point number at coordinates $x,$y. If $x<0 or $y<0 then there's no N and the return is undef.

N values grow rapidly with $x. Pass in a number type such as Math::BigInt to preserve precision.

($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)

The returned range is exact, meaning $n_lo and $n_hi are the smallest and biggest in the rectangle.

FORMULAS

Rectangle to N Range

Within each row increasing X is increasing N, and in each column increasing Y is increasing N. So in a rectangle the lower left corner is the minimum N and the upper right is the maximum N.

OEIS

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

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

    radix=2
      A007814    X coordinate, count low 0 bits of N
      A006519    2^X, the power of 2 divided out

      A025480    Y coordinate of N-1, ie. seq starts from N=0
      A003602    Y+1 coordinate, k for which N=(2k-1)*2^m
      A153733    2*Y coordinate of N-1, strip low 1 bits
      A000265    2*Y+1 coordinate, strip low 0 bits

      A094267    dX, change in X coordinate
      A108715    dY, change in Y coordinate

      A000079    N on X axis, powers 2^X
      A005408    N on Y axis, the odd numbers
      A057716    N not on X axis, the non-powers-of-2

      A118417    N on X=Y+1 diagonal (just below X=Y diagonal)

      A054582    N by diagonals upwards
      A075300    N-1 by diagonals upwards
      A135764    N by diagonals downwards

    radix=3
      A000244    N on X axis, powers 3^X
      A135765    odd N by diagonals, delete the Y=1,2mod4 even rows

    radix=4
      A000302    N on X axis, powers 4^X

    radix=5
      A000351    N on X axis, powers 5^X

    radix=10
      A011557    N on X axis, powers 10^X

SEE ALSO

Math::PlanePath, Math::PlanePath::WythoffArray, Math::PlanePath::ZOrderCurve

HOME PAGE

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

LICENSE

Copyright 2012 Kevin Ryde

This file is part of Math-PlanePath.

Math-PlanePath 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 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. If not, see <http://www.gnu.org/licenses/>.