login
Number of different products (including the empty product) of any subset of {1, 2, 3, ..., n}.
9

%I #47 Sep 26 2022 14:21:06

%S 1,1,2,4,8,16,26,52,88,152,238,476,648,1296,2016,2984,4232,8464,11360,

%T 22720,30544,43744,67072,134144,166336,242752,370992,498144,656832,

%U 1313664,1581312,3162624,3960384,5517248,8386080,11111232,13065792,26131584,39690432

%N Number of different products (including the empty product) of any subset of {1, 2, 3, ..., n}.

%C a(n) <= 2*a(n-1), with equality iff n is prime or n = 4. - _Martin Fuller_, Jun 03 2006

%C a(n) = 2^k * b(n) where k is the number of primes p such that n/2 < p <= n, and b(n) is the number of different products of subsets of {1, 2, ..., n} that exclude these primes. - _David Radcliffe_, Feb 11 2019

%C Conjecture: Let p <= n be prime. If m and p^a*m are two such products, then so is p^k*m for all 0 < k < a. - _Yan Sheng Ang_, Feb 13 2020

%C a(n) is even for n > 1. Since k is a product implies that n!/k is a product, a(n) is odd implies that n! is a square, which is impossible for n > 1 because of the Bertrand's postulate: for n > 1, there is a prime p in the range (n/2, n], so p divides n! while p^2 does not. - _Jianing Song_, Sep 26 2022

%H Yan Sheng Ang, <a href="/A060957/b060957.txt">Table of n, a(n) for n = 0..68</a> (first 50 terms from David Radcliffe)

%e a(4) = 8: the subsets of {1, 2, 3, 4} are {}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}. The 16 numbers as the product are 1, 1, 2, 3, 4, 2, 3, 4, 6, 8, 12, 6, 8, 12, 24. There are only 8 distinct numbers: 1, 2, 3, 4, 6, 8, 12, 24.

%e a(6) = 26: the set {1, 2, 3, 4, 5, 6, 2*3, 2*4, 2*5, ..., 5*6, 2*3*4, 2*3*5, ..., 4*5*6, ..., ...2*3*4*5*6} contains 26 different values: {1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 20, 24, 30, 36, 40, 48, 60, 72, 90, 120, 144, 180, 240, 360, 720}

%p s:= proc(n) option remember; `if`(n=0, {1},

%p map(x-> [x, x*n][], s(n-1)))

%p end:

%p a:= n-> nops(s(n)):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Aug 25 2016

%t (* Script not convenient for n > 24 *) a[n_] := Times @@@ Subsets[Range[n]] // Union // Length; Table[Print["a(", n, ") = ", an = a[n]]; an, {n, 1, 24}] (* _Jean-François Alcover_, Feb 02 2015 *)

%t s[n_] := s[n] = If[n == 0, {1}, Map[Function[x, {x, x*n}], s[n-1]] // Flatten // Union]; a[n_] := Length[s[n]]; Table[an = a[n]; Print[n, " ", an]; an, {n, 0, 30}] (* _Jean-François Alcover_, Nov 01 2016, after _Alois P. Heinz_ *)

%o (Python)

%o from functools import cache

%o @cache

%o def s(n): return {1} if n == 0 else s(n-1) | set(x*n for x in s(n-1))

%o def a(n): return len(s(n))

%o print([a(n) for n in range(30)]) # _Michael S. Branicky_, Jul 31 2022 after _Alois P. Heinz_

%Y Cf. A070861, A070863, A255937, A307105.

%K nonn,nice

%O 0,3

%A _Jonas Wallgren_, May 10 2001

%E More terms from _Lior Manor_ May 26 2002

%E a(26)-a(32) from _Giovanni Resta_, Feb 14 2006

%E More terms from _Martin Fuller_, Jun 03 2006

%E a(0)=1 and a(37)-a(38) from _Alois P. Heinz_, Aug 25 2016