OFFSET
1,1
COMMENTS
The November 2015 - Feb 2016 round of Al Zimmermann's Programming Contests asks for sets of positive integers (instead of {1..n}) minimizing the cardinality of the union of the sum-set and the product-set for set sizes 40, 80, ..., 1000. [corrected by Al Zimmermann, Nov 24 2015]
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..10000
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
Al Zimmermann's Programming Contests, Sums and Products I, Nov 2015 - Feb 2016.
EXAMPLE
a(3)=7 because the union of the set of sums {1+1, 1+2, 1+3, 2+2, 2+3, 3+3} and the set of products {1*1, 1*2, 1*3, 2*2, 2*3, 3*3} = {2,3,4,5,6} U {1,2,3,4,6,9} = {1,2,3,4,5,6,9} has cardinality 7.
PROG
(PARI) a(n) = {my(v = [1..n]); v = setunion(setbinop((x, y)->(x+y), v), setbinop((x, y)->(x*y), v)); #v; } \\ Michel Marcus, Apr 13 2022
(Python)
from math import prod
from itertools import combinations_with_replacement
def A263995(n): return len(set(sum(x) for x in combinations_with_replacement(range(1, n+1), 2)) | set(prod(x) for x in combinations_with_replacement(range(1, n+1), 2))) # Chai Wah Wu, Apr 15 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Hugo Pfoertner, Nov 15 2015
STATUS
approved