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

作者：Ferreira Joao F^*; Mendes Alexandra

来源：Journal of Logical and Algebraic Methods in Programming, 2016, 85(5): 906-920.

DOI：10.1016/j.jlamp.2015.11.004

• Stern-Brocot tree
• Eisenstein-Stern tree (aka Calkin-Wilf tree)
• Calculational method
• Euclid's algorithm
• Sierphiski's triangle
• Rational number

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.

• 出版日期2016-8