Sturmian word: Difference between revisions
(julia example) |
(added Raku programming solution) |
||
Line 184: | Line 184: | ||
# 01001010010010100101001001010010 |
# 01001010010010100101001001010010 |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
=={{header|Raku}}== |
|||
{{trans|Julia}} |
|||
<syntaxhighlight lang="raku" line># 20240215 Raku programming solution |
|||
sub chenfoxlyndonfactorization(Str $s) { |
|||
sub sturmian-word($m, $n) { |
|||
return sturmian-word($n, $m).trans('0' => '1', '1' => '0') if $m > $n; |
|||
my ($res, $k, $prev) = '', 1, 0; |
|||
while ($k * $m) % $n > 0 { |
|||
my $curr = ($k * $m) div $n; |
|||
$res ~= $prev == $curr ?? '0' !! '10'; |
|||
$prev = $curr; |
|||
$k++; |
|||
} |
|||
return $res; |
|||
} |
|||
sub fib-word($n) { |
|||
my ($Sn_1, $Sn) = '0', '01'; |
|||
for 2..$n { ($Sn, $Sn_1) = ($Sn~$Sn_1, $Sn) } |
|||
return $Sn; |
|||
} |
|||
my $fib = fib-word(7); |
|||
my $sturmian = sturmian-word(13, 21); |
|||
say "{$sturmian} <== 13/21" if $fib.substr(0, $sturmian.chars) eq $sturmian; |
|||
sub cfck($a, $b, $m, $n, $k) { |
|||
my (@p, @q) := [0, 1], [1, 0]; |
|||
my $r = (sqrt($a) * $b + $m) / $n; |
|||
for ^$k { |
|||
my $whole = $r.Int; |
|||
my ($pn, $qn) = $whole * @p[*-1] + @p[*-2], $whole * @q[*-1] + @q[*-2]; |
|||
@p.push($pn); |
|||
@q.push($qn); |
|||
$r = 1/($r - $whole); |
|||
} |
|||
return [@p[*-1], @q[*-1]]; |
|||
} |
|||
my $cfck-result = cfck(5, 1, -1, 2, 8); |
|||
say "{sturmian-word($cfck-result[0], $cfck-result[1])} <== 1/phi (8th convergent golden ratio)";</syntaxhighlight> |
|||
{{out}} Same as Julia example. |
|||
You may [https://ato.pxeger.com/run?1=ZVRNb5tAEJWqnvwrJhYRrA2YdVTVKiXxtWcfLTfCGAKyvcACtiLL-SO55ND-qf6azCyfSQ_Yq9k3b2beG3j9I_199fb2tyoja_Hv65ei2kJRVvKY-MI6p3JnaEcTNMHgMgIAGeKd-IwQiDgyu5S-KAzd0cG7B53rJv2os6MzSCIEwT1yuUBUx2cwNBkWmLvHJ5PhiYEHOqZxExyXMOc4OYQI28OEKsAtZiOFUzdTk2hBJSUm9qhdcqIqDYRqwItXVwDPaxIeHqgtuLnBJh29A9egGtMF99OpOl8HEhCtO7qORqRYlGxbKRqh1HQr8Yij4J8azCFBHF7XilIJc9vGcS4KqGCPnKlBVuJlmPuh7EqoqjQ4VkV4V_s7c1W4NQfvPvrE70yYc0QV_jOMLx3wCj9RFn43m_OxsgkpbRyrKKXhmD2hHcS-LBiEeR9zawGCKNgbmo_gLe0CbQz5OhBjmZmwzBn88GCNpHxjwpp83nTboCkXi1yWyMTIyy1MlaGz1k5S7Tf6PLT_HKe4I2iZtH-J0u1vDC2jJnKlfgObwDJbTyy-QWZ1mmMf_V3e3eXqrmVbZnZWFTExsi6WN7G8j6kR-Az3GqyGlv23OeumBbOtt-kcJRktXKzqUCKREvWbeh0sfOYmLDrzPr2Bg8S1QyMNA3zDGotnWZyAsShjCFJxCuVTKEp4Sg-7UID0yyRlY7f-FDRfhPbL8A4 Attempt This Online!] |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
Revision as of 16:11, 15 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.
![](https://upload.wikimedia.org/wikipedia/commons/thumb/2/2d/Fibonacci_word_cutting_sequence.png/300px-Fibonacci_word_cutting_sequence.png)
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 inverse 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
Julia
function sturmian_word(m, n)
m > n && return replace(sturmian_word(n, m), '0' => '1', '1' => '0')
res = ""
k, prev = 1, 0
while rem(k * m, n) > 0
curr = (k * m) ÷ n
res *= prev == curr ? "0" : "10"
prev = curr
k += 1
end
return res
end
function fibWord(n)
Sn_1, Sn, tmp = "0", "01", ""
for _ in 2:n
tmp = Sn
Sn *= Sn_1
Sn_1 = tmp
end
return Sn
end
const fib = fibWord(7)
const sturmian = sturmian_word(13, 21)
@assert fib[begin:length(sturmian)] == sturmian
println(" $sturmian <== 13/21")
""" return the kth convergent """
function cfck(a, b, m, n, k)
p = [0, 1]
q = [1, 0]
r = (sqrt(a) * b + m) / n
for _ in 1:k
whole = Int(trunc(r))
pn = whole * p[end] + p[end-1]
qn = whole * q[end] + q[end-1]
push!(p, pn)
push!(q, qn)
r = 1/(r - whole)
end
return [p[end], q[end]]
end
println(" $(sturmian_word(cfck(5, 1, -1, 2, 8)...)) <== 1/phi (8th convergent golden ratio)")
- Output:
01001010010010100101001001010010 <== 13/21 01001010010010100101001001010010 <== 1/phi (8th convergent golden ratio)
Phix
Rational part translated from Python, quadratic part a modified copy of the Continued fraction convergents task.
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)
printf(1," %s <== 13/21\n",sturmian)
function cfck(integer a, b, m, n, k)
-- return the kth convergent
sequence p = {0, 1},
q = {1, 0}
atom rem = (sqrt(a)*b + m) / n
for i=1 to k do
integer whole = trunc(rem),
pn = whole * p[-1] + p[-2],
qn = whole * q[-1] + q[-2]
p &= pn
q &= qn
rem = 1/(rem-whole)
end for
return {p[$],q[$]}
end function
integer {m,n} = cfck(5, 1, -1, 2, 8) -- (inverse golden ratio)
printf(1," %s <== 1/phi (8th convergent)\n",sturmian_word(m,n))
- Output:
01001010010010100101001001010010 <== 13/21 01001010010010100101001001010010 <== 1/phi (8th convergent)
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
Raku
# 20240215 Raku programming solution
sub chenfoxlyndonfactorization(Str $s) {
sub sturmian-word($m, $n) {
return sturmian-word($n, $m).trans('0' => '1', '1' => '0') if $m > $n;
my ($res, $k, $prev) = '', 1, 0;
while ($k * $m) % $n > 0 {
my $curr = ($k * $m) div $n;
$res ~= $prev == $curr ?? '0' !! '10';
$prev = $curr;
$k++;
}
return $res;
}
sub fib-word($n) {
my ($Sn_1, $Sn) = '0', '01';
for 2..$n { ($Sn, $Sn_1) = ($Sn~$Sn_1, $Sn) }
return $Sn;
}
my $fib = fib-word(7);
my $sturmian = sturmian-word(13, 21);
say "{$sturmian} <== 13/21" if $fib.substr(0, $sturmian.chars) eq $sturmian;
sub cfck($a, $b, $m, $n, $k) {
my (@p, @q) := [0, 1], [1, 0];
my $r = (sqrt($a) * $b + $m) / $n;
for ^$k {
my $whole = $r.Int;
my ($pn, $qn) = $whole * @p[*-1] + @p[*-2], $whole * @q[*-1] + @q[*-2];
@p.push($pn);
@q.push($qn);
$r = 1/($r - $whole);
}
return [@p[*-1], @q[*-1]];
}
my $cfck-result = cfck(5, 1, -1, 2, 8);
say "{sturmian-word($cfck-result[0], $cfck-result[1])} <== 1/phi (8th convergent golden ratio)";
- Output:
Same as Julia example.
You may Attempt This Online!
Wren
The 'rational number' function is a translation of the Python entry.
The 'quadratic number' function is a modified version of the one used in the Continued fraction convergents task.
import "./assert" for Assert
var SturmianWordRat = Fn.new { |m, n|
if (m > n) return SturmianWordRat.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 SturmianWordQuad = Fn.new { |a, b, m, n, k|
var p = [0, 1]
var q = [1, 0]
var rem = (a.sqrt * b + m) / n
for (i in 1..k) {
var whole = rem.truncate
var frac = rem.fraction
var pn = whole * p[-1] + p[-2]
var qn = whole * q[-1] + q[-2]
p.add(pn)
q.add(qn)
rem = 1 / frac
}
return SturmianWordRat.call(p[-1], q[-1])
}
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 = SturmianWordRat.call(13, 21)
Assert.equal(fib[0...sturmian.count], sturmian)
System.print("%(sturmian) from rational number 13/21")
var sturmian2 = SturmianWordQuad.call(5, 1, -1, 2, 8)
Assert.equal(sturmian, sturmian2)
System.print("%(sturmian2) from quadratic number (√5 - 1)/2 (k = 8)")
- Output:
01001010010010100101001001010010 from rational number 13/21 01001010010010100101001001010010 from quadratic number (√5 - 1)/2 (k = 8)