Sturmian word: Difference between revisions
imported>CosmiaNebula (fibonacci word example) |
imported>CosmiaNebula (python, rational case) |
||
Line 27: | Line 27: | ||
where <math>m/n</math> is the first continued fraction approximant to <math>\sqrt a</math> with a denominator <math>n \geq k</math> |
where <math>m/n</math> is the first continued fraction approximant to <math>\sqrt a</math> with a denominator <math>n \geq k</math> |
||
== [[Python]] == |
|||
For rational numbers:<syntaxhighlight lang="python3"> |
|||
def sturmian_word(m, n): |
|||
sturmian = "" |
|||
def invert(string): |
|||
return ''.join(list(map(lambda b: {"0":"1", "1":"0"}[b], string))) |
|||
if m > n: |
|||
return invert(sturmian_word(n, m)) |
|||
k = 1 |
|||
while True: |
|||
current_floor = int(k * m / n) |
|||
previous_floor = int((k - 1) * m / n) |
|||
if k * m % n == 0: |
|||
break |
|||
if previous_floor == current_floor: |
|||
sturmian += "0" |
|||
else: |
|||
sturmian += "10" |
|||
k += 1 |
|||
return sturmian |
|||
</syntaxhighlight> |
|||
Checking that it works on the finite Fibonacci word:<syntaxhighlight lang="python3"> |
|||
def fibWord(n): |
|||
Sn_1 = "0" |
|||
Sn = "01" |
|||
tmp = "" |
|||
for i in range(2, n + 1): |
|||
tmp = Sn |
|||
Sn += Sn_1 |
|||
Sn_1 = tmp |
|||
return Sn |
|||
fib = fibWord(10) |
|||
sturmian = sturmian_word(13, 21) |
|||
assert fib[:len(sturmian)] == sturmian |
|||
print(sturmian) |
|||
# Output: |
|||
# 01001010010010100101001001010010 |
|||
</syntaxhighlight> |
Revision as of 01:10, 1 February 2024
You are encouraged to solve this task according to the task description, using any language you may know.
A 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.
The Sturmian word can be computed thus as an algorithm:
- If , then it is the inverse of the Sturmian word for . So we have reduced to the case of .
- Iterate over
- If is an integer, then the program terminates. Else, if , then the program outputs 0, else, it outputs 10.
The problem:
- Given a positive rational number , specified by two positive integers , output its entire Sturmian word.
- Given a quadratic real number , specified by integers , where is not a perfect square, output the first letters of Sturmian words when given a positive number .
(If the programming language can represent infinite data structures, then that works too.)
A simple check is to do this for the golden ratio , that is, , which would just output the Fibonacci word.
Stretch goal: calculate the Sturmian word for other kinds of definable real numbers, such as cubic roots.
The key difficulty is accurately calculating for large . Floating point arithmetic would lose precision. One can either do this simply by directly searching for some integer such that , or by more trickly methods, such as the continued fraction approach.
First calculate the continued fraction convergents to . Let be a convergent to , such that , 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 , the sequence would stride right across the gap . Thus, we can take the largest such that , and we would know for sure that .
In summary,
where is the first continued fraction approximant to with a denominator
Python
For rational numbers:
def sturmian_word(m, n):
sturmian = ""
def invert(string):
return ''.join(list(map(lambda b: {"0":"1", "1":"0"}[b], string)))
if m > n:
return invert(sturmian_word(n, m))
k = 1
while True:
current_floor = int(k * m / n)
previous_floor = int((k - 1) * m / n)
if k * m % n == 0:
break
if previous_floor == current_floor:
sturmian += "0"
else:
sturmian += "10"
k += 1
return sturmian
Checking that it works on the finite Fibonacci word:
def fibWord(n):
Sn_1 = "0"
Sn = "01"
tmp = ""
for i in range(2, n + 1):
tmp = Sn
Sn += Sn_1
Sn_1 = tmp
return Sn
fib = fibWord(10)
sturmian = sturmian_word(13, 21)
assert fib[:len(sturmian)] == sturmian
print(sturmian)
# Output:
# 01001010010010100101001001010010