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 11An X,Y is mapped to N by
X^2 * Y^2
N = --------------------
distinct primes in YThe 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 < 0The effect is to map a signed s to positive k,
s k
--- ---
-1 <-> 1
1 <-> 2
-2 <-> 3
2 <-> 4
etcFor 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/1Thinking 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
$non the path. If there's no point$nthen the return is an empty list.This depends on factorizing
$nand in the current code there's a hard limit on the amount of factorizing attempted. If$nis 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
$yand in the current code there's a hard limit on the amount of factorizing attempted. If$yis 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 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)
A060837 - permutation DiagonalRationals -> FactorRationals
A071970 - permutation RationalsTree CW -> FactorRationalsThe 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
David M. Bradley, "Counting the Positive Rationals: A Brief Survey",
http://arxiv.org/abs/math/0509025HOME PAGE
http://user42.tuxfamily.org/math-planepath/index.html
LICENSE
Copyright 2011, 2012 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/>.