Kevin Ryde > Math-PlanePath-105 > Math::PlanePath::FactorRationals
Module Version: 105

# 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
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

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 factor p with exponent p^s for 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 s to positive k,

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

For example (and other primes multiply 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 any 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 X or Y it came from.

## Various Values

N=1,2,3,8,5,6,etc in the column X=1 is integers with odd powers of prime factors. This is the fractions 1/Y so the s 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 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 "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. But 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).

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

http://user42.tuxfamily.org/math-planepath/index.html