1Math::PlanePath::FactorURsaetrioCnoanltsr(i3b)uted PerlMDaotchu:m:ePnltaanteiPoanth::FactorRationals(3)
2
3
4

NAME

6       Math::PlanePath::FactorRationals -- rationals by prime powers
7

SYNOPSIS

9        use Math::PlanePath::FactorRationals;
10        my $path = Math::PlanePath::FactorRationals->new;
11        my ($x, $y) = $path->n_to_xy (123);
12

DESCRIPTION

14       This path enumerates rationals X/Y with no common factor, based on the
15       prime powers in numerator and denominator, as per
16
17           Kevin McCrimmon, "Enumeration of the Positive Rationals", American
18           Math. Monthly, Nov 1960, page 868.
19           <http://www.jstor.org/stable/2309448>
20
21           Gerald Freilich, "A Denumerability Formula for the Rationals",
22           American Math. Monthly, Nov 1965, pages 1013-1014.
23           <http://www.jstor.org/stable/2313350>
24
25           Yoram Sagher, "Counting the rationals", American Math. Monthly, Nov
26           1989, page 823.  <http://www.jstor.org/stable/2324846>
27
28       The result is
29
30           15  |      15   60       240            735  960           1815
31           14  |      14       126       350                1134      1694
32           13  |      13   52  117  208  325  468  637  832 1053 1300 1573
33           12  |      24                 600      1176                2904
34           11  |      11   44   99  176  275  396  539  704  891 1100
35           10  |      10        90                 490       810      1210
36            9  |      27  108       432  675      1323 1728      2700 3267
37            8  |      32       288       800      1568      2592      3872
38            7  |       7   28   63  112  175  252       448  567  700  847
39            6  |       6                 150       294                 726
40            5  |       5   20   45   80       180  245  320  405       605
41            4  |       8        72       200       392       648       968
42            3  |       3   12        48   75       147  192       300  363
43            2  |       2        18        50        98       162       242
44            1  |       1    4    9   16   25   36   49   64   81  100  121
45           Y=0 |
46                ----------------------------------------------------------
47                 X=0   1    2    3    4    5    6    7    8    9   10   11
48
49       A given fraction X/Y with no common factor has a prime factorization
50
51           X/Y = p1^e1 * p2^e2 * ...
52
53       The exponents e[i] are positive, negative or zero, being positive when
54       the prime is in the numerator or negative when in the denominator.
55       Those exponents are represented in an integer N by mapping the
56       exponents to non-negative,
57
58           N = p1^f(e1) * p2^f(e2) * ...
59
60           f(e) = 2*e      if e >= 0
61                = 1-2*e    if e < 0
62
63           f(e)      e
64           ---      ---
65            0        0
66            1       -1
67            2        1
68            3       -2
69            4        2
70
71       For example
72
73           X/Y = 125/7 = 5^3 * 7^(-1)
74           encoded as N = 5^(2*3) * 7^(1-2*(-1)) = 5^6 * 7^1 = 5359375
75
76           N=3   ->  3^-1 = 1/3
77           N=9   ->  3^1  = 3/1
78           N=27  ->  3^-2 = 1/9
79           N=81  ->  3^2  = 9/1
80
81       The effect is to distinguish prime factors of the numerator or
82       denominator by odd or even exponents of those primes in N.  Since X and
83       Y have no common factor a given prime appears in one and not the other.
84       The oddness or evenness of the p^f() exponent in N can then encode
85       which of the two X or Y it came from.
86
87       The exponent f(e) in N has term 2*e in both cases, but the exponents
88       from Y are reduced by 1.  This can be expressed in the following form.
89       Going from X,Y to N doesn't need to factorize X, only Y.
90
91                    X^2 * Y^2
92           N = --------------------
93               distinct primes in Y
94
95       N=1,2,3,8,5,6,etc in the column X=1 is integers with odd powers of
96       prime factors.  These are the fractions 1/Y so the exponents of the
97       primes are all negative and thus all exponents in N are odd.
98
99       N=1,4,9,16,etc in row Y=1 are the perfect squares.  That row is the
100       integers X/1 so the exponents are all positive and thus in N become
101       2*e, giving simply N=X^2.
102
103   Odd/Even
104       Option "factor_coding => "odd/even"" changes the f() mapping to
105       numerator exponents as odd numbers and denominator exponents as even.
106
107           f(e) = 2*e-1    if e > 0
108                = -2*e     if e <= 0
109
110       The effect is simply to transpose X<->Y.
111
112       "odd/even" is the form given by Kevin McCrimmon and Gerald Freilich.
113       The default "even/odd" is the form given by Yoram Sagher.
114
115   Negabinary
116       Option "factor_coding => "negabinary"" changes the f() mapping to
117       negabinary as suggested in
118
119           David M. Bradley, "Counting the Positive Rationals: A Brief
120           Survey", <http://arxiv.org/abs/math/0509025>
121
122       This coding is not as compact as odd/even and tends to make bigger N
123       values,
124
125           13  |    2197   4394   6591 140608  10985  13182  15379 281216
126           12  |     108                         540           756
127           11  |    1331   2662   3993  85184   6655   7986   9317 170368
128           10  |    1000          3000                        7000
129            9  |       9     18           576     45            63   1152
130            8  |    8192         24576         40960         57344
131            7  |     343    686   1029  21952   1715   2058         43904
132            6  |     216                        1080          1512
133            5  |     125    250    375   8000           750    875  16000
134            4  |       4            12            20            28
135            3  |      27     54          1728    135           189   3456
136            2  |       8            24            40            56
137            1  |       1      2      3     64      5      6      7    128
138           Y=0 |
139                ----------------------------------------------------------
140                 X=0   1      2      3      4      5      6      7      8
141
142   Reversing Binary
143       Option "factor_coding => "revbinary"" changes the f() mapping to
144       "reversing binary" where a given integer is represented as a sum of
145       powers 2^k with alternating signs
146
147           e = 2^k1 - 2^k2 + 2^k3 - ...           0 <= k1 < k2 < k3
148
149           f(e)      e
150           ---      ---
151            0        0
152            1        1
153            2        2
154            3       -1
155            4        4
156            5       -3
157            6       -2
158            7        3
159
160       This representation is per Knuth volume 2 section 4.1 exercise 27.  The
161       exercise there is to show all integers can be represented this way.
162
163            9  |     729  1458        2916  3645        5103 93312        7290
164            8  |      32          96         160         224         288
165            7  |     343   686  1029  1372  1715  2058       43904  3087  3430
166            6  |     216                    1080        1512
167            5  |     125   250   375   500         750   875 16000  1125
168            4  |      64         192         320         448         576
169            3  |      27    54         108   135         189  3456         270
170            2  |       8          24          40          56          72
171            1  |       1     2     3     4     5     6     7   128     9    10
172           Y=0 |
173                ---------------------------------------------------------------
174                 X=0   1     2     3     4     5     6     7     8     9    10
175
176       The X axis begins with the integers 1 to 7 because f(1)=1 and f(2)=2 so
177       N=X until X has a prime p^3 or higher power.  The first such is X=8=2^3
178       which is f(7)=3 so N=2^7=128.
179

FUNCTIONS

181       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
182       classes.
183
184       "$path = Math::PlanePath::FactorRationals->new ()"
185       "$path = Math::PlanePath::FactorRationals->new (factor_coding => $str)"
186           Create and return a new path object.  "factor_coding" can be
187
188               "even/odd"    (the default)
189               "odd/even"
190               "negabinary"
191               "revbinary"
192
193       "($x,$y) = $path->n_to_xy ($n)"
194           Return X,Y coordinates of point $n on the path.  If there's no
195           point $n then the return is an empty list.
196
197           This depends on factorizing $n and in the current code there's a
198           hard limit on the amount of factorizing attempted.  If $n is too
199           big then the return is an empty list.
200
201       "$n = $path->xy_to_n ($x,$y)"
202           Return the N point number for coordinates "$x,$y".  If there's
203           nothing at "$x,$y", such as when they have a common factor, then
204           return "undef".
205
206           This depends on factorizing $y, or factorizing both $x and $y for
207           negabinary or revbinary.  In the current code there's a hard limit
208           on the amount of factorizing attempted.  If the coordinates are too
209           big then the return is "undef".
210
211       The current factorizing limits handle anything up to 2^32, and above
212       that numbers comprised of small factors.  But big numbers with big
213       factors are not handled.  Is this a good idea?  For large inputs
214       there's no merit in disappearing into a nearly-infinite loop.  Perhaps
215       the limits could be configurable and/or some advanced factoring modules
216       attempted for a while if/when available.
217

OEIS

219       This enumeration of the rationals is in Sloane's Online Encyclopedia of
220       Integer Sequences in the following forms
221
222           <http://oeis.org/A071974> (etc)
223
224           A071974   X coordinate, numerators
225           A071975   Y coordinate, denominators
226           A019554   X*Y product
227           A102631   N in column X=1, n^2/squarefreekernel(n)
228           A072345   X and Y at N=2^k, being alternately 1 and 2^k
229
230           A011262   permutation N at transpose Y/X (exponents mangle odd<->even)
231
232           A060837   permutation DiagonalRationals -> FactorRationals
233           A071970   permutation RationalsTree CW -> FactorRationals
234
235       The last A071970 is rationals taken in order of the Stern diatomic
236       sequence stern[i]/stern[i+1] which is the Calkin-Wilf tree rows
237       ("Calkin-Wilf Tree" in Math::PlanePath::RationalsTree).
238
239       The negabinary representation is
240
241           A053985   index -> signed
242           A005351   signed positives -> index
243           A039724   signed positives -> index, in binary
244           A005352   signed negatives -> index
245
246       The reversing binary representation is
247
248           A065620   index -> signed
249           A065621   signed positives -> index
250           A048724   signed negatives -> index
251

SEE ALSO

253       Math::PlanePath, Math::PlanePath::GcdRationals,
254       Math::PlanePath::RationalsTree, Math::PlanePath::CoprimeColumns
255
256   Other Ways to Do It
257       Niven gives another prime factor based construction but encoding N by
258       runs of 1-bits,
259
260           Ivan Niven, "Note on a paper by L. S. Johnston", American Math.
261           Monthly, volume 55, number 6, June-July 1948, page 358.
262           <http://www.jstor.org/stable/2304962>
263
264       N is written in binary each 0-bit is considered a separator.  The
265       number of 1-bits between each
266
267           N = 11 0 0 111 0 11  binary
268                  | |     |
269                2  0   3    2   f(e) = run lengths of 1-bits
270               -1  0  +2   -1   e exponent by "odd/even" style
271
272           X/Y = 2^(-1) * 3^(+2) * 5^0 * 7^(-1)
273
274       Kevin McCrimmon's note begins with a further possible encoding for N
275       where the prime powers from numerator are spread out to primes p[2i+1]
276       and with 0 powers sending a p[2i] power to the denominator.  In this
277       form the primes from X and Y spread out to different primes rather than
278       different exponents.
279

HOME PAGE

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

LICENSE

284       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
285
286       This file is part of Math-PlanePath.
287
288       Math-PlanePath is free software; you can redistribute it and/or modify
289       it under the terms of the GNU General Public License as published by
290       the Free Software Foundation; either version 3, or (at your option) any
291       later version.
292
293       Math-PlanePath is distributed in the hope that it will be useful, but
294       WITHOUT ANY WARRANTY; without even the implied warranty of
295       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
296       General Public License for more details.
297
298       You should have received a copy of the GNU General Public License along
299       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
300
301
302
303perl v5.30.1                      2020-01-30Math::PlanePath::FactorRationals(3)
Impressum