Ostrowski numeration¶
Ostrowski numeration system
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 >= 0alpha
– 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])