Unique Sequences Containing No $k$-Term Arithmetic Progressions

  • Tanbir Ahmed
  • Janusz Dybizbánski
  • Hunter Snevily

Abstract

In this paper, we are concerned with calculating $r(k, n)$, the length of the longest $k$-AP free subsequences in $1, 2, \ldots , n$. We prove the basic inequality $r(k, n) \le n − \lfloor m/2\rfloor$, where $n = m(k − 1) + r$ and $r < k − 1$. We also discuss a generalization of a famous conjecture of Szekeres (as appears in Erdős and Turán) and describe a simple greedy algorithm that appears to give an optimal $k$-AP free sequence infinitely often. We provide many exact values of $r(k, n)$ in the Appendix.
Published
2013-12-17
Article Number
P29