Greedy algorithm, arithmetic progressions, subset sums and divisibility
type: Item
instance of: scholarly article
title: Greedy algorithm, arithmetic progressions, subset sums and divisibility
zbMATH Open document ID: 0939.11006
DOI: 10.1016/S0012-365X(98)00385-9
author: Vsevolod F. Lev
author: Gerard Rauzy
author: Csaba Sándor
author: András Sárközy
author: P. Erdős
published in: Discrete Mathematics
publication date: 2000-07-02T00:00:00Z
review text: 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.
reviewed by: Štefan Porubský
Mathematics Subject Classification ID: 11B25
zbMATH DE Number: 1334445
zbMATH Keywords: greedy algorithm
zbMATH Keywords: 3-free set
zbMATH Keywords: arithmetic progression
zbMATH Keywords: subset sums
zbMATH Keywords: divisibility
Wikidata QID: Q105956388
MaRDI profile type: Publication
cites work: Extremal problems on non-averaging and non-dividing sets
cites work: On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
cites work: On the lower estimation of non-averaging sets
cites work: Q5805096
cites work: Q3234565
cites work: Q3872528
cites work: Q5203090
cites work: Q5523758
cites work: Greedily Partitioning the Natural Numbers into Sets Free of Arithmetic Progressions
cites work: Irregular Sets of Integers Generated by the Greedy Algorithm
cites work: Sets of Integers With No Long Arithmetic Progressions Generated by the Greedy Algorithm
cites work: Q4312862
cites work: Integer Sets Containing No Arithmetic Progressions
cites work: Primes in short intervals
cites work: Sums of sets of group elements
cites work: On Certain Sets of Integers
cites work: Finite addition theorems. II
cites work: Q4405161
cites work: On a conjecture of Erdös and Heilbronn
cites work: Integer sets containing no arithmetic progressions
full work available at URL: s0012-365x(98)00385-9
OpenAlex ID: W2052034072
description: scientific article; zbMATH DE number 1334445