Kevin Ryde > Math-PlanePath > Math::PlanePath::FractionsTree



Annotate this POD



Open  0
View/Report Bugs
Module Version: 121   Source  


Math::PlanePath::FractionsTree -- fractions by tree


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


This path enumerates fractions X/Y in the range 0 < X/Y < 1 and in reduced form, ie. X and Y having no common factor, using a method by Johannes Kepler.

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

Kepler Tree

The default and only tree currently is by Kepler.

Johannes Kepler, "Harmonices Mundi", Book III. Excerpt of translation by Aiton, Duncan and Field at

In principle similar bit reversal etc variations as in RationalsTree would 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/(X+Y)  Y/(X+Y)

Kepler described the tree as starting at 1, ie. 1/1, which descends to two identical 1/2 and 1/2. For the code here a single copy starting from 1/2 is used.

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 X=Y diagonal. The unused X,Y positions are where X and Y have a common factor. For example X=2,Y=6 have 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 end of each tree row, which is


The diagonal X=Y-1, fraction K/(K+1), is the second in each row, at N=Nstart+1. That's the maximum X/Y in each level.

The N values in the upper octant, ie. above the line Y=2*X, are even and those below that line are odd. This arises since X<Y so the left leg X/(X+Y) < 1/2 and the right leg Y/(X+Y) > 1/2. The left is an even N and the right an odd N.


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

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

Create and return a new path object.

$n = $path->n_start()

Return 1, the first N in the path.

($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).

Tree Methods

Each point has 2 children, so the path is a complete binary tree.

@n_children = $path->tree_n_children($n)

Return the two children of $n, or an empty list if $n < 1 (before the start of the path).

This is simply 2*$n, 2*$n+1. The children are $n with an extra bit appended, either a 0-bit or a 1-bit.

$num = $path->tree_n_num_children($n)

Return 2, since every node has two children, or return undef if $n<1 (before the start of the path).

$n_parent = $path->tree_n_parent($n)

Return the parent node of $n, or undef if $n <= 1 (the top of the tree).

This is simply floor($n/2), stripping the least significant bit from $n (undoing what tree_n_children() appends).

$depth = $path->tree_n_to_depth($n)

Return the depth of node $n, or undef if there's no point $n. The top of the tree at N=1 is depth=0, then its children depth=1, etc.

The structure of the tree with 2 nodes per point means the depth is simply floor(log2(N)), so for example N=4 through N=7 are all depth=2.

Tree Descriptive Methods

$num = $path->tree_num_children_minimum()
$num = $path->tree_num_children_maximum()

Return 2 since every node has 2 children, making that both the minimum and maximum.

$bool = $path->tree_any_leaf()

Return false, since there are no leaf nodes in the tree.


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

      A020651  - X numerator (RationalsTree AYT denominators)
      A086592  - Y denominators
      A086593  - X+Y sum, and every second denominator
      A020650  - Y-X difference (RationalsTree AYT numerators)

The tree descends as X/(X+Y) and Y/(X+Y) so the denominators are two copies of X+Y time after the initial 1/2. A086593 is every second, starting at 2, eliminating the duplication. This is also the sum X+Y, from value 3 onwards, as can be seen by thinking of writing a node as the X+Y which would be the denominators it descends to.


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

Math::NumSeq::SternDiatomic, Math::ContinuedFraction



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

syntax highlighting: