user
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.

Example Sturmian word when x = 0.618..., the golden ratio.

The Sturmian word can be computed thus as an algorithm:

* If 

  x
  >
  1
  {\displaystyle {\displaystyle x>1}}
  , then it is the inverse of the Sturmian word for 

  1

  /
  x
  {\displaystyle {\displaystyle 1/x}}
  . So we have reduced to the case of 

  0
  <
  x
  ≤
  1
  {\displaystyle {\displaystyle 0<x\leq 1}}
  .
* Iterate over 

  f
  l
  o
  o
  r
  (
  1
  x
  )
  ,
  f
  l
  o
  o
  r
  (
  2
  x
  )
  ,
  f
  l
  o
  o
  r
  (
  3
  x
  )
  ,
  …
  {\displaystyle {\displaystyle floor(1x),floor(2x),floor(3x),\dots }}
* If 

  k
  x
  {\displaystyle {\displaystyle kx}}
   is an integer, then the program terminates. Else, if 

  f
  l
  o
  o
  r
  (
  (
  k
  −
  1
  )
  x
  )
  =
  f
  l
  o
  o
  r
  (
  k
  x
  )
  {\displaystyle {\displaystyle floor((k-1)x)=floor(kx)}}
  , then the program outputs 0, else, it outputs 10.

The problem:

* Given a positive rational number 

  m
  n
  {\displaystyle {\displaystyle {\frac {m}{n}}}}
  , specified by two positive integers 

  m
  ,
  n
  {\displaystyle {\displaystyle m,n}}
  , output its entire Sturmian word.
* Given a quadratic real number 

  b


  a
  +
  m
  n
  >
  0
  {\displaystyle {\displaystyle {\frac {b{\sqrt {a}}+m}{n}}>0}}
  , specified by integers 

  a
  ,
  b
  ,
  m
  ,
  n
  {\displaystyle {\displaystyle a,b,m,n}}
  , where 

  a
  {\displaystyle {\displaystyle a}}
   is not a perfect square, output the first 

  k
  {\displaystyle {\displaystyle k}}
   letters of Sturmian words when given a positive number 

  k
  {\displaystyle {\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 

5
−
1
2
{\displaystyle {\displaystyle {\frac {{\sqrt {5}}-1}{2}}}}
, that is, 

a
=
5
,
b
=
1
,
m
=
−
1
,
n
=
2
{\displaystyle {\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 

f
l
o
o
r
(
k


a
)
{\displaystyle {\displaystyle floor(k{\sqrt {a}})}}
 for large 

k
{\displaystyle {\displaystyle k}}
. Floating point arithmetic would lose precision. One can either do this simply by directly searching for some integer 

a
′
{\displaystyle {\displaystyle a'}}
 such that 

a

′

2
≤

k

2
a
<
(

a
′
+
1

)

2
{\displaystyle {\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 

a
{\displaystyle {\displaystyle {\sqrt {a}}}}
. Let 

m
n
{\displaystyle {\displaystyle {\frac {m}{n}}}}
 be a convergent to 

a
{\displaystyle {\displaystyle {\sqrt {a}}}}
, such that 

n
≥
k
{\displaystyle {\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 

0
k
,


1
k
,
…
{\displaystyle {\displaystyle {\frac {0}{k}},{\frac {1}{k}},\dots }}
, the sequence would stride right across the gap 

(
m

/
n
,
2
x
−
m

/
n
)
{\displaystyle {\displaystyle (m/n,2x-m/n)}}
. Thus, we can take the largest 

l
{\displaystyle {\displaystyle l}}
 such that 

l

/
k
≤
m

/
n
{\displaystyle {\displaystyle l/k\leq m/n}}
, and we would know for sure that 

l
=
f
l
o
o
r
(
k


a
)
{\displaystyle {\displaystyle l=floor(k{\sqrt {a}})}}
.

In summary, 

f
l
o
o
r
(
k


a
)
=
f
l
o
o
r
(
m
k

/
n
)
{\displaystyle {\displaystyle floor(k{\sqrt {a}})=floor(mk/n)}}
 where 

m

/
n
{\displaystyle {\displaystyle m/n}}
 is the first continued fraction approximant to 

a
{\displaystyle {\displaystyle {\sqrt {a}}}}
 with a denominator 

n
≥
k
{\displaystyle {\displaystyle n\geq k}}
assistant
**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!