1Math::PlanePath::DiagonUasleRratCioonntarlisb(u3t)ed PerMlatDho:c:uPmleannteaPtaitohn::DiagonalRationals(3)
2
6 Math::PlanePath::DiagonalRationals -- rationals X/Y by diagonals
7
9 use Math::PlanePath::DiagonalRationals;
10 my $path = Math::PlanePath::DiagonalRationals->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This path enumerates positive rationals X/Y with no common factor,
15 going in diagonal order from Y down to X.
16 17 | 96...
18 16 | 80
19 15 | 72 81
20 14 | 64 82
21 13 | 58 65 73 83 97
22 12 | 46 84
23 11 | 42 47 59 66 74 85 98
24 10 | 32 48 86
25 9 | 28 33 49 60 75 87
26 8 | 22 34 50 67 88
27 7 | 18 23 29 35 43 51 68 76 89 99
28 6 | 12 36 52 90
29 5 | 10 13 19 24 37 44 53 61 77 91
30 4 | 6 14 25 38 54 69 92
31 3 | 4 7 15 20 30 39 55 62 78 93
32 2 | 2 8 16 26 40 56 70 94
33 1 | 1 3 5 9 11 17 21 27 31 41 45 57 63 71 79 95
34 Y=0 |
35 +---------------------------------------------------
36 X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
37 The order is the same as the "Diagonals" path, but only those X,Y with
39 no common factor are numbered.
40 1/1, N = 1
42 1/2, 1/2, N = 2 .. 3
43 1/3, 1/3, N = 4 .. 5
44 1/4, 2/3, 3/2, 4/1, N = 6 .. 9
45 1/5, 5/1, N = 10 .. 11
46 N=1,2,4,6,10,etc at the start of each diagonal (in the column at X=1)
48 is the cumulative totient,
49 totient(i) = count numbers having no common factor with i
51 i=K
53 cumulative_totient(K) = sum totient(i)
54 i=1
55 Direction Up
57 Option "direction => 'up'" reverses the order within each diagonal to
58 count upward from the X axis.
59 direction => "up"
61 8 | 27
63 7 | 21 26
64 6 | 17
65 5 | 11 16 20 25
66 4 | 9 15 24
67 3 | 5 8 14 19
68 2 | 3 7 13 23
69 1 | 1 2 4 6 10 12 18 22
70 Y=0|
71 +---------------------------
72 X=0 1 2 3 4 5 6 7 8
73 N Start
75 The default is to number points starting N=1 as shown above. An
76 optional "n_start" can give a different start with the same shape, For
77 example to start at 0,
78 n_start => 0
80 8 | 21
82 7 | 17 22
83 6 | 11
84 5 | 9 12 18 23
85 4 | 5 13 24
86 3 | 3 6 14 19
87 2 | 1 7 15 25
88 1 | 0 2 4 8 10 16 20 26
89 Y=0|
90 +---------------------------
91 X=0 1 2 3 4 5 6 7 8
92 Coprime Columns
94 The diagonals are the same as the columns in "CoprimeColumns". For
95 example the diagonal N=18 to N=21 from X=0,Y=8 down to X=8,Y=0 is the
96 same as the "CoprimeColumns" vertical at X=8. In general the
97 correspondence is
98 Xdiag = Ycol
100 Ydiag = Xcol - Ycol
101 Xcol = Xdiag + Ydiag
103 Ycol = Xdiag
104 "CoprimeColumns" has an extra N=0 at X=1,Y=1 which is not present in
106 "DiagonalRationals". (It would be Xdiag=1,Ydiag=0 which is 1/0.)
107 The points numbered or skipped in a column up to X=Y is the same as the
109 points numbered or skipped on a diagonal, simply because X,Y no common
110 factor is the same as Y,X+Y no common factor.
111 Taking the "CoprimeColumns" as enumerating fractions F = Ycol/Xcol with
113 0 < F < 1 the corresponding diagonal rational 0 < R < infinity is
114 1 F
116 R = ------- = ---
117 1/F - 1 1-F
118 1 R
120 F = ------- = ---
121 1/R + 1 1+R
122 which is a one-to-one mapping between the fractions F < 1 and all
124 rationals.
125
127 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
128 classes.
129 "$path = Math::PlanePath::DiagonalRationals->new ()"
131 "$path = Math::PlanePath::DiagonalRationals->new (direction => $str,
132 n_start => $n)"
133 Create and return a new path object. "direction" (a string) can be
134 "down" (the default)
136 "up"
137 "($x,$y) = $path->n_to_xy ($n)"
139 Return the X,Y coordinates of point number $n on the path. Points
140 begin at 1 and if "$n < 1" then the return is an empty list.
141
143 The current implementation is fairly slack and is slow on medium to
144 large N. A table of cumulative totients is built and retained for the
145 diagonal d=X+Y.
146
148 This enumeration of rationals is in Sloane's Online Encyclopedia of
149 Integer Sequences in the following forms
150 <http://oeis.org/A020652> (etc)
152 direction=down, n_start=1 (the defaults)
154 A020652 X, numerator
155 A020653 Y, denominator
156 A038567 X+Y sum, starting from X=1,Y=1
157 A054431 by diagonals 1=coprime, 0=not
158 (excluding X=0 row and Y=0 column)
159 A054430 permutation N at Y/X
161 reverse runs of totient(k) many integers
162 A054424 permutation DiagonalRationals -> RationalsTree SB
164 A054425 padded with 0s at non-coprimes
165 A054426 inverse SB -> DiagonalRationals
166 A060837 permutation DiagonalRationals -> FactorRationals
167 direction=down, n_start=0
169 A157806 abs(X-Y) difference
170 direction=up swaps X,Y.
172
174 Math::PlanePath, Math::PlanePath::CoprimeColumns,
175 Math::PlanePath::RationalsTree, Math::PlanePath::PythagoreanTree
176
178 <http://user42.tuxfamily.org/math-planepath/index.html>
179
181 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
182 Kevin Ryde
183 Math-PlanePath is free software; you can redistribute it and/or modify
185 it under the terms of the GNU General Public License as published by
186 the Free Software Foundation; either version 3, or (at your option) any
187 later version.
188 Math-PlanePath is distributed in the hope that it will be useful, but
190 WITHOUT ANY WARRANTY; without even the implied warranty of
191 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
192 General Public License for more details.
193 You should have received a copy of the GNU General Public License along
195 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
196perl v5.36.0 2022-07-M2a2th::PlanePath::DiagonalRationals(3)