Sturmian word: Difference between revisions
Content added Content deleted
imported>CosmiaNebula (Sturmian word) |
imported>CosmiaNebula (described the problem) |
||
Line 5: | Line 5: | ||
The Sturmian word can be computed thus as an algorithm: |
The Sturmian word can be computed thus as an algorithm: |
||
* If x > 1, then it is the inverse of the Sturmian word for (1/x). So we have reduced to the case of 0 < x |
* If x > 1, then it is the inverse of the Sturmian word for (1/x). So we have reduced to the case of <math>0 < x \leq 1</math>. |
||
* Iterate over <math>floor(1x), floor(2x), floor(3x), \dots </math> |
* Iterate over <math>floor(1x), floor(2x), floor(3x), \dots </math> |
||
* If <math>kx </math> is an integer, then the program terminates. Else, if <math>floor((k-1)x) = floor(kx)</math>, then the program outputs 0, else, it outputs 10. |
* If <math>kx </math> is an integer, then the program terminates. Else, if <math>floor((k-1)x) = floor(kx)</math>, then the program outputs 0, else, it outputs 10. |
||
The problem: |
|||
* Given a positive rational number <math>\frac mn</math>, specified by two positive integers <math>m, n</math>, output its entire Sturmian word. |
|||
* Given a quadratic real number <math>\frac{\sqrt{a} + m}{n}</math>, specified by three positive integers <math>a, m, n </math>, where <math>a</math> is not a perfect square, output the first <math>k</math> letters of its Sturmian word when given a positive number <math>k</math>. |
|||
Stretch goal: calculate the Sturmian word for other kinds of definable real numbers, such as cubic roots. |
Revision as of 22:44, 31 January 2024
Sturmian word
You are encouraged to solve this task according to the task description, using any language you may know.
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 x > 1, then it is the inverse of the Sturmian word for (1/x). 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 three positive integers , where is not a perfect square, output the first letters of its Sturmian word when given a positive number .
Stretch goal: calculate the Sturmian word for other kinds of definable real numbers, such as cubic roots.