| Math::PlanePath::FactorRationals(3pm) | User Contributed Perl Documentation | Math::PlanePath::FactorRationals(3pm) |
NAME¶
Math::PlanePath::FactorRationals -- rationals by prime powers
SYNOPSIS¶
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 per
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 in
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".
The current factorizing limits handle anything up to 2^32, and above that numbers comprised of small factors. But big numbers with big factors are not handled. Is this a good idea? For large inputs there's no merit in disappearing into a nearly-infinite loop. Perhaps the limits could be configurable and/or some advanced factoring modules attempted for a while if/when available.
OEIS¶
This enumeration of the rationals is in Sloane's Online Encyclopedia of Integer Sequences in the following forms
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::CoprimeColumns
Other Ways to Do It¶
Niven gives another prime factor based construction but encoding N by runs of 1-bits,
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¶
LICENSE¶
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 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/>.
| 2021-01-23 | perl v5.32.0 |