1Math::PlanePath::FactorURsaetrioCnoanltsr(i3b)uted PerlMDaotchu:m:ePnltaanteiPoanth::FactorRationals(3)
2
6 Math::PlanePath::FactorRationals -- rationals by prime powers
7
9 use Math::PlanePath::FactorRationals;
10 my $path = Math::PlanePath::FactorRationals->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This path enumerates rationals X/Y with no common factor, based on the
15 prime powers in numerator and denominator, as per
16 Kevin McCrimmon, "Enumeration of the Positive Rationals", American
18 Math. Monthly, Nov 1960, page 868.
19 <http://www.jstor.org/stable/2309448>
20 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 Yoram Sagher, "Counting the rationals", American Math. Monthly, Nov
26 1989, page 823. <http://www.jstor.org/stable/2324846>
27 The result is
29 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 A given fraction X/Y with no common factor has a prime factorization
50 X/Y = p1^e1 * p2^e2 * ...
52 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 N = p1^f(e1) * p2^f(e2) * ...
59 f(e) = 2*e if e >= 0
61 = 1-2*e if e < 0
62 f(e) e
64 --- ---
65 0 0
66 1 -1
67 2 1
68 3 -2
69 4 2
70 For example
72 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 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 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 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 X^2 * Y^2
92 N = --------------------
93 distinct primes in Y
94 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 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 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 f(e) = 2*e-1 if e > 0
108 = -2*e if e <= 0
109 The effect is simply to transpose X<->Y.
111 "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 Negabinary
116 Option "factor_coding => "negabinary"" changes the f() mapping to
117 negabinary as suggested in
118 David M. Bradley, "Counting the Positive Rationals: A Brief
120 Survey", <http://arxiv.org/abs/math/0509025>
121 This coding is not as compact as odd/even and tends to make bigger N
123 values,
124 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 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 e = 2^k1 - 2^k2 + 2^k3 - ... 0 <= k1 < k2 < k3
148 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 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 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 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
181 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
182 classes.
183 "$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 "even/odd" (the default)
189 "odd/even"
190 "negabinary"
191 "revbinary"
192 "($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 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 "$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 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 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
219 This enumeration of the rationals is in Sloane's Online Encyclopedia of
220 Integer Sequences in the following forms
221 <http://oeis.org/A071974> (etc)
223 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 A011262 permutation N at transpose Y/X (exponents mangle odd<->even)
231 A060837 permutation DiagonalRationals -> FactorRationals
233 A071970 permutation RationalsTree CW -> FactorRationals
234 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 The negabinary representation is
240 A053985 index -> signed
242 A005351 signed positives -> index
243 A039724 signed positives -> index, in binary
244 A005352 signed negatives -> index
245 The reversing binary representation is
247 A065620 index -> signed
249 A065621 signed positives -> index
250 A048724 signed negatives -> index
251
253 Math::PlanePath, Math::PlanePath::GcdRationals,
254 Math::PlanePath::RationalsTree, Math::PlanePath::CoprimeColumns
255 Other Ways to Do It
257 Niven gives another prime factor based construction but encoding N by
258 runs of 1-bits,
259 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 N is written in binary each 0-bit is considered a separator. The
265 number of 1-bits between each
266 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 X/Y = 2^(-1) * 3^(+2) * 5^0 * 7^(-1)
273 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
281 <http://user42.tuxfamily.org/math-planepath/index.html>
282
284 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
285 Kevin Ryde
286 This file is part of Math-PlanePath.
288 Math-PlanePath is free software; you can redistribute it and/or modify
290 it under the terms of the GNU General Public License as published by
291 the Free Software Foundation; either version 3, or (at your option) any
292 later version.
293 Math-PlanePath is distributed in the hope that it will be useful, but
295 WITHOUT ANY WARRANTY; without even the implied warranty of
296 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
297 General Public License for more details.
298 You should have received a copy of the GNU General Public License along
300 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
301perl v5.34.0 2022-01-21Math::PlanePath::FactorRationals(3)