| Math::PlanePath::FactorRationals(3pm) | User Contributed Perl Documentation | Math::PlanePath::FactorRationals(3pm) |
NAME¶
Math::PlanePath::FactorRationals -- rationals by prime powersSYNOPSIS¶
use Math::PlanePath::FactorRationals; my $path = Math::PlanePath::FactorRationals->new; my ($x, $y) = $path->n_to_xy (123);
DESCRIPTION¶
This path enumerates rationals X/Y with no common factor, based on the prime powers in numerator and denominator, as perKevin McCrimmon, "Enumeration of the Positive
Rationals", American Math. Monthly, Nov 1960, page 868.
<http://www.jstor.org/stable/2309448>
Gerald Freilich, "A Denumerability Formula for the Rationals",
American Math. Monthly, Nov 1965, pages 1013-1014.
<http://www.jstor.org/stable/2313350>
Yoram Sagher, "Counting the rationals", American Math. Monthly, Nov
1989, page 823. <http://www.jstor.org/stable/2324846>
The result is
15 | 15 60 240 735 960 1815
14 | 14 126 350 1134 1694
13 | 13 52 117 208 325 468 637 832 1053 1300 1573
12 | 24 600 1176 2904
11 | 11 44 99 176 275 396 539 704 891 1100
10 | 10 90 490 810 1210
9 | 27 108 432 675 1323 1728 2700 3267
8 | 32 288 800 1568 2592 3872
7 | 7 28 63 112 175 252 448 567 700 847
6 | 6 150 294 726
5 | 5 20 45 80 180 245 320 405 605
4 | 8 72 200 392 648 968
3 | 3 12 48 75 147 192 300 363
2 | 2 18 50 98 162 242
1 | 1 4 9 16 25 36 49 64 81 100 121
Y=0 |
----------------------------------------------------------
X=0 1 2 3 4 5 6 7 8 9 10 11
A given fraction X/Y with no common factor has a prime factorization
X/Y = p1^e1 * p2^e2 * ...The exponents e[i] are positive, negative or zero, being positive when the prime is in the numerator or negative when in the denominator. Those exponents are represented in an integer N by mapping the exponents to non-negative,
N = p1^f(e1) * p2^f(e2) * ...
f(e) = 2*e if e >= 0
= 1-2*e if e < 0
f(e) e
--- ---
0 0
1 -1
2 1
3 -2
4 2
For example
X/Y = 125/7 = 5^3 * 7^(-1)
encoded as N = 5^(2*3) * 7^(1-2*(-1)) = 5^6 * 7^1 = 5359375
N=3 -> 3^-1 = 1/3
N=9 -> 3^1 = 3/1
N=27 -> 3^-2 = 1/9
N=81 -> 3^2 = 9/1
The effect is to distinguish prime factors of the numerator or denominator by
odd or even exponents of those primes in N. Since X and Y have no common
factor a given prime appears in one and not the other. The oddness or evenness
of the p^f() exponent in N can then encode which of the two X or Y it came
from.
The exponent f(e) in N has term 2*e in both cases, but the exponents from Y are
reduced by 1. This can be expressed in the following form. Going from X,Y to N
doesn't need to factorize X, only Y.
X^2 * Y^2
N = --------------------
distinct primes in Y
N=1,2,3,8,5,6,etc in the column X=1 is integers with odd powers of prime
factors. These are the fractions 1/Y so the exponents of the primes are all
negative and thus all exponents in N are odd.
N=1,4,9,16,etc in row Y=1 are the perfect squares. That row is the integers X/1
so the exponents are all positive and thus in N become 2*e, giving simply
N=X^2.
Odd/Even¶
Option "factor_coding => "odd/even"" changes the f() mapping to numerator exponents as odd numbers and denominator exponents as even. f(e) = 2*e-1 if e > 0
= -2*e if e <= 0
The effect is simply to transpose X<->Y.
"odd/even" is the form given by Kevin McCrimmon and Gerald Freilich.
The default "even/odd" is the form given by Yoram Sagher.
Negabinary¶
Option "factor_coding => "negabinary"" changes the f() mapping to negabinary as suggested inDavid M. Bradley, "Counting the Positive Rationals:
A Brief Survey", <http://arxiv.org/abs/math/0509025>
This coding is not as compact as odd/even and tends to make bigger N values,
13 | 2197 4394 6591 140608 10985 13182 15379 281216
12 | 108 540 756
11 | 1331 2662 3993 85184 6655 7986 9317 170368
10 | 1000 3000 7000
9 | 9 18 576 45 63 1152
8 | 8192 24576 40960 57344
7 | 343 686 1029 21952 1715 2058 43904
6 | 216 1080 1512
5 | 125 250 375 8000 750 875 16000
4 | 4 12 20 28
3 | 27 54 1728 135 189 3456
2 | 8 24 40 56
1 | 1 2 3 64 5 6 7 128
Y=0 |
----------------------------------------------------------
X=0 1 2 3 4 5 6 7 8
Reversing Binary¶
Option "factor_coding => "revbinary"" changes the f() mapping to "reversing binary" where a given integer is represented as a sum of powers 2^k with alternating signs e = 2^k1 - 2^k2 + 2^k3 - ... 0 <= k1 < k2 < k3
f(e) e
--- ---
0 0
1 1
2 2
3 -1
4 4
5 -3
6 -2
7 3
This representation is per Knuth volume 2 section 4.1 exercise 27. The exercise
there is to show all integers can be represented this way.
9 | 729 1458 2916 3645 5103 93312 7290
8 | 32 96 160 224 288
7 | 343 686 1029 1372 1715 2058 43904 3087 3430
6 | 216 1080 1512
5 | 125 250 375 500 750 875 16000 1125
4 | 64 192 320 448 576
3 | 27 54 108 135 189 3456 270
2 | 8 24 40 56 72
1 | 1 2 3 4 5 6 7 128 9 10
Y=0 |
---------------------------------------------------------------
X=0 1 2 3 4 5 6 7 8 9 10
The X axis begins with the integers 1 to 7 because f(1)=1 and f(2)=2 so N=X
until X has a prime p^3 or higher power. The first such is X=8=2^3 which is
f(7)=3 so N=2^7=128.
FUNCTIONS¶
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.- "$path = Math::PlanePath::FactorRationals->new ()"
- "$path = Math::PlanePath::FactorRationals->new (factor_coding => $str)"
- Create and return a new path object. "factor_coding" can be
"even/odd" (the default) "odd/even" "negabinary" "revbinary"
- "($x,$y) = $path->n_to_xy ($n)"
- Return X,Y coordinates of point $n on the path. If there's no point $n then the return is an empty list. This depends on factorizing $n and in the current code there's a hard limit on the amount of factorizing attempted. If $n is too big then the return is an empty list.
- "$n = $path->xy_to_n ($x,$y)"
- Return the N point number for coordinates "$x,$y". If there's nothing at "$x,$y", such as when they have a common factor, then return "undef". This depends on factorizing $y, or factorizing both $x and $y for negabinary or revbinary. In the current code there's a hard limit on the amount of factorizing attempted. If the coordinates are too big then the return is "undef".
OEIS¶
This enumeration of the rationals is in Sloane's Online Encyclopedia of Integer Sequences in the following forms<http://oeis.org/A071974> (etc)
A071974 X coordinate, numerators
A071975 Y coordinate, denominators
A019554 X*Y product
A102631 N in column X=1, n^2/squarefreekernel(n)
A072345 X and Y at N=2^k, being alternately 1 and 2^k
A011262 permutation N at transpose Y/X (exponents mangle odd<->even)
A060837 permutation DiagonalRationals -> FactorRationals
A071970 permutation RationalsTree CW -> FactorRationals
The last A071970 is rationals taken in order of the Stern diatomic sequence
stern[i]/stern[i+1] which is the Calkin-Wilf tree rows ("Calkin-Wilf
Tree" in Math::PlanePath::RationalsTree).
The negabinary representation is
A053985 index -> signed
A005351 signed positives -> index
A039724 signed positives -> index, in binary
A005352 signed negatives -> index
The reversing binary representation is
A065620 index -> signed
A065621 signed positives -> index
A048724 signed negatives -> index
SEE ALSO¶
Math::PlanePath, Math::PlanePath::GcdRationals, Math::PlanePath::RationalsTree, Math::PlanePath::CoprimeColumnsOther Ways to Do It¶
Niven gives another prime factor based construction but encoding N by runs of 1-bits,Ivan Niven, "Note on a paper by L. S.
Johnston", American Math. Monthly, volume 55, number 6, June-July 1948,
page 358. <http://www.jstor.org/stable/2304962>
N is written in binary each 0-bit is considered a separator. The number of
1-bits between each
N = 11 0 0 111 0 11 binary
| | |
2 0 3 2 f(e) = run lengths of 1-bits
-1 0 +2 -1 e exponent by "odd/even" style
X/Y = 2^(-1) * 3^(+2) * 5^0 * 7^(-1)
Kevin McCrimmon's note begins with a further possible encoding for N where the
prime powers from numerator are spread out to primes p[2i+1] and with 0 powers
sending a p[2i] power to the denominator. In this form the primes from X and Y
spread out to different primes rather than different exponents.
HOME PAGE¶
<http://user42.tuxfamily.org/math-planepath/index.html>LICENSE¶
Copyright 2011, 2012, 2013, 2014 Kevin Ryde This file is part of Math-PlanePath. 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/>.| 2014-08-30 | perl v5.20.1 |