/ 
Math-PlanePath-109
River stage one • 3 direct dependents • 4 total dependents
/ Math::PlanePath::FactorRationals

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. This is per Kevin McCrimmon, and independently Gerald Freilich, and also Yoram Sagher.

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 either positive or negative, being positive when the prime is in the numerator or negative when in the denominator. Those exponents are represented in an integer N by

   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 2*e in both cases, with those from Y reduced by 1. This can be expressed in the following form, which shows how going from X,Y to N doesn't need to factorize X, only Y.

         X^2 * Y^2
N = --------------------
    distinct primes in Y

The exponents mapped positive<->even and negative<->odd is the form given by Freilich and Sagher. McCrimmon has them the opposite, as positive<->odd negative<->even. The only difference in the two is to swap Y/X.

Various Values

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 s exponents there are all positive and thus in N become 2*s, giving simply N=X^2.

As noted by David M. Bradley, other mappings of signed <-> unsigned powers could give other enumerations. The "negabinary" a[k]*(-2)^k is one possibility, or the "reversing binary representation" (-1)^k*2^ek of Knuth vol 2 section 4.1 exercise 27. But the alternating "+" and "-" here keeps the growth of N down to roughly X^2*Y^2, per the N=X^2*Y^2/Yprimes formula above.

FUNCTIONS

See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.

$path = Math::PlanePath::FactorRationals->new ()

Create and return a new path object.

($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 and in the current code there's a hard limit on the amount of factorizing attempted. If $y is 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 also the order of the Calkin-Wilf tree rows ("Calkin-Wilf Tree" in Math::PlanePath::RationalsTree).

SEE ALSO

Math::PlanePath, Math::PlanePath::GcdRationals, Math::PlanePath::RationalsTree, Math::PlanePath::CoprimeColumns

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

David M. Bradley, "Counting the Positive Rationals: A Brief Survey", http://arxiv.org/abs/math/0509025

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/>.