Sturmian word: Difference between revisions

A [[wp:Sturmian_word|Sturmian word]] is a binary sequence, finite or infinite, that makes up the cutting sequence for a positive real number x, as shown in the picture.

[[File:Fibonacci word cutting sequence.png|thumb|Example Sturmian word when x = 0.618..., the golden ratio.]]

First calculate the [[continued fraction convergents]] 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>.

 

 

 

== {{header|Phix}} ==