Math::PlanePath::FactorRationals -- rationals by prime powers
use Math::PlanePath::FactorRationals; my $path = Math::PlanePath::FactorRationals->new; my ($x, $y) = $path->n_to_xy (123);
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.
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.
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.
$n
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.
$x,$y
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.
$y
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.
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) 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).
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
http://user42.tuxfamily.org/math-planepath/index.html
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/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.