NAME

Math::PlanePath::MathImageFractionsTree -- fractions by tree

SYNOPSIS

use Math::PlanePath::MathImageFractionsTree;
my $path = Math::PlanePath::MathImageFractionsTree->new (tree_type => 'Kepler');
my ($x, $y) = $path->n_to_xy (123);

DESCRIPTION

This path enumerates fractions X/Y < 1 in reduced form, ie. X and Y having no common factor and X<Y so value 0 < X/Y < 1.

Fractions are traversed by rows of a binary tree which effectively represents a coprime pair X,Y by the steps of the binary greatest common divisor algorithm which would prove X,Y coprime. The steps left or right are encoded/decoded as an N value.

The only tree currently is Johannes Kepler, though in principle some bit reversal etc variations such as in RationalsTree may be possible.

N=1                             1/2
                          ------   ------
N=2 to N=3             1/3               2/3
                      /    \            /   \
N=4 to N=7         1/4      3/4      2/5      3/5
                   | |      | |      | |      | |
N=8 to N=15     1/5  4/5  3/7 4/7  2/7 5/7  3/8 5/8

A node descends as

      X/Y
    /     \
X/(X+Y)  Y/(X+Y)

Plotting the N values by X,Y is as follows. Since it's only fractions X/Y<1, ie. X<Y, all points are above the diagonal. The unused X,Y positions are where X and Y have a common factor. For example X=2,Y=6 has common factor 2 so is never reached.

12  |    1024                  26        27                1025
11  |     512   48   28   22   34   35   23   29   49  513     
10  |     256        20                  21       257          
 9  |     128   24        18   19        25  129               
 8  |      64        14        15        65                    
 7  |      32   12   10   11   13   33                         
 6  |      16                  17                              
 5  |       8    6    7    9                                   
 4  |       4         5                                        
 3  |       2    3                                             
 2  |       1                                                  
 1  |
Y=0 |   
     ----------------------------------------------------------
      X=0   1    2    3    4    5    6    7    8    9   10   11

The X=1 vertical is the fractions 1/Y at the left of each tree row, which is at N value

Nstart=2^level

The X=Y-1 diagonal is the second in each row, Nstart+1, which is the maximum X/Y in that level.

OEIS

The trees are in Sloane's Online Encyclopedia of Integer Sequences in the following forms

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

A020651  - Kepler numerators
A086592  - Kepler half-tree denominators
A086593  - Kepler half-tree denominators, every second value

FUNCTIONS

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

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

Create and return a new path object.

($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)

Return a range of N values which occur in a rectangle with corners at $x1,$y1 and $x2,$y2. The range is inclusive.

For reference, $n_hi can be quite large because within each row there's only one new 1/Y fraction. So if X=1 is included then roughly $n_hi = 2**max(x,y). If min(x,y) is bigger than 1 then it reduces a little to roughly 2**(max/min + min).

SEE ALSO

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

Math::NumSeq::SternDiatomic

Johannes Kepler, "Harmonices Mundi" Book III. Excerpt at

http://ndirty.cute.fi/~karttu/Kepler/a086592.htm