The n-dimensional Stern–Brocot tree
| Autor: | Håkan Lennerstad |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Unit sphere
Discrete mathematics Algebra and Number Theory Fibonacci number K-ary tree Coprime integers Computer Science::Information Retrieval 010102 general mathematics Astrophysics::Instrumentation and Methods for Astrophysics Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 0102 computer and information sciences 01 natural sciences Combinatorics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES 010201 computation theory & mathematics Stern–Brocot tree Minkowski's question mark function Computer Science::General Literature 0101 mathematics ComputingMilieux_MISCELLANEOUS Least common multiple Calkin–Wilf tree Mathematics |
| Zdroj: | International Journal of Number Theory. 15:1219-1236 |
| ISSN: | 1793-7310 1793-0421 |
| DOI: | 10.1142/s1793042119500672 |
| Popis: | This paper generalizes the Stern–Brocot tree to a tree that consists of all sequences of [Formula: see text] coprime positive integers. As for [Formula: see text] each sequence [Formula: see text] is the sum of a specific set of other coprime sequences, its Stern–Brocot set [Formula: see text], where [Formula: see text] is the degree of [Formula: see text] With an orthonormal base as the root, the tree defines a fast iterative structure on the set of distinct directions in [Formula: see text] and a multiresolution partition of [Formula: see text]. Basic proofs rely on a matrix representation of each coprime sequence, where the Stern–Brocot set forms the matrix columns. This induces a finitely generated submonoid [Formula: see text] of [Formula: see text], and a unimodular multidimensional continued fraction algorithm, also generalizing [Formula: see text]. It turns out that the [Formula: see text]-dimensional subtree starting with a sequence [Formula: see text] is isomorphic to the entire [Formula: see text]-dimensional tree. This allows basic combinatorial properties to be established. It turns out that also in this multidimensional version, Fibonacci-type sequences have maximal sequence sum in each generation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|