Sturmian word

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 ${\displaystyle x>1}$ , then it is the inverse of the Sturmian word for ${\displaystyle 1/x}$ . So we have reduced to the case of ${\displaystyle 0<x\leq 1}$ .
Iterate over ${\displaystyle floor(1x),floor(2x),floor(3x),\dots }$
If ${\displaystyle kx}$ is an integer, then the program terminates. Else, if ${\displaystyle floor((k-1)x)=floor(kx)}$ , then the program outputs 0, else, it outputs 10.

The problem:

Given a positive rational number ${\displaystyle {\frac {m}{n}}}$ , specified by two positive integers ${\displaystyle m,n}$ , output its entire Sturmian word.
Given a quadratic real number ${\displaystyle {\frac {b{\sqrt {a}}+m}{n}}>0}$ , specified by integers ${\displaystyle a,b,m,n}$ , where ${\displaystyle a}$ is not a perfect square, output the first ${\displaystyle k}$ letters of Sturmian words when given a positive number ${\displaystyle k}$ .

(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 ${\displaystyle {\frac {{\sqrt {5}}-1}{2}}}$ , that is, ${\displaystyle a=5,b=1,m=-1,n=2}$ , 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 ${\displaystyle floor(k{\sqrt {a}})}$ for large ${\displaystyle k}$ . Floating point arithmetic would lose precision. One can either do this simply by directly searching for some integer ${\displaystyle a'}$ such that ${\displaystyle a'^{2}\leq k^{2}a<(a'+1)^{2}}$ , or by more trickly methods, such as the continued fraction approach.

First calculate the continued fraction convergents to ${\displaystyle {\sqrt {a}}}$ . Let ${\displaystyle {\frac {m}{n}}}$ be a convergent to ${\displaystyle {\sqrt {a}}}$ , such that ${\displaystyle n\geq k}$ , 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 ${\displaystyle {\frac {0}{k}},{\frac {1}{k}},\dots }$ , the sequence would stride right across the gap ${\displaystyle (m/n,2x-m/n)}$ . Thus, we can take the largest ${\displaystyle l}$ such that ${\displaystyle l/k\leq m/n}$ , and we would know for sure that ${\displaystyle l=floor(k{\sqrt {a}})}$ .

In summary, ${\displaystyle floor(k{\sqrt {a}})=floor(mk/n)}$ where ${\displaystyle m/n}$ is the first continued fraction approximant to ${\displaystyle {\sqrt {a}}}$ with a denominator ${\displaystyle n\geq k}$

ALGOL 68

Translation of: Python

BEGIN # Sturmian word - based on the Python sample                    #

    PROC sturmian word = ( INT m, n )STRING:
         IF m > n THEN
            STRING sturmian := sturmian word( n, m );
            FOR s pos FROM LWB sturmian TO UPB sturmian DO
                CHAR c = sturmian[ s pos ];
                sturmian[ s pos ] := IF c = "0" THEN "1" ELIF c = "1" THEN "0" ELSE c FI
            OD;
            sturmian
         ELSE
            STRING sturmian := "";
            INT current floor := 0;
            FOR k WHILE ( k * m ) MOD n /= 0 DO
                INT previous floor = current floor;
                current floor := ( k * m ) OVER n;
                IF previous floor = current floor THEN
                    sturmian +:= "0"
                ELSE
                    sturmian +:= "10"
                FI
            OD;
            sturmian
         FI # sturmian word # ;

    # Checking that it works on the finite Fibonacci word:            #

    PROC fibonacci word = ( INT n )STRING:
         BEGIN
            STRING sn1 := "0", sn := "01";
            FROM 2 TO n DO
                STRING tmp = sn;
                sn +:= sn1;
                sn1 := tmp
            OD;
            sn
         END # fibonacci word # ;

    BEGIN
        STRING f word   = fibonacci word( 10 );
        STRING sturmian = sturmian word( 13, 21 );
        IF f word[ : UPB sturmian[ AT 1 ] AT 1 ] = sturmian THEN
            print( ( sturmian ))
        ELSE
            print( ( "*** unexpected result: (", sturmian, ") (", f word, ")" ) )
        FI;
        print( ( newline ) )
    END

END

Output:

01001010010010100101001001010010

BASIC

BASIC256

Translation of: FreeBASIC

fib = fibWord(10)
sturmian = sturmian_word(13, 21)
if left(fib, length(sturmian)) = sturmian then print sturmian
end

function invert(cadena)
	for i = 1 to length(cadena)
		b = mid(cadena, i, 1)
		if b = "0" then
			inverted += "1"
		else
			if b = "1" then
				inverted += "0"
			end if
		end if
	next
	return inverted
end function

function sturmian_word(m, n)
	sturmian = ""
	if m > n then 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 mod n = 0 then exit while
		if previous_floor = current_floor then
			sturmian += "0"
		else
			sturmian += "10"
		end if
		k += 1
	end while
	return sturmian
end function

function fibWord(n)
	Sn_1 = "0"
	Sn = "01"

	for i = 2 to n
		tmp = Sn
		Sn += Sn_1
		Sn_1 = tmp
	next
	return Sn
end function

Output:

01001010010010100101001001010010

FreeBASIC

Translation of: Python

Function invert(cadena As String) As String
    Dim As String inverted, b
    For i As Integer = 1 To Len(cadena)
        b = Mid(cadena, i, 1)
        inverted += Iif(b = "0", "1", "0")
    Next
    Return inverted
End Function

Function sturmian_word(m As Integer, n As Integer) As String
    Dim sturmian As String
    If m > n Then Return invert(sturmian_word(n, m))
    
    Dim As Integer k = 1
    Do
        Dim As Integer current_floor = Int(k * m / n)
        Dim As Integer previous_floor = Int((k - 1) * m / n)
        If k * m Mod n = 0 Then Exit Do
        sturmian += Iif(previous_floor = current_floor, "0", "10")
        k += 1
    Loop
    Return sturmian
End Function

Function fibWord(n As Integer) As String
    Dim As String Sn_1 = "0"
    Dim As String Sn = "01"
    
    For i As Integer = 2 To n
        Dim As String tmp = Sn
        Sn += Sn_1
        Sn_1 = tmp
    Next
    Return Sn
End Function

Dim As String fib = fibWord(10)
Dim As String sturmian = sturmian_word(13, 21)
If Left(fib, Len(sturmian)) = sturmian Then Print sturmian

Sleep

Output:

01001010010010100101001001010010

Yabasic

Translation of: FreeBASIC

fib$ = fibword$(10)
sturmian$ = sturmian_word$(13,21)
if left$(fib$,len(sturmian$)) = sturmian$  print sturmian$
end
sub invert$(cadena$)
    for i = 1 to len(cadena$)
        b$ = mid$(cadena$,i,1)
        if b$ = "0" then
            inverted$ = inverted$ +"1"
        elsif b$ = "1" then
            inverted$ = inverted$ +"0"
        fi
    next i
    return inverted$
end sub
sub sturmian_word$(m,n)
    sturmian$ = ""
    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 mod(k*m, n) = 0  break
        if previous_floor = current_floor then
            sturmian$ = sturmian$ +"0"
        else
            sturmian$ = sturmian$ +"10"
        fi
        k = k +1
    end while
    return sturmian$
end sub
sub fibword$(n)
    sn_1$ = "0"
    sn$ = "01"
    for i = 2 to n
        tmp$ = sn$
        sn$ = sn$ + sn_1$
        sn_1$ = tmp$
    next i
    return sn$
end sub

Output:

01001010010010100101001001010010

C++

#include <cmath>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

// Return the Sturmian word for the strictly positive rational number m / n
std::string sturmian_word_rational(const uint32_t& m, const uint32_t& n) {
	if ( m > n ) {
		const std::string inverse = sturmian_word_rational(n, m);
		std::string result;
		for ( const char& ch : inverse ) {
			result += ( ch == '0' ? "1" : "0" );
		}
		return result;
	}

	std::string sturmian;
	uint32_t k = 1;
	while ( ( k * m ) % n != 0 ) {
		const uint32_t previous_floor = ( k - 1 ) * m / n;
		const uint32_t current_floor = ( k * m ) / n;
		sturmian += ( previous_floor == current_floor ? "0" : "10" );
		k += 1;
	}
	return sturmian;
}

// Return the first 'letter_count' letters of Sturmian word for the strictly positive real number
// ( b * √(a) + m ) / n, where a is not a perfect square
std::string sturmian_word_quadratic(const int32_t& b, const uint32_t& a, const int32_t& m, const int32_t& n,
		                            const uint32_t& letter_count) {
	std::vector<uint32_t> p = { 0, 1 };
	std::vector<uint32_t> q = { 1, 0 };
	double remainder = ( b * std::sqrt(a) + m ) / n;

	for ( uint32_t i = 1; i <= letter_count; ++i ) {
		const int32_t integer_part = static_cast<uint32_t>(remainder);
		const double fraction_part  = remainder - integer_part;
		const int32_t pn = integer_part * p.back() + p[p.size() - 2];
		const int32_t qn = integer_part * q.back() + q[q.size() - 2];
		p.emplace_back(pn);
		q.emplace_back(qn);
		remainder = 1.0 / fraction_part;
	};
	return sturmian_word_rational(p.back(), q.back());
}

// Return the Fibonacci word for the given integer
// For more information visit https://en.wikipedia.org/wiki/Fibonacci_word
std::string fibonacci_word(const uint32_t& number) {
	std::string previous = "0";
	std::string result = "01";
	for ( uint32_t i = 2; i < number; ++i ) {
		std::string temp = result;
		result += previous;
		previous = temp;
	}
	return result;
}

int main() {
	const std::string sturmian = sturmian_word_rational(13, 21);
	std::cout << sturmian << " from rational number 13 / 21" << std::endl;

	std::cout << sturmian_word_quadratic(1, 5, -1, 2, 8)
			  << " from real number ( √5 - 1 ) / 2, the first 8 letters" << std::endl;

	std::string fibonacci = fibonacci_word(10);
	std::cout << "Sturmian word equals Fibonacci word? : " << std::boolalpha
		      << ( sturmian == fibonacci.substr(0, sturmian.length()) ) << std::endl;
}

Output:

01001010010010100101001001010010 from rational number 13 / 21
01001010010010100101001001010010 from real number ( √5 - 1 ) / 2, the first 8 letters
Sturmian word equals Fibonacci word? : true

FutureBasic

include "NSLog.incl"

local fn Sturmian_word( m as int, n as int ) as CFStringRef
  if ( m > n )
    CFStringRef replaced = fn StringByReplacingOccurrencesOfString( fn Sturmian_word( n, m ), @"0", @"2" )
    replaced = fn StringByReplacingOccurrencesOfString( replaced, @"1", @"0" )
    replaced = fn StringByReplacingOccurrencesOfString( replaced, @"2", @"1" )
    return replaced
  end if
  CFMutableStringRef res = fn MutableStringNew
  int k = 1, prev = 0
  while ( (k * m) % n > 0 )
    int curr = (k * m) / n
    if prev == curr then MutableStringAppendString( res, @"0" ) else MutableStringAppendString( res, @"10" )
    prev = curr
    k++
  wend
  return res
end fn = NULL

local fn FibWord( n as int ) as CFStringRef
  NSUInteger     i
  CFStringRef Sn_1 = @"0"
  CFStringRef   Sn = @"01"
  CFStringRef  tmp = @""
  
  for i = 2 to n
    tmp = Sn
    Sn = fn StringByAppendingString( Sn, Sn_1 )
    Sn_1 = tmp
  next
end fn = Sn

local fn Cfck( a as int, b as int, m as int, n as int, k as int ) as CFArrayRef
  NSUInteger i
  CFMutableArrayRef p = fn MutableArrayWithObjects( @0, @1, NULL )
  CFMutableArrayRef q = fn MutableArrayWithObjects( @1, @0, NULL )
  double r = ( sqr(a) * b + m ) / (double)n
  
  for i = 0 to k - 1
    int whole = fn trunc(r)
    int pn = whole * fn NumberIntValue( fn ArrayLastObject( p ) ) + fn NumberIntValue( p[fn ArrayCount(p) - 2] )
    int qn = whole * fn NumberIntValue( fn ArrayLastObject( q ) ) + fn NumberIntValue( q[fn ArrayCount(q) - 2] )
    MutableArrayAddObject( p, @(pn) )
    MutableArrayAddObject( q, @(qn) )
    r = 1 / (r - whole)
  next
end fn = @[fn ArrayLastObject( p ), fn ArrayLastObject( q )]

void local fn DoIt
  CFStringRef fib = fn FibWord(7)
  CFStringRef sturmian = fn Sturmian_word( 13, 21 )
  if fn StringIsEqual( left( fib, len( sturmian ) ), sturmian ) then NSLog( @"%@ <== from rational number 13/21", sturmian )
  CFArrayRef result = fn Cfck( 5, 1, -1, 2, 8 ) // inverse golden ratio
  NSLog( @"%@ <== 1/phi (8th convergent golden ratio)", fn Sturmian_word( fn NumberIntValue( result[0] ), fn NumberIntValue( result[1] ) ) )
end fn

fn DoIt

HandleEvents

Output:

01001010010010100101001001010010 <== from rational number 13/21
01001010010010100101001001010010 <== 1/phi (8th convergent golden ratio)

Go

Works with: Go version 1.10.2

Translation of: Julia

package main

import (
	"fmt"
	"math"
	"strings"
)

func sturmianWord(m, n int) string {
	if m > n {
		result := sturmianWord(n, m)
		result = strings.ReplaceAll(result, "0", "t")
		result = strings.ReplaceAll(result, "1", "0")
		return strings.ReplaceAll(result, "t", "1")
	}
	
	var sb strings.Builder
	k, prev := 1, 0
	
	for (k*m)%n > 0 {
		curr := (k * m) / n
		if prev == curr {
			sb.WriteString("0")
		} else {
			sb.WriteString("10")
		}
		prev = curr
		k++
	}
	
	return sb.String()
}

func fibWord(n int) string {
	sn_1, sn := "0", "01"
	
	for i := 2; i <= n; i++ {
		tmp := sn
		sn = sn + sn_1
		sn_1 = tmp
	}
	
	return sn
}

func cfck(a, b, m, n, k float64) [2]int {
	p := []int{0, 1}
	q := []int{1, 0}
	r := (math.Sqrt(a) * b + m) / n
	
	for i := 0; i < int(k); i++ {
		whole := int(math.Floor(r))
		pn := whole*p[len(p)-1] + p[len(p)-2]
		qn := whole*q[len(q)-1] + q[len(q)-2]
		p = append(p, pn)
		q = append(q, qn)
		r = 1 / (r - float64(whole))
	}
	
	return [2]int{p[len(p)-1], q[len(q)-1]}
}

func main() {
	fib := fibWord(7)
	sturmian := sturmianWord(13, 21)
	
	// Check if assertion holds
	if !strings.HasPrefix(fib, sturmian) {
		panic("Assertion failed")
	}
	
	fmt.Printf(" %s <== 13/21\n", sturmian)
	
	// Calculate convergent of golden ratio
	result := cfck(5, 1, -1, 2, 8)
	goldenRatioConvergent := sturmianWord(result[0], result[1])
	fmt.Printf(" %s <== 1/phi (8th convergent golden ratio)\n", goldenRatioConvergent)
}

Output:

01001010010010100101001001010010 <== 13/21
01001010010010100101001001010010 <== 1/phi (8th convergent golden ratio)

Java

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public final class SturmianWord {

	public static void main(String[] args) {
		String sturmian = sturmianWordRational(13, 21);
		System.out.println(sturmian + " from rational number 13 / 21");
		
		System.out.println(sturmianWordQuadratic(1, 5, -1, 2, 8) 
			+ " from real number ( √5 - 1 ) / 2, the first 8 letters");
		
		String fibonacci = fibonacciWord(10);
		System.out.println("Sturmian word equals Fibonacci word? : "
			+ sturmian.equals(fibonacci.substring(0, sturmian.length())));
	}
	
	// Return the Sturmian word for the strictly positive rational number m / n
	private static String sturmianWordRational(int m, int n) {
	    if ( m > n ) {
	    	return sturmianWordRational(n, m).chars().mapToObj( i -> String.valueOf((char) i) )
	    		.reduce("", (accumulator, term) -> accumulator += ( term.equals("0") ? "1" : "0" ));
	    }
	    
	    StringBuilder sturmian = new StringBuilder();
	    int k = 1;	    
	    while ( ( k * m ) % n != 0 ) {	        
	        final int previousFloor = ( k - 1 ) * m / n;
	        final int currentFloor = ( k * m ) / n;
	        sturmian.append( previousFloor == currentFloor ? "0" : "10" );
	        k += 1;
	    }	    
	    return sturmian.toString();	    
	}
	
	// Return the first 'letterCount' letters of Sturmian word for the strictly positive real number
	// ( b * √(a) + m ) / n, where a is not a perfect square
	private static String sturmianWordQuadratic(int b, int a, int m, int n, int letterCount) {
	    List<Integer> p = Stream.of( 0, 1 ).collect(Collectors.toList());
	    List<Integer> q = Stream.of( 1, 0 ).collect(Collectors.toList());	    
	    double remainder = ( b * Math.sqrt(a) + m ) / n;
	    
	    for ( int i = 1; i <= letterCount; i++ ) {
	        final int integerPart = (int) remainder;
	        final double fractionPart  = remainder - integerPart;
	        final int pn = integerPart * p.getLast() + p.get(p.size() - 2);
	        final int qn = integerPart * q.getLast() + q.get(q.size() - 2);
	        p.addLast(pn);
	        q.addLast(qn);
	        remainder = 1.0 / fractionPart;
	    };	    
	    return sturmianWordRational(p.getLast(), q.getLast());
	}
	
	// Return the Fibonacci word for the given integer 
	// @see https://en.wikipedia.org/wiki/Fibonacci_word
	private static String fibonacciWord(int number) {
	    String previous = "0";
	    String result = "01";	    
	    for ( int i = 2; i < number; i++ ) {
	        String temp = result;
	        result += previous;
	        previous = temp;
	    }	    
	    return result;
	}

}

Output:

01001010010010100101001001010010 from rational number 13 / 21
01001010010010100101001001010010 from real number ( √5 - 1 ) / 2, the first 8 letters
Sturmian word equals Fibonacci word? : true

jq

Adapted from Wren

Works with jq, the C implementation of jq

Works with gojq, the Go implementation of jq

## Generic functions
def assertEq($a; $b):
  if $a == $b then .
  else . as $in
  | "assertion violation: \($a) != \($b)" | debug
  | $in
  end;

# Emit a stream of characters
def chars: explode[] | [.] | implode;

# Input: a string of "0"s and "1"s
def flip:
  {"1": "0", "0": "1"} as $flip
  | reduce chars as $c (""; . + $flip[$c]);

def fibWord($n):
  { sn1: "0", sn: "01" }
  | reduce range (2; 1+$n) as $i (.; {sn: (.sn+.sn1), sn1: .sn})
  | .sn;

### Sturmian words

def SturmianWordRat($m; $n):
  if $m > $n
  then SturmianWordRat($n; $m) | flip
  else {sturmian: "", k: 1}
  | until (.k * $m % $n == 0;
      ( (.k * $m / $n)|floor) as $curr
      | (((.k - 1) * $m / $n)|floor) as $prev
      | .sturmian += (if $prev == $curr then "0" else "10" end)
      | .k += 1 )
  | .sturmian
  end;

def SturmianWordQuad($a; $b; $m; $n; $k):
  def fraction: . - trunc;
    { p: [0, 1],
      q: [1, 0],
     rem: ((($a|sqrt) * $b + $m) / $n)
    }
    | reduce range(1; 1+$k) as $i (.;
          (.rem|trunc) as $whole
          | (.rem|fraction) as $frac
          | ($whole * .p[-1] + .p[-2]) as $pn
          | ($whole * .q[-1] + .q[-2]) as $qn
          | .p += [$pn]
          | .q += [$qn]
          | .rem = (1 / $frac) )
    | SturmianWordRat(.p[-1]; .q[-1]) ;

### The tasks

def tasks:
  fibWord(10) as $fib
  | SturmianWordRat(13; 21) as $sturmian
  | SturmianWordQuad(5; 1; -1; 2; 8) as $sturmian2

  | assertEq($fib[0:$sturmian|length]; $sturmian)
  | assertEq($sturmian; $sturmian2)
  
  | "\($sturmian) from rational number 13/21",
    "\($sturmian2) from quadratic number (√5 - 1)/2 (k = 8)";

tasks

Output:

01001010010010100101001001010010 from rational number 13/21
01001010010010100101001001010010 from quadratic number (√5 - 1)/2 (k = 8)

Julia

Translation of: Phix

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)

Nim

Translation of: Phix

import std/[lenientops, math, strformat, strutils]

proc sturmianWord(m, n: Positive): string =
  if m > n:
    return sturmianWord(n, m).multiReplace(("0", "1"), ("1", "0"))
  var (k, prev) = (1, 0)
  while k * m mod n > 0:
    let curr = (k * m) div n
    result.add if curr == prev: "0" else: "10"
    prev = curr
    inc k


proc fibWord(n: Positive): string =
  var prev = "0"
  result = "01"
  for _ in 2..n:
    swap prev, result
    result = prev & result

const Fib = fibWord(7)
const Sturmian = sturmianWord(13, 21)
doAssert Fib[0..Sturmian.high] == Sturmian
echo &"{Sturmian} <== 13/21"


proc cfck(a, b, m, n, k: int): tuple[nom, denom: Natural] =
  var p = @[0, 1]
  var q = @[1, 0]
  var r = (sqrt(a.toFloat) * b + m) / n
  for _ in 1..k:
    let whole = int(r)
    let pn = whole * p[^1] + p[^2]
    let qn = whole * q[^1] + q[^2]
    p.add pn
    q.add qn
    r = 1 / (r - whole)
  result = (p[^1], q[^1])

let (m, n) = cfck(5, 1, -1, 2, 8)
echo &"{sturmianWord(m, n)} <== 1/phi (8th convergent golden ratio)"

Output:

01001010010010100101001001010010 <== 13/21
01001010010010100101001001010010 <== 1/phi (8th convergent golden ratio)

Perl

Translation of: Raku

# 20240916 Perl programming solution

use strict;
use warnings;
use POSIX qw(floor);

sub sturmian_word {
   my ($m, $n) = @_;
   if ($m > $n) {
      my $sw = sturmian_word($n, $m);
      return $sw =~ tr/01/10/;
   }
   my $res = "";
   my ($k, $prev) = (1, 0);
   while (($k * $m) % $n > 0) {
      my $curr = floor($k * $m / $n);
      $res .= ($prev == $curr) ? "0" : "10";
      $prev = $curr;
      $k++;
   }
   return $res;
}

sub fib_word {
   my ($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);
print "$sturmian <== 13/21\n" if substr($fib, 0, length($sturmian)) eq $sturmian;

sub cfck {
   my ($a, $b, $m, $n, $k) = @_;
   my @p = (0, 1);
   my @q = (1, 0);
   my $r = (sqrt($a) * $b + $m) / $n;
   for (1..$k) {
      my $whole = int($r);
      my ($pn, $qn) = ($whole * $p[-1] + $p[-2],  $whole * $q[-1] + $q[-2]);

      push @p, $pn;
      push @q, $qn;
      $r = 1 / ($r - $whole);
   }
   return ($p[-1], $q[-1]);
}

my ($p, $q) = cfck(5, 1, -1, 2, 8);
print sturmian_word($p, $q) . " <== 1/phi (8th convergent golden ratio)\n";

You may Attempt This Online!

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

Translation of: Julia

# 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

Library: Wren-assert

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)