/ 
Math-PlanePath-62
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 idea might have been first by Kevin McCrimmon then independently (was it?) by Gerald Freilich in reverse, and again by 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 1872 
12  |      24                 600      1176                2904      
11  |      11   44   99  176  275  396  539  704  891 1100      1584 
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 1008 
 6  |       6                 150       294                 726      
 5  |       5   20   45   80       180  245  320  405       605  720 
 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  144 
Y=0 |
     ---------------------------------------------------------------
      X=0   1    2    3    4    5    6    7    8    9   10   11   12

An X,Y is mapped to N by

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

The effect is to distinguish prime factors coming from the numerator or denominator by making odd or even powers of those primes in N.

A rational X/Y has prime p with exponent p^s for either positive or negative s. Positive is in the numerator X, negative in the denominator Y. This is turned into a power p^k in N,

k = /  2*s      if s >= 0
    \  1-2*s    if s < 0

The effect is to map a signed exponent s to a positive exponent k,

 s          k
-1    ->    1
 1    ->    2
-2    ->    3
 2    ->    4
etc

For example (and other primes multiply in similarly),

N=3   ->  3^-1 = 1/3
N=9   ->  3^1  = 3/1
N=27  ->  3^-2 = 1/9
N=81  ->  3^2  = 9/1

Thinking in terms of X and Y values the key is that since X and Y have no common factor a prime p appears in one of X or Y but not both. The oddness/evenness of the p^k exponent in N can then encode which of the two it appears in.

Various Values

The leftmost column at X=1 is integers with odd powers of prime factors. That column is the fractions 1/Y so the s exponents of the primes there are all negative and thus all exponents in N are odd.

The bottom row at Y=1 is 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 alternate + and - as done here keeps the growth of N down to roughly X^2*Y^2, as per the first N formula.

FUNCTIONS

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

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

Create and return a new path object.

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 - numerators, X
A071975 - denominators, Y
A019554 - product num*den, ie. X*Y
A102631 - n^2/squarefreekernel(n), left column at X=1
A060837 - permutation DiagonalRationals -> FactorRationals
A071970 - permutation Stern/CW -> FactorRationals

The last A071970 is rationals taken in order of the Stern diatomic sequence stern[i]/stern[i+1], which is the order of the Calkin-Wilf tree rows (see "Calkin-Wilf Tree" in Math::PlanePath::RationalsTree).

BUGS

n_to_xy() depends on factorizing $n and xy_to_n() depends on factorizing $y. In the current code there's a limit on the amount of factorizing attempted and above that the return is empty or undef respectively. The present 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. But perhaps the limits could be configurable and/or some factoring modules tried for a while if/when available.

SEE ALSO

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

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