Sturmian word: Difference between revisions
(Added Wren) |
(draft/clarify) |
||
Line 1: | Line 1: | ||
{{task}} |
{{draft task}} |
||
{{clarify task}} |
|||
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. |
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.]] |
[[File:Fibonacci word cutting sequence.png|thumb|Example Sturmian word when x = 0.618..., the golden ratio.]] |
||
Line 23: | Line 23: | ||
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>. |
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>. |
||
In summary,<math |
In summary, <math>floor(k\sqrt a) = floor(mk/n)</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> |
||
where <math>m/n</math> is the first continued fraction approximant to <math>\sqrt a</math> with a denominator <math>n \geq k</math> |
|||
== {{header|Phix}} == |
== {{header|Phix}} == |
Revision as of 16:14, 1 February 2024
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
Phix
with javascript_semantics
function sturmian_word(integer m, n)
if m > n then
return sq_sub('0'+'1',sturmian_word(n,m))
end if
string res = ""
integer k = 1, prev = 0
while remainder(k*m,n) do
integer curr = floor(k*m/n)
res &= iff(prev=curr?"0":"10")
prev = curr
k += 1
end while
return res
end function
function fibWord(integer n)
string Sn_1 = "0",
Sn = "01",
tmp = ""
for i=2 to n do
tmp = Sn
Sn &= Sn_1
Sn_1 = tmp
end for
return Sn
end function
string fib = fibWord(7),
sturmian = sturmian_word(13, 21)
assert(fib[1..length(sturmian)] == sturmian)
?sturmian
- Output:
"01001010010010100101001001010010"
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
Wren
For rational numbers m / n:
import "./assert" for Assert
var SturmianWord = Fn.new { |m, n|
if (m > n) return SturmianWord.call(n, m).reduce("") { |acc, c|
return acc + (c == "0" ? "1" : "0")
}
var sturmian = ""
var k = 1
while (k * m % n != 0) {
var currFloor = (k * m / n).floor
var prevFloor = ((k - 1) * m / n).floor
sturmian = sturmian + (prevFloor == currFloor ? "0" : "10")
k = k + 1
}
return sturmian
}
var fibWord = Fn.new { |n|
var sn1 = "0"
var sn = "01"
for (i in 2..n) {
var tmp = sn
sn = sn + sn1
sn1 = tmp
}
return sn
}
var fib = fibWord.call(10)
var sturmian = SturmianWord.call(13, 21)
Assert.equal(fib[0...sturmian.count], sturmian)
System.print(sturmian)
- Output:
01001010010010100101001001010010