A263996 Smallest possible cardinality of the union of the set of pairwise sums and the set of pairwise products from a set of n positive integers.

1, 4, 7, 11, 15, 20, 26, 30, 36, 44, 49, 57, 64, 71, 80, 86, 96, 104, 112, 121, 131, 141, 150, 160, 169, 179, 190, 200, 212, 222, 235, 248, 260, 272, 283, 296, 307, 320, 335, 348, 360, 371

Offset

1,2

Comments

The November 2015 - February 2016 round of Al Zimmermann's programming contests asked for optimal sets producing a(40), a(80), a(120), ..., a(1000).

References

Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer-Verlag New York, 2004. Problem F18.

Links

Hugo Pfoertner, Table of n, a(n) for n = 1..205

P. Erdős and E. Szemeredi, On sums and products of integers, Studies in Pure Mathematics, Birkhäuser, Basel, 1983, pp. 213-218. DOI:10.1007/978-3-0348-5438-2_19

Kevin Hartnett, How a Strange Grid Reveals Hidden Connections Between Simple Numbers, Quanta Magazine, Feb. 6 2019.

Al Zimmermann's Programming Contests, Sums and Products I, Nov 2015 - Feb 2016.

Example

a(1) = 1 because for the set {2} the union of {2+2} and {2*2} = {4}.
a(7) = 26: The set {1,2,3,4,6,8,12} has the set of pairwise sums {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,24} and the set of pairwise products {1,2,3,4,6,8,9,12,16,18,24,32,36,48,64,72,96,144}. The cardinality of the union of the two sets, {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,24,32,36,48,64,72,96,144}, is 26. This is the first nontrivial case with a(n) < A263995(n), which uses the set {1..n}.

Crossrefs

Cf. A027424, A263995.

Sequence in context: A130252 A130254 A278114 * A172472 A134918 A310741

Adjacent sequences: A263993 A263994 A263995 * A263997 A263998 A263999

Keyword

nonn

Author

Hugo Pfoertner, Nov 15 2015

Status

approved