Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Iterated floor function, algebraic numbers, discrete chaos, Beatty subsequences, semigroups


Author: Aviezri S. Fraenkel
Journal: Trans. Amer. Math. Soc. 341 (1994), 639-664
MSC: Primary 11B83; Secondary 11B39, 11Z50, 58F13
DOI: https://doi.org/10.1090/S0002-9947-1994-1138949-9
MathSciNet review: 1138949
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For a real number $ \alpha $, the floor function $ \left\lfloor \alpha \right\rfloor $ is the integer part of $ \alpha $. The sequence $ \{ \left\lfloor {m\alpha } \right\rfloor :m = 1,2,3, \ldots \} $ is the Beatty sequence of $ \alpha $. Identities are proved which express the sum of the iterated floor functional $ {A^i}$ for $ 1 \leq i \leq n$, operating on a nonzero algebraic number $ \alpha $ of degree $ \leq n$, in terms of only $ {A^1} = \left\lfloor {m\alpha } \right\rfloor ,m$ and a bounded term. Applications include discrete chaos (discrete dynamical systems), explicit construction of infinite nonchaotic subsequences of chaotic sequences, discrete order (identities), explicit construction of nontrivial Beatty subsequences, and certain arithmetical semigroups. (Beatty sequences have a large literature in combinatorics. They have also been used in nonperiodic tilings (quasicrystallography), periodic scheduling, computer vision (digital lines), and formal language theory.)


References [Enhancements On Off] (What's this?)

  • [1] Th. Bang, On the sequence $ [n\alpha ]$, $ n = 1,2, \ldots $, Math. Scand. 5 (1957), 69-76. MR 0092798 (19:1159h)
  • [2] S. Beatty, Problem 3173, Amer. Math. Monthly 33 (1926), 159; 34 (1927), 159.
  • [3] M. A. Berger, A. Felzenbaum, and A. S. Fraenkel, A non-analytic proof of the Newman-Znám result for disjoint covering systems, Combinatorica 6 (1986), 235-243. MR 875291 (88d:11012)
  • [4] -, Disjoint covering systems of rational Beatty sequences, J. Combin. Theory Ser. A 42 (1986), 150-153. MR 843471 (87j:11021)
  • [5] J. Berstel, Langford strings are squarefree, Bull. EATCS 37 (1989), 127-129.
  • [6] M. Boshernitzan and A. S. Fraenkel, Nonhomogeneous spectra of numbers, Discrete Math. 34 (1981), 325-327. MR 613413 (82d:10077)
  • [7] -, A linear algorithm for nonhomogeneous spectra of numbers, J. Algorithms 5 (1984), 187-198. MR 744489 (85j:11183)
  • [8] L. Carlitz, R. Scoville, and V. E. Hoggatt, Fibonacci representations, Fibonacci Quart. 10 (1972), 1-28. MR 0304292 (46:3427)
  • [9] L. Dorst and A. W. M. Smeulders, Discrete representation of straight lines, IEEE Trans. Pattern Anal. Machine Intell. PAMI-6 (1984), 450-463.
  • [10] R. B. Eggleton, A. S. Fraenkel, and R. J. Simpson, Beatty sequences and Langford sequences, Discrete Math. 111 (1993), 165-178. MR 1210094 (94a:11018)
  • [11] P. Erdös, On a problem concerning covering systems, Mat. Lopok 3 (1952), 122-128. (Hungarian; English summary)
  • [12] P. Erdös and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographie No. 28 de L'Enseignement Math., Université de Genève, 1980, 128 pages. MR 592420 (82j:10001)
  • [13] A. S. Fraenkel, The bracket function and complementary sets of integers, Canad. J. Math., 21 (1969), 6-27. MR 0234900 (38:3214)
  • [14] -, Complementing and exactly covering sequences, J. Combin. Theory Ser. A 14 (1973), 8-20. MR 0309770 (46:8875)
  • [15] -, How to beat your Wythoff games' opponent on three fronts, Amer. Math. Monthly 89 (1982), 353-361. MR 660914 (84k:90099)
  • [16] -, Systems of numeration, Amer. Math. Monthly 92 (1985), 105-114. MR 777556 (86d:11016)
  • [17] A. S. Fraenkel, J. Levitt, and M. Shimshoni, Characterization of the set of values $ f(n) = [n\alpha ]$, $ n = 1,2, \ldots $, Discrete Math. 2 (1972), 335-345. MR 0302599 (46:1743)
  • [18] A. S. Fraenkel, M. Mushkin, and U. Tassa, Determination of $ [n\theta ]$ by its sequence of differences, Canad. Math. Bull. 21 (1978), 441-446. MR 523586 (80d:10051)
  • [19] A. S. Fraenkel, H. Porta and K. B. Stolarsky, Some arithmetical semigroups, Analytic Number Theory, Proc. of Conf. in Honor of Paul T. Bateman (B. C. Berndt, H. G. Diamond, H. Halberstam, and A. Hildebrand, eds.), Progress in Math., vol. 85, Birkhäuser, Boston, Mass., 1990, pp. 255-264. MR 1084184 (92h:11004)
  • [20] -, The almost $ PV$ behavior of some far from $ PV$ algebraic integers, (1991), Discrete Math, (inpress)..
  • [21] S. W. Golomb, Discrete chaos: sequences satisfying "strange" recursions, (1991), preprint.
  • [22] R. L. Graham, Covering the integers by disjoint sets of the form $ \{ [n\alpha + \beta ]:n = 1,2, \ldots \} $, J. Combin. Theory Ser. A 15 (1973), 354-358. MR 0325564 (48:3911)
  • [23] R. L. Graham, S. Lin, and C.-S. Lin, Spectra of numbers, Math. Mag. 51 (1978), 174-176. MR 0491580 (58:10808)
  • [24] R. K. Guy, Unsolved problems in number theory, Springer-Verlag, New York, 1981. MR 656313 (83k:10002)
  • [25] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, Oxford Univ. Press, 4th ed., Oxford, 1960.
  • [26] D. Hofstadter, Gödel, Escher, Bach, an external golden braid, Random House, New York, 1979. MR 530196 (80j:03009)
  • [27] W. J. LeVeque, Fundamentals of number theory, Addison-Wesley, Reading, Mass., 1977. MR 0480290 (58:465)
  • [28] M. Lindenbaum and A. Bruckstein, On recursive $ O(N)$ partitioning of a digital curve into digital straight lines (submitted).
  • [29] W. F. Lunnon and P. A. B. Pleasants, Quasicrystallographic tilings, J. Math. Pures Appl. 66 (1987), 217-263. MR 913854 (89e:52028)
  • [30] C. L. Mallows, Conway's challenge sequence, Amer. Math. Monthly 98 (1991), 5-20. MR 1083608 (92e:39007)
  • [31] M. D. McIlroy, A note on discrete representation of lines, AT&T Tech. J. 64 (1984), 481-490.
  • [32] F. Mignosi, On the number of factors of Sturmian words, Theoret. Comput. Sci. 82 (1991), 71-84. MR 1112109 (92g:68082)
  • [33] R. Morikawa, Disjoint sequences generated by the bracket function, Bull. Faculty Liberal Arts, Nagasaki Univ. 26 (1985), 1-13. MR 805434 (87b:11020)
  • [34] C. D. Olds, Continued fractions, Random House, New York, 1963. MR 0146146 (26:3672)
  • [35] R. Penrose, The role of aesthetics in pure and applied mathematical research, Bull. Inst. Math. Appl. 10 (1974), 266-271.
  • [36] -, Pentaplexity: a class of non-periodic tilings of the plane, Eureka 39 (1978). Reprinted in Math. Intelligencer 2 (1979), 32-37. MR 558670 (81d:52012)
  • [37] O. Perron, Die Lehre von den Kettenbrüchen, Band I, Teubner, Stuttgart, 1954. MR 0064172 (16:239e)
  • [38] H. Porta and K. B. Stolarsky, Wythoff pairs as semigroup invariants, Adv. in Math. 85 (1991), 69-82. MR 1087797 (92d:11020)
  • [39] S. Porubský, Results and problems on covering systems of residue classes, Mitt. Math. Sem. Giessen, Heft 150, Giessen, 1981. MR 638657 (83b:10068)
  • [40] A. Rosenfeld, Digital straight line segments, IEEE Trans. Comput. C-23 (1974), 1264-1269. MR 0405960 (53:9752)
  • [41] R. J. Simpson, The Japanese remainder theorem, Tech. Report 3/90, School of Mathematics and Statistics, Curtin University of Technology, Perth, Western Australia, 1990.
  • [42] -, Disjoint covering systems of rational Beatty sequences, Discrete Math. 92 (1991), 361-369. MR 1140599 (93b:11023)
  • [43] Th. Skolem, On certain distributions of integers in pairs with given differences, Math. Scand. 5 (1957), 57-68. MR 0092797 (19:1159g)
  • [44] -, Über einige Eigenschaften der Zahlenmengen $ [\alpha n + \beta ]$ bei irrationalem $ \alpha $ mit einleitenden Bemerkungen über einige kombinatorische Probleme, Norske Vid. Selsk. Forh. (Trondheim) 30 (1957), 118-125.
  • [45] N. J. A. Sloane, A handbook of integer sequences, Academic Press, New York, 1973. MR 0357292 (50:9760)
  • [46] K. B. Stolarsky, Beatty sequences, continued fractions, and certain shift operators, Canad. Math. Bull. 19 (1976), 473-482. MR 0444558 (56:2908)
  • [47] V. Thébault, Les récréations mathématiques, Gauthier-Villars, Paris, 1952.
  • [48] W. D. Wei and C. L. Liu, On a periodic maintenance problem, Oper. Res. Lett. 2 (1983), 90-93.
  • [49] W. A. Wythoff, A modification of the game of Nim, Nieuw Arch. Wisk. 7 (1907), 199-202.
  • [50] S. Znám, A survey of covering systems of congruences, Acta Math. Univ. Comenian. 40-41 (1982), 59-78. MR 686961 (84e:10004)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 11B83, 11B39, 11Z50, 58F13

Retrieve articles in all journals with MSC: 11B83, 11B39, 11Z50, 58F13


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1994-1138949-9
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society