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 10131014. 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 nonnegative,
N = p1^f(e1) * p2^f(e2) * ...
f(e) = 2*e if e >= 0
= 12*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^(12*(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*e1 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 returnundef
.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 isundef
.
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 nearlyinfinite 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 CalkinWilf tree rows ("CalkinWilf 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 1bits,
Ivan Niven, "Note on a paper by L. S. Johnston", American Math. Monthly, volume 55, number 6, JuneJuly 1948, page 358. http://www.jstor.org/stable/2304962
N is written in binary each 0bit is considered a separator. The number of 1bits between each
N = 11 0 0 111 0 11 binary
  
2 0 3 2 f(e) = run lengths of 1bits
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/mathplanepath/index.html
LICENSE
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
This file is part of MathPlanePath.
MathPlanePath 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.
MathPlanePath 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 MathPlanePath. If not, see <http://www.gnu.org/licenses/>.