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.
- Extremal problems on non-averaging and non-dividing sets
- Finite addition theorems. II
- Greedily Partitioning the Natural Numbers into Sets Free of Arithmetic Progressions
- scientific article; zbMATH DE number 3121715 (Why is no real title available?)
- scientific article; zbMATH DE number 3675978 (Why is no real title available?)
- scientific article; zbMATH DE number 683826 (Why is no real title available?)
- scientific article; zbMATH DE number 3437146 (Why is no real title available?)
- scientific article; zbMATH DE number 4196054 (Why is no real title available?)
- scientific article; zbMATH DE number 3236148 (Why is no real title available?)
- scientific article; zbMATH DE number 3065959 (Why is no real title available?)
- Integer Sets Containing No Arithmetic Progressions
- Integer sets containing no arithmetic progressions
- Irregular Sets of Integers Generated by the Greedy Algorithm
- On a conjecture of Erdös and Heilbronn
- On Certain Sets of Integers
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- On the lower estimation of non-averaging sets
- Primes in short intervals
- Sets of Integers With No Long Arithmetic Progressions Generated by the Greedy Algorithm
- Sums of sets of group elements
- On \(\text{AP}_{3}\)-covering sequences
- Characters of independent Stanley sequences
- On generalized Stanley sequences
- A note on \(AP_3\)-covering sequences
- On the growth of Stanley sequences
- A note on maximal progression-free sets
- On the classification of Stanley sequences
- Sequences of positive integers containing no p terms in arithmetic progression generated by the greedy algorithm
- Greedily Partitioning the Natural Numbers into Sets Free of Arithmetic Progressions
- On the growth of the counting function of Stanley sequences
- Novel structures in Stanley sequences
This page was built for publication: Greedy algorithm, arithmetic progressions, subset sums and divisibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1301639)
