# Ostrowski numeration¶

Ostrowski numeration

See [Ber2001].

REFERENCES:

Ber2001

Valérie Berthé. Autour du système de numération d’Ostrowski. Bull. Belg. Math. Soc. Simon Stevin, 8(2):209–239, 2001. Journées Montoises d’Informatique Théorique (Marne-la-Vallée, 2000).

Bou2015

Bourla, Avraham. « Irrational Base Counting ». arXiv:1511.02179 [math], 6 novembre 2015. http://arxiv.org/abs/1511.02179.

AUTHOR:

• Sébastien Labbé, May 24, 2017

slabbe.ostrowski.cf_positive_representation(beta, alpha)
slabbe.ostrowski.ostrowski_integer(n, alpha)

INPUT:

• n – integer >= 0

• alpha – irrational real number > 0

EXAMPLES:

sage: from slabbe.ostrowski import ostrowski_integer
sage: ostrowski_integer(5, golden_ratio)
([0, 0, 0, 0, 1], [1, 1, 2, 3, 5])
sage: ostrowski_integer(10, golden_ratio)
([0, 0, 1, 0, 0, 1], [1, 1, 2, 3, 5, 8])
sage: ostrowski_integer(123456, e)
([0, 0, 1, 0, 2, 0, 0, 5, 0, 0, 5, 0, 1, 6],
[1, 1, 3, 4, 7, 32, 39, 71, 465, 536, 1001, 8544, 9545, 18089])
sage: ostrowski_integer(123456, pi)
([4, 11, 0, 211, 0, 0, 0, 1],
[1, 7, 106, 113, 33102, 33215, 66317, 99532])


TESTS:

sage: ostrowski_integer(10, 4/5)
Traceback (most recent call last):
...
ValueError: alpha (=4/5) must be irrational

sage: for i in range(10): print(i, ostrowski_integer(i, golden_ratio))
0 ([], [])
1 ([0, 1], [1, 1])
2 ([0, 0, 1], [1, 1, 2])
3 ([0, 0, 0, 1], [1, 1, 2, 3])
4 ([0, 1, 0, 1], [1, 1, 2, 3])
5 ([0, 0, 0, 0, 1], [1, 1, 2, 3, 5])
6 ([0, 1, 0, 0, 1], [1, 1, 2, 3, 5])
7 ([0, 0, 1, 0, 1], [1, 1, 2, 3, 5])
8 ([0, 0, 0, 0, 0, 1], [1, 1, 2, 3, 5, 8])
9 ([0, 1, 0, 0, 0, 1], [1, 1, 2, 3, 5, 8])


Digits of numbers from 1 to 24 in base sqrt(2)-1 where (q_k)_0^3=(1,2,5,12) appearing in [Bou2015]:

sage: rows = [[i]+ostrowski_integer(i, sqrt(2)-1)[0]+[0,0,0,0] for i in range(25)]
sage: table(rows=rows,header_row='N c1 c2 c3 c4'.split())
N    c1   c2   c3   c4
+----+----+----+----+----+
0    0    0    0    0
1    1    0    0    0
2    0    1    0    0
3    1    1    0    0
4    0    2    0    0
5    0    0    1    0
6    1    0    1    0
7    0    1    1    0
8    1    1    1    0
9    0    2    1    0
10   0    0    2    0
11   1    0    2    0
12   0    0    0    1
13   1    0    0    1
14   0    1    0    1
15   1    1    0    1
16   0    2    0    1
17   0    0    1    1
18   1    0    1    1
19   0    1    1    1
20   1    1    1    1
21   0    2    1    1
22   0    0    2    1
23   1    0    2    1
24   0    0    0    2

slabbe.ostrowski.ostrowski_real(beta, alpha, stop=10, verbose=False)

this is broken code

EXAMPLES:

sage: from slabbe.ostrowski import ostrowski_real
sage: ostrowski_real(golden_ratio^-2, golden_ratio-1, stop=5)   # not tested
Traceback (most recent call last):
...
AssertionError: 0 <= b_2(=3) <= a_2(=1) is false

sage: ostrowski_real(golden_ratio^-3, golden_ratio-1, stop=5)
([0, 0, 1, 0, 0],
[golden_ratio - 1,
golden_ratio - 2,
2*golden_ratio - 3,
3*golden_ratio - 5,
5*golden_ratio - 8])