Provided by: libmath-planepath-perl_113-1_all 
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
Kevin 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
in
David 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".
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
<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::CoprimeColumns
Other 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 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/>.