Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Sets of integers with nonlong arithmetic progressions generated by the greedy algorithm

Authors: Joseph L. Gerver and L. Thomas Ramsey
Journal: Math. Comp. 33 (1979), 1353-1359
MSC: Primary 10L10
MathSciNet review: 537982
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ {S_k}$ be the set of positive integers containing no arithmetic progression of k terms, generated by the greedy algorithm. A heuristic formula, supported by computational evidence, is derived for the asymptotic density of $ {S_k}$ in the case where k is composite. This formula, with a couple of additional assumptions, is shown to imply that the greedy algorithm would not maximize $ {\Sigma _{n \in S}}1/n$ over all S with no arithmetic progression of k terms. Finally it is proved, without relying on any conjecture, that for all $ \varepsilon > 0$, the number of elements of $ {S_k}$ which are less than n is greater than $ (1 - \varepsilon )\sqrt {2n} $ for sufficiently large n.

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

  • [1] P. ERDÖS & P. TURAN, "On certain sequences of integers," J. London Math. Soc., v. 11, 1936, pp. 261-264.
  • [2] J. GERVER, "The sum of the reciprocals of a set of integers with no arithmetic progression of k terms," Proc. Amer. Math. Soc., v. 62, 1977, pp. 211-214. MR 0439796 (55:12678)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10L10

Retrieve articles in all journals with MSC: 10L10

Additional Information

Article copyright: © Copyright 1979 American Mathematical Society

American Mathematical Society