Provided by: libmath-planepath-perl_125-1_all bug

NAME

       Math::PlanePath::DiagonalRationals -- rationals X/Y by diagonals

SYNOPSIS

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

DESCRIPTION

       This path enumerates positive rationals X/Y with no common factor, going in diagonal order
       from Y down to X.

           17  |    96...
           16  |    80
           15  |    72 81
           14  |    64    82
           13  |    58 65 73 83 97
           12  |    46          84
           11  |    42 47 59 66 74 85 98
           10  |    32    48          86
            9  |    28 33    49 60    75 87
            8  |    22    34    50    67    88
            7  |    18 23 29 35 43 51    68 76 89 99
            6  |    12          36    52          90
            5  |    10 13 19 24    37 44 53 61    77 91
            4  |     6    14    25    38    54    69    92
            3  |     4  7    15 20    30 39    55 62    78 93
            2  |     2     8    16    26    40    56    70    94
            1  |     1  3  5  9 11 17 21 27 31 41 45 57 63 71 79 95
           Y=0 |
               +---------------------------------------------------
                X=0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16

       The order is the same as the "Diagonals" path, but only those X,Y with no common factor
       are numbered.

           1/1,                      N = 1
           1/2, 1/2,                 N = 2 .. 3
           1/3, 1/3,                 N = 4 .. 5
           1/4, 2/3, 3/2, 4/1,       N = 6 .. 9
           1/5, 5/1,                 N = 10 .. 11

       N=1,2,4,6,10,etc at the start of each diagonal (in the column at X=1) is the cumulative
       totient,

           totient(i) = count numbers having no common factor with i

                                    i=K
           cumulative_totient(K) =  sum   totient(i)
                                    i=1

   Direction Up
       Option "direction => 'up'" reverses the order within each diagonal to count upward from
       the X axis.

           direction => "up"

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

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

           n_start => 0

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

   Coprime Columns
       The diagonals are the same as the columns in "CoprimeColumns".  For example the diagonal
       N=18 to N=21 from X=0,Y=8 down to X=8,Y=0 is the same as the "CoprimeColumns" vertical at
       X=8.  In general the correspondence is

          Xdiag = Ycol
          Ydiag = Xcol - Ycol

          Xcol = Xdiag + Ydiag
          Ycol = Xdiag

       "CoprimeColumns" has an extra N=0 at X=1,Y=1 which is not present in "DiagonalRationals".
       (It would be Xdiag=1,Ydiag=0 which is 1/0.)

       The points numbered or skipped in a column up to X=Y is the same as the points numbered or
       skipped on a diagonal, simply because X,Y no common factor is the same as Y,X+Y no common
       factor.

       Taking the "CoprimeColumns" as enumerating fractions F = Ycol/Xcol with 0 < F < 1 the
       corresponding diagonal rational 0 < R < infinity is

                  1         F
           R = -------  =  ---
               1/F - 1     1-F

                  1         R
           F = -------  =  ---
               1/R + 1     1+R

       which is a one-to-one mapping between the fractions F < 1 and all rationals.

FUNCTIONS

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

       "$path = Math::PlanePath::DiagonalRationals->new ()"
       "$path = Math::PlanePath::DiagonalRationals->new (direction => $str, n_start => $n)"
           Create and return a new path object.  "direction" (a string) can be

               "down"     (the default)
               "up"

       "($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 < 1" then the return is an empty list.

BUGS

       The current implementation is fairly slack and is slow on medium to large N.  A table of
       cumulative totients is built and retained for the diagonal d=X+Y.

OEIS

       This enumeration of rationals is in Sloane's Online Encyclopedia of Integer Sequences in
       the following forms

           <http://oeis.org/A020652> (etc)

           direction=down, n_start=1  (the defaults)
             A020652   X, numerator
             A020653   Y, denominator
             A038567   X+Y sum, starting from X=1,Y=1
             A054431   by diagonals 1=coprime, 0=not
                         (excluding X=0 row and Y=0 column)

             A054430   permutation N at Y/X
                         reverse runs of totient(k) many integers

             A054424   permutation DiagonalRationals -> RationalsTree SB
             A054425     padded with 0s at non-coprimes
             A054426     inverse SB -> DiagonalRationals
             A060837   permutation DiagonalRationals -> FactorRationals

           direction=down, n_start=0
             A157806   abs(X-Y) difference

       direction=up swaps X,Y.

SEE ALSO

       Math::PlanePath, Math::PlanePath::CoprimeColumns, Math::PlanePath::RationalsTree,
       Math::PlanePath::PythagoreanTree

HOME PAGE

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

LICENSE

       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde

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