/ 
Math-PlanePath-92
River stage one • 3 direct dependents • 4 total dependents
/ Math::PlanePath::DiagonalRationals

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.

The N=1,2,4,6,10,etc in the leftmost column (at X=1) is the cumulative totient,

phi(i) = count divisors of i

                i=K
phicumul(K) =  sum   phi(i)
                i=1

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

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

OEIS

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

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

A020652   numerators, X
A020653   denominators, Y
A157806   difference, abs(X-Y)
A054431   by diagonals 1=coprime, 0=not
            (excluding X=0 row and Y=0 column)

A061579   permutation N at transpose Y/X
            reverse runs of phi(k) integers

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

FUNCTIONS

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

$path = Math::PlanePath::DiagonalRationals->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 < 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 X+Y sum used.

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