NAME
Math::PlanePath::MathImagePowerRationals -- rationals by prime powers
SYNOPSIS
use Math::PlanePath::MathImagePowerRationals;
my $path = Math::PlanePath::MathImagePowerRationals->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 and independently (was it?) by Gerald Freilich in reverse and then 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 12An X,Y is mapped to N by
X^2 * Y^2
N = --------------------
distinct primes in YThe effect is to distinguish primes coming from the numerator or denominator by making odd or even powers in N.
In a rational X/Y each prime p has an exponent p^s with s positive or negative. 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 < 0This maps a signed exponent s to a positive exponent k,
s k
-1 -> 1
1 -> 2
-2 -> 3
2 -> 4
etcFor 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/1Thinking in terms of X and Y values the key is that since X and Y have no common factor a prime p appears in the factorization 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.
Values
The leftmost column X=1,Y=K is the square-free integers N. That column is the fractions 1/K so the s exponents of the primes there are all negative and thus all exponents in N are odd, so N is square-free.
The bottom row X=K,Y=1 is the perfect squares. That row is the integers K/1 so the s exponents there are all positive and thus in N become 2*s, giving simply N=K^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 X^2*Y^2 or thereabouts per the first N formula.
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
A071975 - denominators
A060837 - permutation DiagonalRationals -> PowerRationals
A071970 - permutation Stern/CW -> PowerRationalsThe 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).
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.
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). Anything up to 2^32 is handled, and numbers bigger than that entirely comprised of small factors, but not big numbers with big factors.
Is this a good idea? For large inputs there's no value 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