---
name: "Math::PlanePath::FractionsTree"
section: "3pm"
platform: "linux"
package: "libmath-planepath-perl"
version: "129-1"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/Math::PlanePath::FractionsTree"
---

# Math::PlanePath::FractionsTree(3pm)

## NAME

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

## SYNOPSIS

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

## DESCRIPTION

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 \<http://ndirty.cute.fi/~karttu/Kepler/a086592.htm\>

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/Y
        /     \
    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

```
    Nstart=2^level
```

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.

## FUNCTIONS

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.

## OEIS

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

\<http://oeis.org/A020651\> (etc)

```
    tree_type=Kepler
      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.

## SEE ALSO

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

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

## HOME PAGE

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

## LICENSE

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