NAME

Math::PlanePath::MathImageSagherRationals -- rationals by prime factorization

SYNOPSIS

use Math::PlanePath::MathImageSagherRationals;
my $path = Math::PlanePath::MathImageSagherRationals->new;
my ($x, $y) = $path->n_to_xy (123);

DESCRIPTION

This path enumerates rationals X/Y with no common factor using a method by Yoram Sagher based on the prime factors in numerator and denominator.

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   12

Since X and Y have no common factor, a prime p appears in the factorization of X or Y but not both. If X has p^k then it's represented in N as p^2k, or if Y has p^k then in N as p^(2k-1). In N the odd/evenness of the power of p indicates whether it belongs in the numerator or denominator, and halving is the power there. This is a one-to-one mapping between rationals X/Y and integers N.

Fractions 1/K are at X=1,Y=K in the left column at X=1. Primes 1/P are there as N=P directly, or 1/P^2 as N=P^3, and in general 1/P^k as N==P^(2k-1). So the N values in that column are the primes and all integers whose prime factors all have odd powers.

Integer primes P/1 are in the bottom row at Y=1, as X=P^2,Y=1. In general any X/1 is N=X^2, so that row is all the perfect squares.

OEIS

This path is in Sloane's Online Encyclopedia of Integer Sequences in the following forms

http://oeis.org/A071974   (etc)

A071974 - numerators
A071975 - denominators
A060837 - permutation Cantor diagonal -> Sagher
A071970 - permutation CW/Stern -> Sagher

A071970 takes fractions in the Stern diatomic sequence stern[i]/stern[i+1], which is the order of the Calkin-Wilf tree read by rows (see "Calkin-Wilf Tree" in Math::PlanePath::RationalsTree).

FUNCTIONS

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

$path = Math::PlanePath::MathImageSagherRationals->new ()

Create and return a new path object.

SEE ALSO

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