|
%I #44 Apr 25 2023 08:17:19
%S 2,4,7,11,15,20,27,32,39,46,56,63,75,83,93,102,118,127,146,156,169,
%T 182,204,215,231,245,261,274,302,315,346,361,379,398,418,432,469,489,
%U 510,527,567,585,627,647,669,693,739,756,788,810,838,862,914,937
%N Cardinality of the union of the set of sums and the set of products made from pairs of integers from {1..n}.
%C 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]
%D Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer-Verlag New York, 2004. Problem F18.
%H Hugo Pfoertner, <a href="/A263995/b263995.txt">Table of n, a(n) for n = 1..10000</a>
%H P. Erdős and E. Szemeredi, <a href="http://renyi.hu/~p_erdos/1983-18.pdf">On sums and products of integers</a>, Studies in Pure Mathematics, Birkhäuser, Basel, 1983, pp. 213-218. DOI:10.1007/978-3-0348-5438-2_19
%H Al Zimmermann's Programming Contests, <a href="http://azspcs.com/Contest/SumsAndProducts1">Sums and Products I</a>, Nov 2015 - Feb 2016.
%F a(n) = A027424(n) + A108954(n). - _Jon Maiga_, Jan 03 2022
%e 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.
%o (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
%o (Python)
%o from math import prod
%o from itertools import combinations_with_replacement
%o 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
%Y Cf. A027424, A108954, A263996.
%K nonn
%O 1,1
%A _Hugo Pfoertner_, Nov 15 2015
|
