Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Greedily partitioning the natural numbers into sets free of arithmetic progressions


Authors: Joseph Gerver, James Propp and Jamie Simpson
Journal: Proc. Amer. Math. Soc. 102 (1988), 765-772
MSC: Primary 11B25; Secondary 05A99
DOI: https://doi.org/10.1090/S0002-9939-1988-0929018-1
MathSciNet review: 929018
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We describe a "greedy" algorithm for partitioning the natural numbers into sets free of arithmetic progressions of length 3. A recursive formula governing the resulting partition is proved, and some features of its asymptotic behavior are discussed.


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

  • [1] P. Erdös and P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261-264.
  • [2] H. Furstenberg, Y. Katznelson, and D. Ornstein, The ergodic theoretical proof of Szemerédi's theorem, Bull. Amer. Math. Soc. (N.S.) 7 (1982), 527-552. MR 670131 (84b:28016)
  • [3] J. L. Gerver, Irregular sets of integers generated by the greedy algorithm, Math. Comp. 40 (1983), 667-676. MR 689480 (84d:10056)
  • [4] J. L. Gerver and L. T. Ramsey, Sets of integers with no long arithmetic progressions generated by the greedy algorithm, Math. Comp. 33 (1979), 1353-1359. MR 537982 (80k:10053)
  • [5] Richard K. Guy, Unsolved problems in number theory, Springer-Verlag, 1980.
  • [6] D. J. Newman, Sequences without arithmetic progressions, Analytic Number Theory (Philadelphia, Pa., 1980), Lecture Notes in Math., vol. 899, Springer, Berlin and New York, 1981, pp. 311-314. MR 654536 (83h:10102)
  • [7] A.M. Odlyzko and R. P. Stanley, Some curious sequences constructed with the greedy algorithm, unpublished Bell Laboratories report, January 1978.
  • [8] R. A. Rankin, Sets of integers containing not more than a given number of terms in arithmetical progression, Proc. Roy. Soc. Edinburgh Sect. A 65 (1960/1961), 332-344. MR 0142526 (26:95)
  • [9] K. F. Roth, Sur quelques ensembles d'entiers, C. R. Acad. Sci. Paris 234 (1952), 388-390. MR 0046374 (13:724d)
  • [10] R. Salem and D. C. Spencer, On sets of integers which contain no three terms in arithmetical progression, Proc. Nat. Acad. Sci. U.S.A. 28 (1942), 561-563. MR 0007405 (4:131e)
  • [11] E. Szemerédi, On sets of integers containing no $ k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199-245. MR 0369312 (51:5547)
  • [12] B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw. Arch. Wisk. 15 (1927), 212-216.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 11B25, 05A99

Retrieve articles in all journals with MSC: 11B25, 05A99


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1988-0929018-1
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society