Math::...nsTree(3pm)

💖 NAME 💖

Math::PlanePath::FractionsTree — bestie, it's literally fractions, but as a tree 🌳✨

(oh also hi, this is from the User Contributed Perl Documentation, the Math::...nsTree(3pm) page — cute name, truncated by the terminal, we move on 💅)

---

🌸 SYNOPSIS 🌸

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

---

🦋 DESCRIPTION 🦋

Okay so here's the vibe: this path enumerates fractions X/Y where 0 < X/Y < 1 and they're in reduced form — meaning X and Y share no common factor, no cap, they're coprime besties 🫶 — using a method by Johannes Kepler.

The fractions get traversed in rows of a binary tree. That tree effectively represents a coprime pair X,Y by subtraction steps of a subtraction-only form of Euclid's greatest common divisor algorithm — the kind that would prove X,Y are coprime. And the steps, left or right? Those get encoded/decoded as an N value. That's the whole bit ✨

🌳 Kepler Tree

The default tree, and honestly the only one currently, is by Kepler. Iconic of him.

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. (Would be. Are they here? No. Moving on 🎀)

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. (One copy. We're efficient like that 💅)

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 — not on the guest list, sorry 🚫

    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. Maximum! Main character energy 👑

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. Left = even, right = odd, that's the rule 🌈

---

✨ FUNCTIONS ✨

See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes. (The shared lore, iykyk 💜)

• $path = Math::PlanePath::FractionsTree->new () — Create and return a new path object. Fresh out the box 🎀
• $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). Big numbers, big feelings 😭

🧚 Tree Methods

Each point has 2 children, so the path is a complete binary tree. Two kids per node, balanced family fr fr 💖

• @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. Bit go brrr ⭐

• $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). Undo the append, slay 💅

• $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. Minimum = maximum = 2, a rare unanimous moment 🫶

• $bool = $path->tree_any_leaf() — Return false, since there are no leaf nodes in the tree. No leaves, all vibes 🍓

---

🔥 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. Duplication eliminated — we love a clean dataset ✨

---

👑 SEE ALSO 👑

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

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

(go read them, they're all iconic, this is your sign 🌈)

---

🌸 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/>.

⚠️ okay bestie real talk, that all-caps WARRANTY disclaimer is NOT a joke, it's the actual legal text — no warranty, no promises, that's the whole point of the license. Respect the fine print 🙈

---

and that's the whole page, we ate and left no crumbs 💅✨ this was perl v5.32.0, dated 2021-01-23, from the Math::...nsTree(3pm) page — mwah, bye bestie 🦋💖