++ed by:
Kevin Ryde
and 1 contributors

# 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

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