Factor Complexity p(n)

Sturmian words have complexity p(n) = n + 1, meaning they have exactly n+1 distinct factors (subwords) of length n. This is the minimum complexity for non-eventually-periodic sequences.

About Sturmian Words

Cutting Sequences: A Sturmian word encodes a line with irrational slope α on a unit grid. When the line crosses a horizontal grid line, we write '0'; when it crosses a vertical line, we write '1'.

Balance Property: For any two factors (subwords) of the same length, the number of 1s differs by at most 1. This is equivalent to being a Sturmian word.

Famous Example: The Fibonacci word uses slope 1/φ (golden ratio), producing: 0100101001...