Sturmian word: Difference between revisions

* Given a quadratic real number <math>\frac{b\sqrt{a} + m}{n} > 0</math>, specified by three positive integers <math>a, b, m, n </math>, where <math>a</math> is not a perfect square, output the first <math>k</math> letters of its Sturmian wordwords when given a positive number <math>k</math>.

First calculate the [[continued fraction representation of <math>\sqrt a</math>, then obtaining the convergent sequenceconvergents]] to <math>\sqrt a</math>. Let <math>\frac mn </math> be a convergent to <math>\sqrt a</math>, such that <math>n \geq k</math>, then since the convergent sequence is the '''best rational approximant''' for denominators up to that point, we know for sure that, if we write out <math>\frac{0}{k}, \frac{1}{k}, \dots</math>, the sequence would stride right across the gap <math>(m/n, 2x - m/n)</math>. Thus, we can take the largest <math>l</math> such that <math>l/k \leq m/n</math>, and we would know for sure that <math>l = floor(k\sqrt a)</math>.