Greedy algorithm, arithmetic progressions, subset sums and divisibility
A subset of the set of non--negative integers is called \(3\)--free if it contains no \(3\)--term arithmetic progression. In the first part of the paper some results of computer experiments are presented connected with the so called Stanley type greedy algorithm in which the next term of the sequence is generated as the smallest integers exceeding the maximal term of the sequence such that the resulting sequence is \(3\)--free. The first `theoretical' result shows that there is an infinite \(3\)--free set \(A=\{a_1,a_2,\dots\}\) such that \(a_1=1\) and \(a_k\in[k^2,k^2+k-2]\) for \(k\geq 2\). This yields an improvement on the difference between consecutive terms of an infinite \(3\)--free set which can be deduced from greedy type constructions. The next group of results is motivated by the observation that in a \(3\)--term arithmetical progression the middle term divides the sum of the other two. The authors introduce three properties named P (no term divides the sum of distinct greater terms), Q (no term divides the sum of distinct other terms), and R (no subsum of a finite number of terms divides another subsum of the same type) and give some results centered about these properties. For instance, if \(P(n)\) and \(Q(n)\) denote the number of a maximal subset of \([1,n]\) with property P, and Q, resp., then \(\sqrt{2n}-3/2\leq P(n)\leq 3\sqrt{n}+1\), or \(Q(n)<3\sqrt{n}+1\), etc. A bunch of various open problems is spread throughout the paper.
scientific article; zbMATH DE number 1334445
scientific article