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

Math-PlanePath-104.tar.gz

Dependencies

Annotate this POD

Website

# CPAN RT

 New 1 Open 1
View/Report Bugs
Module Version: 104

# 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 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)

A020651  - Kepler numerators (RationalsTree AYT denominators)
A086592  - Kepler denominators
A086593  - Kepler sum X+Y, and every second denominator
A020650  - Kepler difference Y-X (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.

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