Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T07:34:20.015Z Has data issue: false hasContentIssue false
  • English
  • Français

ON INTEGER SEQUENCES GENERATED BY LINEAR MAPS

Published online by Cambridge University Press:  01 May 2009

ARTŪRAS DUBICKAS
ARTŪRAS DUBICKAS*
Affiliation:
Department of Mathematics and Informatics, Vilnius University, Naugarduko 24, Vilnius LT-03225, Lithuania E-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let x0 < x1 < x2 < ⋅⋅⋅ be an increasing sequence of positive integers given by the formula xn=⌊βxn−1 + γ⌋ for n=1, 2, 3, . . ., where β > 1 and γ are real numbers and x0 is a positive integer. We describe the conditions on integers bd, . . ., b0, not all zero, and on a real number β > 1 under which the sequence of integers wn=bdxn+d + ⋅⋅⋅ + b0xn, n=0, 1, 2, . . ., is bounded by a constant independent of n. The conditions under which this sequence can be ultimately periodic are also described. Finally, we prove a lower bound on the complexity function of the sequence qxn+1 − pxn ∈ {0, 1, . . ., q−1}, n=0, 1, 2, . . ., where x0 is a positive integer, p > q > 1 are coprime integers and xn=⌈pxn−1/q⌉ for n=1, 2, 3, . . . A similar speculative result concerning the complexity of the sequence of alternatives (F:x↦x/2 or S:x↦(3x+1)/2) in the 3x+1 problem is also given.

Keywords

11B5011B8311R0668R15
Type
Research Article
Information
Glasgow Mathematical Journal , Volume 51 , Issue 2 , May 2009 , pp. 243 - 252
Copyright
Copyright © Glasgow Mathematical Journal Trust 2008

References

REFERENCES

1.Adamczewski, B. and Bugeaud, Y., On the complexity of algebraic numbers I. Expansions in integer bases, Ann. Math. 165 (2007), 547–565.CrossRefGoogle Scholar
2.Akiyama, S., Frougny, C. and Sakarovitch, J., Powers of rationals modulo 1 and rational base number systems, Isr. J. Math. 168 (2008), 53–91.CrossRefGoogle Scholar
3.Allouche, J.-P. and Shallit, J., Automatic sequences. Theory, applications, generalizations (Cambridge University Press, Cambridge, UK, 2003).CrossRefGoogle Scholar
4.Berstel, J. and Karhumäki, J., Combinatorics on words – a tutorial, in Current trends in theoretical computer science. The challenge of the new century, Vol. 2: Formal models and semantics (Paun, G.Rozenberg, G. and Salomaa, A., Editors), (World Scientific, River Edge, N J, 2004), 415–475.CrossRefGoogle Scholar
5.Dubickas, A., Arithmetical properties of powers of algebraic numbers, Bull. Lond. Math. Soc. 38 (2006), 70–80.CrossRefGoogle Scholar
6.Dubickas, A., Arithmetical properties of linear recurrent sequences, J. Number Theory 122 (2007), 142–150.CrossRefGoogle Scholar
7.Ferenczi, S. and Mauduit, C., Transcendence of numbers with a low complexity expansion, J. Number Theory 67 (1997), 146–161.CrossRefGoogle Scholar
8.Flatto, L., Lagarias, J. C. and Pollington, A. D., On the range of fractional parts {ξ (p/q)n}, Acta Arith. 70 (1995), 125–147.CrossRefGoogle Scholar
9.Frougny, C. and Solomyak, B., Finite β-expansions, Ergodic Theory Dyn. Syst. 12 (1994), 713–723.CrossRefGoogle Scholar
10.Graham, R. L., Knuth, D. E. and Patashnik, O., Concrete mathematics (Addison-Wesley, New York, 1989).Google Scholar
11.Guimond, L. S., Masáková, Z., and Pelantová, E., Arithmetics of beta-expansions, Acta Arith. 112 (2004), 23–40.CrossRefGoogle Scholar
12.Ito, S. and Takahashi, Y., Markov subshifts and the realization of β-expansions, J. Math. Soc. Jpn. 26 (1974), 33–55.CrossRefGoogle Scholar
13.Jakobczyk, F., On the generalized Josephus problem, Glasgow Math. J. 14 (1973), 168–173.CrossRefGoogle Scholar
14.Lothaire, M., Algebraic combinatorics on words, Encyclopedia of mathematics and its applications, Vol. 90 (Cambridge University Press, Cambridge, UK, 2002).CrossRefGoogle Scholar
15.Morse, M. and Hedlund, G. A., Symbolic dynamics II: Sturmian sequences, Am. J. Math. 62 (1940), 1–42.CrossRefGoogle Scholar
16.Odłyzko, A. and Wilf, H., Functional iteration and the Josephus problem, Glasgow Math. J. 33 (1991), 235–240.CrossRefGoogle Scholar
17.Parry, W., On the β-expansions of real numbers, Acta Math. Sci. Hung. 11 (1960), 401–416.CrossRefGoogle Scholar
18.Rényi, A., Representations for real numbers and their ergodic properties, Acta Math. Sci. Hung. 8 (1957), 477–493.CrossRefGoogle Scholar
19.Robinson, W. J., The Josephus problem, Math. Gaz. 44 (1960), 47–52.CrossRefGoogle Scholar
20.Schmidt, K., On periodic expansions of Pisot numbers and Salem numbers, Bull. Lond. Math. Soc. 12 (1980), 269–278.CrossRefGoogle Scholar
21.Sloane, N. J. A., The on-line encyclopedia of integer sequences, http://www.research.att.com/~njas/sequences.Google Scholar