A calculational approach to path-based properties of the Eisenstein-Stern and Stern-Brocot trees via matrix algebra

• Type: Article in International Scientific Journal
• Date: 2016

Authors

Ferreira, JF (Author) Other; Mendes, A (Author) Other

Journal

Title: Journal of Logical and Algebraic Methods in Programming

Vol. 85

Pages: 906-920

ISSN: 2352-2208

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 1 Citation

Scopus - 0 Citations

Other information

Authenticus ID: P-00K-HQ9

DOI: 10.1016/j.jlamp.2015.11.004

Abstract (EN): This paper proposes a calculational approach to prove properties of two well-known binary trees used to enumerate the rational numbers: the Stern-Brocot tree and the Eisenstein-Stern tree (also known as Calkin-Wilf tree). The calculational style of reasoning is enabled by a matrix formulation that is well-suited to naturally formulate path-based properties, since it provides a natural way to refer to paths in the trees. Three new properties are presented. First, we show that nodes with palindromic paths contain the same rational in both the Stern-Brocot and Eisenstein-Stern trees. Second, we show how certain numerators and denominators in these trees can be written as the sum of two squares x(2) and y(2), with the rational x/y appearing in specific paths. Finally, we show how we can construct Sierpifiski's triangle from these trees of rationals. (C) 2015 Published by Elsevier Inc.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 15