Ostrowski numeration

In mathematics, Ostrowski numeration, named after Alexander Ostrowski, is either of two related numeration systems based on continued fractions: a non-standard positional numeral system for integers and a non-integer representation of real numbers.

Fix a positive irrational number α with continued fraction expansion [a₀; a₁, a₂, ...]. Let (q_n) be the sequence of denominators of the convergents p_n/q_n to α: so q_n = a_nq_n−1 + q_n−2. Let α_n denote Tⁿ(α) where T is the Gauss map T(x) = {1/x}, and write β_n = (−1)ⁿ⁺¹ α₀ α₁ ... α_n: we have β_n = a_nβ_n−1 + β_n−2.

Real number representations

Every positive real x can be written as

$x=\sum _{n=1}^{\infty }b_{n}\beta _{n}\$

where the integer coefficients 0 ≤ b_n ≤ a_n and if b_n = a_n then b_n−1 = 0.

Integer representations

Every positive integer N can be written uniquely as

$N=\sum _{n=1}^{k}b_{n}q_{n}\$

where the integer coefficients 0 ≤ b_n ≤ a_n and if b_n = a_n then b_n−1 = 0.

If α is the golden ratio, then all the partial quotients a_n are equal to 1, the denominators q_n are the Fibonacci numbers and we recover Zeckendorf's theorem on the Fibonacci representation of positive integers as a sum of distinct non-consecutive Fibonacci numbers.

See also

• Complete sequence

References

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015..
• Epifanio, C.; Frougny, C.; Gabriele, A.; Mignosi, F.; Shallit, J. (2012). "Sturmian graphs and integer representations over numeration systems". Discrete Appl. Math. 160 (4–5): 536–547. doi:10.1016/j.dam.2011.10.029. ISSN 0166-218X. Zbl 1237.68134.
• Ostrowski, Alexander (1921). "Bemerkungen zur Theorie der diophantischen Approximationen". Hamb. Abh. (in German). 1: 77–98. JFM 48.0197.04.
• Pytheas Fogg, N. (2002). Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, Anne (eds.). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.