On Sequences Without k-Term Geometric Progressions

作者：Huang, Zhengwen^*; Shao, Zehui; Deng, Fei; Xu, Xiaodong

来源：Journal of Computational and Theoretical Nanoscience, 2014, 11(2): 358-362.

DOI：10.1166/jctn.2014.3361

• Geometric Progression
• Computer Search
• Integer Linear Programming

Let k >= 2, a k-term geometric progression, also called a k-GP, is a sequence of positive integers {a(1), a(2), ... ,a(k)} such that there is a non-zero number r with the property that a(i+1) = a(i)r for i = 1, 2, ... , k - 1. For positive integers n and k, let g(k)(n) be the size of the largest subset of {1, 2, ... , n} without geometric progressions of length k. Rankin in 1960 suggested looking at sequences without k-term geometric progressions, and constructed such sequences for each k with positive density. In this paper, we present techniques to find large k-GP free sets of {1, 2, ... , n}, and give empirical results obtained by coding up those techniques. Moreover, iterated rounding approximation algorithm is used to obtain lower bounds and the experimental results show that it produces better lower bounds than previous greedy lower bounds.

• 出版日期2014-2
• 单位广西科学院; 成都理工大学; 中国环境科学研究院; 成都大学