Provided by: libmath-planepath-perl_125-1_all bug

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, as per

           Kevin McCrimmon, "Enumeration of the Positive Rationals", American Math. Monthly, Nov
           1960, page 868.  <http://www.jstor.org/stable/2309448>

           Gerald Freilich, "A Denumerability Formula for the Rationals", American Math. Monthly,
           Nov 1965, pages 1013-1014.  <http://www.jstor.org/stable/2313350>

           Yoram Sagher, "Counting the rationals", American Math. Monthly, Nov 1989, page 823.
           <http://www.jstor.org/stable/2324846>

       The result is

           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

       A given fraction X/Y with no common factor has a prime factorization

           X/Y = p1^e1 * p2^e2 * ...

       The exponents e[i] are positive, negative or zero, being positive when the prime is in the
       numerator or negative when in the denominator.  Those exponents are represented in an
       integer N by mapping the exponents to non-negative,

           N = p1^f(e1) * p2^f(e2) * ...

           f(e) = 2*e      if e >= 0
                = 1-2*e    if e < 0

           f(e)      e
           ---      ---
            0        0
            1       -1
            2        1
            3       -2
            4        2

       For example

           X/Y = 125/7 = 5^3 * 7^(-1)
           encoded as N = 5^(2*3) * 7^(1-2*(-1)) = 5^6 * 7^1 = 5359375

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

       The effect is to distinguish prime factors of the numerator or denominator by odd or even
       exponents of those primes in N.  Since X and Y have no common factor a given prime appears
       in one and not the other.  The oddness or evenness of the p^f() exponent in N can then
       encode which of the two X or Y it came from.

       The exponent f(e) in N has term 2*e in both cases, but the exponents from Y are reduced by
       1.  This can be expressed in the following form.  Going from X,Y to N doesn't need to
       factorize X, only Y.

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

       N=1,2,3,8,5,6,etc in the column X=1 is integers with odd powers of prime factors.  These
       are the fractions 1/Y so the 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 are the perfect squares.  That row is the integers X/1 so the
       exponents are all positive and thus in N become 2*e, giving simply N=X^2.

   Odd/Even
       Option "factor_coding => "odd/even"" changes the f() mapping to numerator exponents as odd
       numbers and denominator exponents as even.

           f(e) = 2*e-1    if e > 0
                = -2*e     if e <= 0

       The effect is simply to transpose X<->Y.

       "odd/even" is the form given by Kevin McCrimmon and Gerald Freilich.  The default
       "even/odd" is the form given by Yoram Sagher.

   Negabinary
       Option "factor_coding => "negabinary"" changes the f() mapping to negabinary as suggested
       in

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

       This coding is not as compact as odd/even and tends to make bigger N values,

           13  |    2197   4394   6591 140608  10985  13182  15379 281216
           12  |     108                         540           756
           11  |    1331   2662   3993  85184   6655   7986   9317 170368
           10  |    1000          3000                        7000
            9  |       9     18           576     45            63   1152
            8  |    8192         24576         40960         57344
            7  |     343    686   1029  21952   1715   2058         43904
            6  |     216                        1080          1512
            5  |     125    250    375   8000           750    875  16000
            4  |       4            12            20            28
            3  |      27     54          1728    135           189   3456
            2  |       8            24            40            56
            1  |       1      2      3     64      5      6      7    128
           Y=0 |
                ----------------------------------------------------------
                 X=0   1      2      3      4      5      6      7      8

   Reversing Binary
       Option "factor_coding => "revbinary"" changes the f() mapping to "reversing binary" where
       a given integer is represented as a sum of powers 2^k with alternating signs

           e = 2^k1 - 2^k2 + 2^k3 - ...           0 <= k1 < k2 < k3

           f(e)      e
           ---      ---
            0        0
            1        1
            2        2
            3       -1
            4        4
            5       -3
            6       -2
            7        3

       This representation is per Knuth volume 2 section 4.1 exercise 27.  The exercise there is
       to show all integers can be represented this way.

            9  |     729  1458        2916  3645        5103 93312        7290
            8  |      32          96         160         224         288
            7  |     343   686  1029  1372  1715  2058       43904  3087  3430
            6  |     216                    1080        1512
            5  |     125   250   375   500         750   875 16000  1125
            4  |      64         192         320         448         576
            3  |      27    54         108   135         189  3456         270
            2  |       8          24          40          56          72
            1  |       1     2     3     4     5     6     7   128     9    10
           Y=0 |
                ---------------------------------------------------------------
                 X=0   1     2     3     4     5     6     7     8     9    10

       The X axis begins with the integers 1 to 7 because f(1)=1 and f(2)=2 so N=X until X has a
       prime p^3 or higher power.  The first such is X=8=2^3 which is f(7)=3 so N=2^7=128.

FUNCTIONS

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

       "$path = Math::PlanePath::FactorRationals->new ()"
       "$path = Math::PlanePath::FactorRationals->new (factor_coding => $str)"
           Create and return a new path object.  "factor_coding" can be

               "even/odd"    (the default)
               "odd/even"
               "negabinary"
               "revbinary"

       "($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, or factorizing both $x and $y for negabinary or
           revbinary.  In the current code there's a hard limit on the amount of factorizing
           attempted.  If the coordinates are 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.
       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 the Calkin-Wilf tree rows ("Calkin-Wilf Tree" in
       Math::PlanePath::RationalsTree).

       The negabinary representation is

           A053985   index -> signed
           A005351   signed positives -> index
           A039724   signed positives -> index, in binary
           A005352   signed negatives -> index

       The reversing binary representation is

           A065620   index -> signed
           A065621   signed positives -> index
           A048724   signed negatives -> index

SEE ALSO

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

   Other Ways to Do It
       Niven gives another prime factor based construction but encoding N by runs of 1-bits,

           Ivan Niven, "Note on a paper by L. S. Johnston", American Math. Monthly, volume 55,
           number 6, June-July 1948, page 358.  <http://www.jstor.org/stable/2304962>

       N is written in binary each 0-bit is considered a separator.  The number of 1-bits between
       each

           N = 11 0 0 111 0 11  binary
                  | |     |
                2  0   3    2   f(e) = run lengths of 1-bits
               -1  0  +2   -1   e exponent by "odd/even" style

           X/Y = 2^(-1) * 3^(+2) * 5^0 * 7^(-1)

       Kevin McCrimmon's note begins with a further possible encoding for N where the prime
       powers from numerator are spread out to primes p[2i+1] and with 0 powers sending a p[2i]
       power to the denominator.  In this form the primes from X and Y spread out to different
       primes rather than different exponents.

HOME PAGE

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

LICENSE

       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017 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/>.