A263995 Cardinality of the union of the set of sums and the set of products made from pairs of integers from {1..n}.

2, 4, 7, 11, 15, 20, 27, 32, 39, 46, 56, 63, 75, 83, 93, 102, 118, 127, 146, 156, 169, 182, 204, 215, 231, 245, 261, 274, 302, 315, 346, 361, 379, 398, 418, 432, 469, 489, 510, 527, 567, 585, 627, 647, 669, 693, 739, 756, 788, 810, 838, 862, 914, 937

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.

Formula

a(n) = A027424(n) + A108954(n). - Jon Maiga, Jan 03 2022

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

Cf. A027424, A108954, A263996.

Sequence in context: A025696 A077169 A094277 * A293239 A261878 A261993

Adjacent sequences: A263992 A263993 A263994 * A263996 A263997 A263998

Keyword

nonn

Author

Hugo Pfoertner, Nov 15 2015

Status

approved